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