Next: Edge Flip Algorithm Up: Algorithms Previous: Algorithms

## Plane Sweep Algorithm for Triangulation and Convex Hull

Plane Sweep is a very powerful approach for solving problems involving geometric objects in the plane. Best examples for such problems are line segments intersection, finding the contour of the union of rectangles and Voronoi diagrams as discussed in [6], [9] and [2]. In sweeping, an imaginary vertical sweepline passes through the geometrical objects, usually from left to right. As the sweepline moves, problem has been solved for the data to the left of the sweepline, is currently being solved for the data at or near the sweepline and is going to be solved sometime later for the data to right of the sweep-line. Basically, plane sweep reduces a problem in two dimensional space to a series of problems in one dimensional space. It is very beneficial because to solve a one dimensional problem is much easier. However, in order to achieve such a reduction one needs to sort the objects (points in our case) from left to right. Since the time complexity of the sorting algorithm is critical, I used a slightly modified version of quicksort algorithm discussed in [2]. Modification is due to the relatively bad performance of quicksort for small number of data. For n less than some CUTOFF value insertion sort is called. Experimentally, a good CUTOFF value is specified as 10 in [14]. Here is the pseudo code for the sweepline algorithm:
. Sort points from left to right
. Construct the initial triangle (convex hull) using the first three points
. for i = 4 to n do
Using as the starting point
Move counterclockwise on the convex polygon until the tangent points,
inserting the edges between and polygon point to the triangulation
Using as the starting point
Move clockwise on the convex polygon until the tangent points,
inserting the edges between and polygon point to the triangulation
Update the convex hull removing all points visible to except
the tangent points and inserting between the two tangent points.
endfor

Next: Edge Flip Algorithm Up: Algorithms Previous: Algorithms

Alper Ungor
Tue May 13 15:38:16 CDT 1997