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
x, y and the point p3 located separately at both sides
of Segment
1x1,y1
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
1p with
p2
, the point
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
Copyright © 2012 SciRes. AJCM