 American Journal of Computational Mathematics, 2012, 2, 336-340 http://dx.doi.org/10.4236/ajcm.2012.24046 Published Online December 2012 (http://www.SciRP.org/journal/ajcm) Research on Algorithm of the Point Set in the Plane Based on Delaunay Triangulation Bin Yang, Shuyuan Shang School of Information Engineering, Beijing Institute of Fashion Technology, Beijing, China Email: 84957043@163.com, shangshuy@163.com Received August 1, 2012; revised September 19, 2012; accepted September 30, 2012 ABSTRACT In the paper, an improved algorithm is presented for Delaunay triangulation of the point-set in the plain. Based on the original algorithm, we propose the notion of removing circle. During the process of triangulation, and the circle dy- namically moves, the algorithm which is simple and practical, therefore evidently accelerates the process of searching a new point, while generating a new triangle. Then it shows the effect of the algorithm in the finite element mesh. Keywords: Point-Set in the Plane; Delaunay Triangulation; Removing Circle; Finite Element Mesh 1. Introduction Triangulation is an important task to geometric geo- physical processes. It is widely used, such as in digital terrain model (DEM), image processing, etc. It compared with other types of polygon, there are many characteris- tics and advantages, for example it can be used to close to the fitting complex boundary better, generate the finite element mesh and be used in computer graphics process- ing and pattern recognition. In 3D virtual modeling sur- face description and many other fields [1-3], there are algorithms of triangulation. Therefore, in order to solve the problems, people develop many algorithms. Among them, the algorithm of Delaunay triangulation is the most famous, but also commonly used methods in triangula-tions [4-7]. 2. Definitions and Conceptions 1) If in the 2D plane geophysical processes all bounded areas are triangle, this plane split will be called triangula- tion. And the finite-set M is a triangulation with the maximum number of plan edges. 2) Set the point X in the plane, the area 2, , , 1,2,,, ijVix RdxpdxpjNj i   is called polygon Voronoi [8,9]. Set the distance d(x,pi) between point x to point pi in the point-set P that contains many different points in n-dimensional Rn Euclidean space. A convex hull called n-dimensional simplex is consisted of (n + 1) vertexes in an Rn− dimensional space. It is shown in Figure 1, two dimensional simplex as triangle, 3D simplex for tetrahe- dron . In the two dimensional space, the neighborhood V1V2V3V4V5 of the point p in Figure 2(a) is the part of the gray area whose boundary is a convex polygon called polygon Voronoi of the point p and is consisted of per- pendicular bisectors of the point p in connection with the adjacent nodes. And the polygon Voronoi contains only one node. A graph of Doronoi constitutes the polygons of all points in the point set. And it is shown in Figure 2(b). After the graph Voronoi is made, we will do its dual graphs, that is, the perpendicular bisectors of each edge Voronoi going through the two points in the point set. Normally, a vertex of a graph of Voronoi belongs to three polygons of Voronoi, while there is only one node in each polygon Voronoi. The set of triangles is Delau- nay triangle mesh dissection which is called Delaunay triangulation. A Delaunay triangulation and its dual graphs is shown in Figure 2(c ). 3. Some Basic Properties of the Delaunay Triangulation Setting a point set P that contains n discrete points in the two-dimensional domain, there are several ways to achieve dissection of the point set P. Criterion for empty circumscribed circle: for the given point set P in 2D Euclidean space P, there is no dissect- tion point in the circumscribed circles of any two-di- mensional simplex within D(P). The whole area is com- pletely covered with all non-overlapping Delaunay train- gles. Criterion for partial restriction: it is specifically shown that Delaunay triangulations will be regained only through partial modification after adding, removing or moving a vertex in existing D(P). The set consisting of Copyright © 2012 SciRes. AJCM B. YANG, S. Y. SHANG 337 (a) (b) Figure 1. Simplexes. (a) 2D simplex—triangle; (b) 3D sim-plex—tetrahedron. (a) (b) (c) Figure 2. The formation process of two dimensional delau-nay triangulation. (a) The neighborhood of the point p and Polygon voronoi; (b) A graph of vorono; (c) The triangula-tion of delaunay. all triangles you need to modify is called domain of in-fluence. It can be proved that each vertex within domain of influence is visible for the point added or deleted, thus domain of influence is partially limited. Criterion for the largest minimum angle: it is proved by Russian mathematician Delaunay in 1934: there must be only one algorithm of triangulation, making the sum of the minimum angles inside a triangle the largest. De- launay triangulation can avoid the triangles that do not meet the criteria, and this is finite element mesh genera- tion needs. In 1977, Sibson  proved, it is equivalent for the point-set in the plane to be associated with the criterion for Voronoi neighborhood, the criterion for empty cir- cumscribed circle and the criterion for the largest mini- mum angle, and there is only one so-called Delaunay triangulation which meets these three criteria. Specifi- cally speaking, as for a given point set P in the plane, each of triangulations T(P) always contains a triangle whose inner angle is the smallest, yet the smallest angle is the largest one among the minimum angles. It is be- cause of the property that Delaunay triangulation is al- ways possible avoiding the emergence of a “long and thin” triangle and automatically closes to an equilateral triangle. It should be noted that the characteristics of De- launay triangulation apply only to a point-set. Delaunay triangulations of 3D and more dimensions don’t have the corresponding character. Apparently, this is a specific property of the set of two-dimensional Delaunay train- gulation of points different from the more-dimensional point set [4-7]. 4. The Description of Algorithm The basic idea of the paper based on two-dimensional Delaunay triangulations of a point-set in the plane is: first a triangular that meets the conditions is generated, then a new triangle should be generated based on each edge of the triangle which go to match the proper point in differ- ent directions, finally, a network of triangulation will be created by growing around based on the new triangle and all points covered with the plane, and the network meets the requirements. The algorithm lies in the growth of each new triangle. And the key to the growth of a triangle is the extension of each edge, in other word, a qualified point might be found in two-dimensional point-set to form a new train- gle. The extended side should meet the following four conditions: 1) the qualified point is not on the extending side or its extension line (namely, they are not collinear); 2) the qualified point and the third point of the triangle must stay separately at both sides of the extending edge; 3) each edge of a triangle is used twice at most; 4) a an-gle formed by connecting the qualified point and two Copyright © 2012 SciRes. AJCM B. YANG, S. Y. SHANG 338 vertexes of the extended side should be as large as possi- ble . The basic procedure of triangulation algorithm in the two-dimensional point set is as follows: Input: in the plane, setting a point Set M that contains n points with coordinates (xi, yi), i = 1, ···, n. Output: in the plane, the List N of triangulation with n points. First, Input: the vertices p1, p2, p3 (not in a straight line) of the triangle to be extended, edge p1p2 to be ex- tended; Second, Compare the frequency Count of utilization of the edge p1p2 with two: the count = two, then return to the First to find other extending edge; if the count < two, to continue; Third, Search the qualified points in the point set M, and take them out from the set successively; In the implementation of the Third, it will have the fol- lowing several situations: 1) judge whether the point P and the extending edge p1p2 is collinear, if so, then turn the Third, otherwise continue; 2) judge whether the point px, y and the point p3 located separately at both sides of Segment p1x1,y1 p2x2,y2, the result of judg-ment depends on whether the values of the two third- order determinants is the same plus-minus sign, if it is positive, it means that the point P and the point p3 stay at the same side of Segment p1p2, then turn the Third, oth-erwise continue; 3) examine whether point p1, point p2 and point P locate the same segment, if so, when the fre-quency Count of utilization of a edge is two, to it turns the Third, if the count < two, to continue; Fourth, Calculate the degree of the angle of p1p with pp2 and p1p with pp2, the point p is the last found point. If the degree of a new angle is lower than that of the angle with the last-found point, the value of the point P will be written down and update in the List M, then continue; otherwise returns the Third; Fifth, since the point P is what the algorithm requires, the triangle with the three vertexes p1, p2 and P is put into the List N of triangulation. Sixth, Update the record of the list with p1, p2 and P separately, and delete all the points with the frequency of use of edges equivalent to 2, return the Third, and find n qualified points in the point-set, at the last output and terminate. The flow chart of algorithm is shown in Fig- ure 3. It can be found from the experiments: 1) In fact, all the triangles except the first triangle grow from one edge of a triangle. 2) Actually, in the growth of two dimensional triangu- lation, (that is, to be extended later in the diameter of the circle edge points) it is impossible for some points to participate in the generation of new triangle, so their judgments should be cancelled. In the original algorithm, c hoose three ri ght point s t o m ake up a t riangle i n t he s et of points M, choose one s ide for expansion if the c ount that expand s i de used is l ess t han 2c hoose quali fied poi nt P i n the set M if t he poi nt p is c ol l i near t o ex pand edge judgi ng if point p and point p3 i s i n the same s ide of ex pand s i de i f the count t hat p1p and pp2 us ed is less t han 2 updat e set M and rec ord poi nt preco rdi n g p 、p1 and p2 i n t he s et N and delete the points t hat count of edge used i s 2. YN i f the incl uded angle bet ween p1 p and pp2 i s less t han the i ncluded angl e between p1 p’ and p’ p2 YYNYNNNY Figure 3. The flow chart of algorithm. the search time of the third point is basically proportional to the total number of points when the edge is being ex- tended, after removing these points that are not associ- ated with the generation of a triangle, during the genera- tion, the range of the search will dynamically lower in the two-dimensional point-set and the search time will be greatly shortened. It is found easily that the more points, the more obvious the effect. And it will be verified in the later experiment. 5. Improvement of Triangulations Algorithm During the extension of the triangle, searching the third point is the criterion for judging the size of angle, but in most cases, distance also has a great influence on its. Specifically, under the condition of an equal angle, it is usually found that it is the third point that a point is closer to the edge, not far away from the edge. And this is not mentioned in the original algorithm. In this case, a new kind way is put forward in this paper: choose an edge of an original triangle as extending edge, then a Copyright © 2012 SciRes. AJCM B. YANG, S. Y. SHANG 339article whose diameter is the length of the edge is made. Search the point on the circle and write them down [10- 12]. And compare distances between these points and the diameter, keep the point that is closer to the edge and form a new triangle with the diameter. Finally, a network will be created by expanding around based on the new triangles and all points covered with the plane, and meet the requirements of triangulation. Improvement of trian-gulartion algorithm in the original algorithm is as follows: During the Third in the original algorithm, add a circle with the diameter equivalent to the length of an extend- ing edge, it is shown in Figure 4. And choose the point closest to extending edge on the circle, to delete some Choose the qualified points in the point set (locate the circle whose diameter is the length of the extending side) Choose the points closest to the extending side on the circle Figure 4. The new algorithm. (a) (b) (c) Figure 5. The differences of two methods; (a) The original method; (b) The process of new method; (c) The new method. List 1. The differences of two methods. Methods of triangulation The number of triangle (k) Computing time (s) Memory consumption (M)The original 100 15 s 45 M New 147 18 s 46 M points. This optimizes the original algorithm and accel- erates the speed of the algorithm. The experimental results show that compared with the original algorithm, the speed of improved algorithm in-creases slowly, shown in list 1, but the quality (accuracy) of triangulation gets obvious improvement, the experi-mental results shown as Figure 5. The quality of trian-gulation is the most importantly valued, and this is con-sistent with the ideas of the algorithm. Because of simple structure, practical applicability and universality of algo-rithm of and it can meet what the practical engineering needs. REFERENCES  Q.-L. Li, “Three-Dimensional Modeling Based on the Statue of Point Cloud Data,” Master’s Thesis, Tongji University, Shanghai, 2009.  G.-H. Peng, “Technical Research on Surface Reconstruc-tion Based on Scattered Data,” Master’s Thesis, North-western Polytechnical University, Fremont, 2006.  Y. Huang, W. Yu and T. Chen, “Three-Dimensional Body Scanning System for Apparel Mass Customiza-tion,” Optical Engineering, Vol. 41, No. 7, 2002, pp. 1475-1479. doi:10.1117/1.1478700  W. Sun, C. Bradley, Y. E. Zhang and H. T. Loh, “Cloud Data Modeling Employing a Unified Non-Redundant Tri-angular Mesh,” Computer-Aided Design, Vol. 33, No. 2, 2001, pp. 183-193.  R. Sibson, “Locally Equiangular Triangulation,” Com-puter Journal, Vol. 21, No. 3, 1977, pp. 243-245. doi:10.1093/comjnl/21.3.243  H.-B. Ling and B. Wu, “An Improved Algorithm for Auto-Connection Delaunay Triangulation,” Computer Application, Vol. 19, No. 12, 1999, pp. 10-12.  L. Guibas, “Basic Algorithms and Combinatorics in Compu-Tatinal,” Worksh on Computational Geometry, 1986, p. 119.  Z. Zhou and R.-T. Liu, “A New Triangulation Algorithm of the Point Set in the Plane,” Journal of Harbin Univer-sity of Science and Technology, Vol. 12, No. 2, 2007, pp. 78-80.  P.-D. Zhou, “The Algorithm for Triangulation of the Pint Set in the Plane,” Journal of Computer Aided Design and Computer Graphics, Vol. 8, No. 4, 1996, pp. 259-264.  X.-D. Li, “Algorithm Implementation of Two-Dimension and Multi-Dimension Linked Lists,” Journal of Foshan Institute of Science and Technology, Vol. 21, No. 3, 2003, pp. 35-38. Copyright © 2012 SciRes. AJCM B. YANG, S. Y. SHANG Copyright © 2012 SciRes. AJCM 340  A.-J. Chen, J.-D. Li and D.-D. Li, “Improved Random-ized Algorithm for Circle Detection,” Opto-Electronic Engineering, Vol. 33, No. 12, 2006, pp. 92-93.  J.-R. Wang and H.-T. Zheng, “The Projection Model and Application Based on Oval and Round,” Mathematics of Shanghai Middle School, Vol. 6, 2007, p. 47.