The first industrial project of GeMMA was aimed to provide two robust dynamic link libraries for the German branch of the renowned engineering software producer. We have developed a novel polygon trapezoidation algorithm and adapted an existing polygon triangulation algorithm. Both of them are based on a sweep-line paradigm. They can handle simple (non-self-intersecting) polygons with or without holes. The latter may be separately trapezoidated/ triangulated on a request. After months of intensive testing in the AUTODESK’s testing department, our solutions were accepted for incorporation in a worldwide used commercial software product, while GeMMA was honoured with the AUTODESK’s certificate of quality. Besides the feasibility, correctness and speed, we also had to achieve high level of numerical robustness by avoiding all arithmetical operations that could produce inexact results: floating point divisions, triangular functions and square root calculations.

The proposed polygon trapezoidation algorithm represents an original approach. As the sweepline glides over the plane, a set of so-called open trapezoids is generated and maintained. An actual trapezoid is cut from the open one by adding a horizontal side in accordance with the context of a processed vertex. In this manner, a simple polygon is partitioned into a set of trapezoids with horizontal parallel sides. These may be limited either with original or with newly added vertices. Some trapezoids may also be degenerated into triangles. In comparison to the fastest Seidel’s method at the time, our algorithm revealed 30 to 100% faster performance, although both methods require O(n log n) time with respect to the number of vertices n.

Another problem considered in the project was the polygon triangulation. One could use the trapezoidation and then partition each trapezoid into two triangles, but our costomers preferred the solution without additional vertices that would typically appear during the trapezoidation. We have utilized quite traditional two-step approach which firstly decomposes the input polygon into the so-called y-monotone pieces as proposed by Garey, Johnson, Preparata and Tarjan (1978), and then separately triangulates each separate y-monotone polygon with the method introduced by Lee and Preparata (1977). To achieve the required speed, we have slightly adapted the algorithm by utilizing some redundant data structures, particularly the so-called neighbour tree for each vertex.

The theoretical analysis has shown that the first step runs in O(n log NMS), where NMS is the number of monotone pieces, while the triangulation itself requires linear O(n) time. Since the sweep-line algorithm must be pre-processed by sorting and since a popular quicksort performs best in random case, but appears slow in intuitively the simplest cases (corresponding to polygons with low NMS), this project initiated our increased interest in developing adaptive sorting algorithms. Our original solutions include vertex sort, smart quicksort and finally (still unpublished) smart merge sort.