Computing Minimum Distance between Curves/Surfaces Based on PSO Algorithm
|School||Fujian Normal University|
|Keywords||B-Spline Curve B-Spline Surface Particle Swarm Optimization Algorithm Newton iteration the minimum distance|
The problems of minimum distance have many applications in lots areas. Nowadays, parametric curves or surfaces are used as the mainstream models in modeling systems. Most former algorithms have a lot flaws, such as:computing methods are complex, the algorithms’application scope are limited. But algorithms of Artificial Intelligence have the advantage of flexibility. They can be applied to the computing of the minimum distances between complicated curves or surfaces. This thesis mainly studies the minimum distance problems of parameter curves or surfaces. The main works and contributions are summarized as follows:According to the principle of the particle swarm optimization algorithm, traditional idea is as follows:each point at a B-Spline curve is set as a particle. Then each point is translated, according to the formulas of the particle swarm algorithm. But the new position, if in this way, may be out of the curve. To solve this problem, the idea of applying the particle swarm optimization to the parametric domain to compute the minimum distance between two B-Spline curves, is proposed. Firstly, the algorithm sets some points in each parametric domain. The points’number in each parametric domain is the same. The points are matched randomly from one parametric domain to the other. Secondly, each pair’s distance and the minimum distance are computed. And each point’s personal parametric best value is computed. Each point’s group’s parametric best value is computed, too. Thirdly, according to the PSO algorithm, after its iteration, each point’s personal parametric best value and group’s parametric best value are renewed. When the algorithm’s termination condition is satisfied, the minimum distance between two B-Spline curves is computed. This algorithm is simple and the experiences show that it has a good effort.According to the analysis of the algorithm’s experiences, an improved algorithm is put forward. The improvement includes the improvement matching ways for two far-away points and the improvement of precision. The experience shows the efficiency is improved by finding the minimum distance pairs. The experience also shows the precision is improved by using Newton iteration.The thesis has extended the methods for computing the minimum distance between two curves to two surfaces. An algorithm for computing the minimum distance between two B-Spline surfaces based on the parametric domain. And an improved algorithm has been put forward. The experiences show that the algorithms have good convergence, efficiency and perception.The thesis also puts forward the algorithm for the minimum distance between two B-Spline surfaces. After the analysis of the experiences, an improved algorithm is put forward. The improved algorithm has the advantage of higher efficiency and better precision.The methods mentioned in the thesis can be applied to many areas, not only B-Spline curves or surfaces, but also other kinds parametric of curves or surfaces. The basic idea can be applied to other kinds parametric of curves or surfaces. The methods can be applied to the distances between points to curves or surfaces, curves to curves or surfaces, surfaces to surfaces and so on. The methods have the meaning for further researches.