Algorithms for the Triangulation of Plane Line-Segment Sets
Zhou Pei-de · Computer Engineering and Science · 2003
Two algorithms are presented for computing the triangulation of plane line-segment sets. The first one is to use the idea of plane sweep. When the sweep-line reaches it, the event-point will be dealt with, i.e. the event-point is connected with some sweeped points, so that the sweeped regions are triangulated. When the sweep-line reaches the leftest event-point, the point will be dealt with, and the triangulation of plane line-segment sets is accomplished. The second one is based on computing the convex hulls layer by layer, and convex hulls are changed into ploygons. Thus the embedded polygonal layers are formed. The regions inside the convex hull of a line-segment set is covered with these polygons. Then each polygon is triangulated, i.e. the triangulation of the plane line-segment set is accomplished.The time complexities of the two algorithms are respectively O( nlogn) and O( mnlogn) , where n is the number of line-segments in the line-segment set, m is the number of layers of the convex hull.