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
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,,,
ij
Vix 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 [2].
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
C
opyright © 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 [5] 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

B. YANG, S. Y. SHANG 338
vertexes of the extended side should be as large as possi-
ble [6].
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

p
x, y and the point p3 located separately at both sides
of Segment

p
1x1,y1

p
2x2,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
p
1p with
p
p2
, 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 2
c 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 p
reco 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.
Y
N
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
Y
Y
N
Y
N
N
N
Y
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

B. YANG, S. Y. SHANG 339
article 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
[1] Q.-L. Li, “Three-Dimensional Modeling Based on the
Statue of Point Cloud Data,” Master’s Thesis, Tongji
University, Shanghai, 2009.
[2] G.-H. Peng, “Technical Research on Surface Reconstruc-
tion Based on Scattered Data,” Master’s Thesis, North-
western Polytechnical University, Fremont, 2006.
[3] 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
[4] 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.
[5] R. Sibson, “Locally Equiangular Triangulation,” Com-
puter Journal, Vol. 21, No. 3, 1977, pp. 243-245.
doi:10.1093/comjnl/21.3.243
[6] H.-B. Ling and B. Wu, “An Improved Algorithm for
Auto-Connection Delaunay Triangulation,” Computer
Application, Vol. 19, No. 12, 1999, pp. 10-12.
[7] L. Guibas, “Basic Algorithms and Combinatorics in
Compu-Tatinal,” Worksh on Computational Geometry,
1986, p. 119.
[8] 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.
[9] 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.
[10] 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.

B. YANG, S. Y. SHANG 340
[11] 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.
[12] 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.