Implementation of the Clarkson, Cole and Tarjan trapezoid decomposition probabilistic algorithm [1] by Dimitrios Gunopulos (2/92). With some handy command-line options by Nina Amenta (7/94). The algorithm: The input is a simple polygon. The algorithm computes the trapezoid decomposition in O(log*n) phases, each taking O(n) time to complete. In each phase a set of edges is considered. The edges are assigned to phases in the beginning, using a randomized scheme. In the first phase, a bounding box is partitioned to trapezoids by the first set of edges. In subsequent phases each new set of edges farther refines the trapezoid decomposition. In the end, a subdivision of both the polygon and the bounding box is obtained. The trapezoids have their parallel edges horizontal. A simple O(n log n) algorithm is used to partition the first set of edges. When the -p command line option is specified, this algorithm is used for the entire trapezoidation. Most polygons will be small; so this will generally be faster. The input: It is read from standard input. The polygon is given as a chain of consecutive vertices (2 floats each - x and y coordinates) with the length of the chain given first (int). The algorithm does not terminate if two points have the same y coordinate, or if two non consecutive edges of the input polygon intersect (so the polygon is not simple). A sample input file is given below. The ouput: The procedure trap_dec() returns a pointer x to the top trapezoid in the interior of the polygon. The top trapezoid of the bounding box is x->upm. The procedures reportintraps() and reportalltraps() give the list of the trapezoids in the polygon and the list of all trapezoids found, respectively. The procedure reporttrap(x) prints information for a given trapezoid x. The default mode is to print only the trapezoids that decompose the interior of the input simple polygon. The command -a also reports the trapezoids outside the polygon (in the bounding box). With the -o command line option, the program produces just a list of trapezoid vertices. These are given as an OOGL .quad file, a format which can be viewed using the GeomView visualization system (available from The Geometry Center at ftp.geom.umn.edu). Each line gives the four vertices of one trapezoid, as three-dimensional points lying in the plane z=0. Sample output is given below. [1] Randomized Parallel Algorithms for Trapezoidal Diagrams, Clarkson, Cole, Tarjan, 7th Ann. Symposium on Computational Geometry, 1991. Sample input file: --- 20 91.000000 52.000000 33.000000 79.000000 1.000000 82.000000 -66.250000 21.750000 -41.500000 33.500000 12.000000 25.000000 43.000000 36.000000 35.500000 41.500000 34.000000 55.000000 5.500000 70.500000 85.000000 30.000000 55.000000 40.000000 44.000000 46.000000 63.000000 12.000000 69.000000 2.000000 75.000000 8.000000 76.750000 13.250000 72.500000 26.500000 88.000000 5.000000 95.500000 32.500000 --- Sample default output (these are the first trapezoids for the input polygon given): decomposition: trapezoid number: 64 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 138 right edge 1.000000 82.000000 33.000000 79.000000 right edge number: 137 top line: 82.000000 , bottom line: 79.000000 the four vertices are : (1.000000, 82.000000),(1.000000, 82.000000), (33.000000, 79.000000),(-2.348548, 79.000000) upl NULL upm 32 upr NULL downl 66 downm NULL downr 66 upprev NULL upnext NULL downprev NULL downnext NULL trapezoid number: 66 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 138 right edge 33.000000 79.000000 91.000000 52.000000 right edge number: 136 top line: 79.000000 , bottom line: 70.500000 the four vertices are : (33.000000, 79.000000),(-2.348548, 79.000000), (51.259262, 70.500000),(-11.836100, 70.500000) upl 64 upm NULL upr 64 downl 68 downm 43 downr 59 upprev NULL upnext NULL downprev 63 downnext 67 trapezoid number: 68 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 139 right edge 5.500000 70.500000 34.000000 55.000000 right edge number: 9 top line: 70.500000 , bottom line: 55.000000 the four vertices are : (5.500000, 70.500000),(-11.836100, 70.500000), (34.000000, 55.000000),(-29.136929, 55.000000) upl 66 upm NULL upr 66 downl 69 downm NULL downr 69 upprev 33upnext NULL downprev 63 downnext NULL trapezoid number: 69 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 140 right edge 34.000000 55.000000 35.500000 41.500000 right edge number: 8 top line: 55.000000 , bottom line: 41.500000 the four vertices are : (34.000000, 55.000000),(-29.136929, 55.000000), (35.500000, 41.500000),(-44.205395, 41.500000) upl 68 upm NULL upr 68 downl 70 downm NULL downr 70 upprev 34upnext NULL downprev 63 downnext NULL trapezoid number: 70 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 141 right edge 35.500000 41.500000 43.000000 36.000000 right edge number: 145 top line: 41.500000 , bottom line: 36.000000 the four vertices are : (35.500000, 41.500000),(-44.205395, 41.500000), (43.000000, 36.000000),(-50.344398, 36.000000) upl 69 upm NULL upr 69 downl 72 downm NULL downr 72 upprev 35upnext 71 downprev NULL downnext NULL trapezoid number: 72 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 141 right edge 43.000000 36.000000 12.000000 25.000000 right edge number: 144 top line: 36.000000 , bottom line: 33.500000 the four vertices are : (43.000000, 36.000000),(-50.344398, 36.000000), (35.954544, 33.500000),(-53.134853, 33.500000) upl 70 upm NULL upr 70 downl 74 downm 40 downr 42 upprev NULL upnext NULL downprev 63 downnext 73 trapezoid number: 74 left edge 1.000000 82.000000 -66.250000 21.750000 left edge number: 142 right edge -41.500000 33.500000 -66.250000 21.750000 right edge number: 4 top line: 33.500000 , bottom line: 21.750000 the four vertices are : (-41.500000, 33.500000),(-53.134853, 33.500000), (-66.250000, 21.750000),(-66.250000, 21.750000) upl 72 upm NULL upr 72 downl NULL downm 37 downr NULL upprev 36upnext NULL downprev 63 downnext NULL --- Sample OOGL output: QUAD 1.000000 82.000000 0.0 1.000000 82.000000 0.0 -2.348548 79.000000 0.0 33.000000 79.000000 0.0 96.500000 83.000000 0.0 -67.250000 83.000000 0.0 -67.250000 82.000000 0.0 96.500000 82.000000 0.0 1.000000 82.000000 0.0 -67.250000 82.000000 0.0 -67.250000 21.750000 0.0 -66.250000 21.750000 0.0 57.551472 21.750000 0.0 -67.250000 21.750000 0.0 -67.250000 12.000000 0.0 63.000000 12.000000 0.0 63.000000 12.000000 0.0 -67.250000 12.000000 0.0 -67.250000 2.000000 0.0 69.000000 2.000000 0.0 96.500000 2.000000 0.0 -67.250000 2.000000 0.0 -67.250000 -1.000000 0.0 96.500000 -1.000000 0.0 1.000000 82.000000 0.0 1.000000 82.000000 0.0 -2.348548 79.000000 0.0 33.000000 79.000000 0.0 33.000000 79.000000 0.0 -2.348548 79.000000 0.0 -11.836100 70.500000 0.0 51.259262 70.500000 0.0 5.500000 70.500000 0.0 -11.836100 70.500000 0.0 -29.136929 55.000000 0.0 34.000000 55.000000 0.0 34.000000 55.000000 0.0 -29.136929 55.000000 0.0 -44.205395 41.500000 0.0 35.500000 41.500000 0.0 35.500000 41.500000 0.0 -44.205395 41.500000 0.0 -50.344398 36.000000 0.0 43.000000 36.000000 0.0 43.000000 36.000000 0.0 -50.344398 36.000000 0.0 -53.134853 33.500000 0.0 35.954544 33.500000 0.0 -41.500000 33.500000 0.0 -53.134853 33.500000 0.0 -66.250000 21.750000 0.0 -66.250000 21.750000 0.0 -41.500000 33.500000 0.0 -41.500000 33.500000 0.0 -59.404255 25.000000 0.0 12.000000 25.000000 0.0 55.735294 25.000000 0.0 -59.404255 25.000000 0.0 -66.250000 21.750000 0.0 57.551472 21.750000 0.0 35.954544 33.500000 0.0 -41.500000 33.500000 0.0 12.000000 25.000000 0.0 12.000000 25.000000 0.0 5.500000 70.500000 0.0 5.500000 70.500000 0.0 34.000000 55.000000 0.0 35.925926 55.000000 0.0 35.925926 55.000000 0.0 34.000000 55.000000 0.0 35.000000 46.000000 0.0 53.592594 46.000000 0.0 44.000000 46.000000 0.0 35.000000 46.000000 0.0 35.500000 41.500000 0.0 46.514706 41.500000 0.0 46.514706 41.500000 0.0 35.500000 41.500000 0.0 43.000000 36.000000 0.0 49.588234 36.000000 0.0 49.588234 36.000000 0.0 43.000000 36.000000 0.0 12.000000 25.000000 0.0 55.735294 25.000000 0.0 44.000000 46.000000 0.0 44.000000 46.000000 0.0 47.352940 40.000000 0.0 55.000000 40.000000 0.0 55.000000 40.000000 0.0 47.352940 40.000000 0.0 52.941177 30.000000 0.0 85.000000 30.000000 0.0 94.818184 30.000000 0.0 52.941177 30.000000 0.0 54.897057 26.500000 0.0 93.863640 26.500000 0.0 72.500000 26.500000 0.0 54.897057 26.500000 0.0 62.301468 13.250000 0.0 76.750000 13.250000 0.0 76.750000 13.250000 0.0 62.301468 13.250000 0.0 63.000000 12.000000 0.0 76.333336 12.000000 0.0 76.333336 12.000000 0.0 63.000000 12.000000 0.0 65.400002 8.000000 0.0 75.000000 8.000000 0.0 75.000000 8.000000 0.0 65.400002 8.000000 0.0 69.000000 2.000000 0.0 69.000000 2.000000 0.0 72.500000 26.500000 0.0 72.500000 26.500000 0.0 76.750000 13.250000 0.0 82.052322 13.250000 0.0 82.052322 13.250000 0.0 76.750000 13.250000 0.0 75.000000 8.000000 0.0 85.837212 8.000000 0.0 85.837212 8.000000 0.0 75.000000 8.000000 0.0 72.000000 5.000000 0.0 88.000000 5.000000 0.0 96.500000 5.000000 0.0 72.000000 5.000000 0.0 69.000000 2.000000 0.0 96.500000 2.000000 0.0 93.863640 26.500000 0.0 72.500000 26.500000 0.0 88.000000 5.000000 0.0 88.000000 5.000000 0.0 53.592594 46.000000 0.0 44.000000 46.000000 0.0 55.000000 40.000000 0.0 65.370369 40.000000 0.0 65.370369 40.000000 0.0 55.000000 40.000000 0.0 85.000000 30.000000 0.0 85.000000 30.000000 0.0 51.259262 70.500000 0.0 5.500000 70.500000 0.0 41.814816 52.000000 0.0 91.000000 52.000000 0.0 91.000000 52.000000 0.0 41.814816 52.000000 0.0 80.092590 32.500000 0.0 95.500000 32.500000 0.0 95.500000 32.500000 0.0 80.092590 32.500000 0.0 85.000000 30.000000 0.0 94.818184 30.000000 0.0 96.500000 82.000000 0.0 1.000000 82.000000 0.0 33.000000 79.000000 0.0 96.500000 79.000000 0.0 96.500000 79.000000 0.0 33.000000 79.000000 0.0 91.000000 52.000000 0.0 96.500000 52.000000 0.0 96.500000 52.000000 0.0 91.000000 52.000000 0.0 95.500000 32.500000 0.0 96.500000 32.500000 0.0 96.500000 32.500000 0.0 95.500000 32.500000 0.0 88.000000 5.000000 0.0 96.500000 5.000000 0.0 decomposition: 1.000000 82.000000 0.0 1.000000 82.000000 0.0 -2.348548 79.000000 0.0 33.000000 79.000000 0.0 33.000000 79.000000 0.0 -2.348548 79.000000 0.0 -11.836100 70.500000 0.0 51.259262 70.500000 0.0 5.500000 70.500000 0.0 -11.836100 70.500000 0.0 -29.136929 55.000000 0.0 34.000000 55.000000 0.0 34.000000 55.000000 0.0 -29.136929 55.000000 0.0 -44.205395 41.500000 0.0 35.500000 41.500000 0.0 35.500000 41.500000 0.0 -44.205395 41.500000 0.0 -50.344398 36.000000 0.0 43.000000 36.000000 0.0 43.000000 36.000000 0.0 -50.344398 36.000000 0.0 -53.134853 33.500000 0.0 35.954544 33.500000 0.0 -41.500000 33.500000 0.0 -53.134853 33.500000 0.0 -66.250000 21.750000 0.0 -66.250000 21.750000 0.0 35.954544 33.500000 0.0 -41.500000 33.500000 0.0 12.000000 25.000000 0.0 12.000000 25.000000 0.0 51.259262 70.500000 0.0 5.500000 70.500000 0.0 41.814816 52.000000 0.0 91.000000 52.000000 0.0 91.000000 52.000000 0.0 41.814816 52.000000 0.0 80.092590 32.500000 0.0 95.500000 32.500000 0.0 95.500000 32.500000 0.0 80.092590 32.500000 0.0 85.000000 30.000000 0.0 94.818184 30.000000 0.0 94.818184 30.000000 0.0 52.941177 30.000000 0.0 54.897057 26.500000 0.0 93.863640 26.500000 0.0 72.500000 26.500000 0.0 54.897057 26.500000 0.0 62.301468 13.250000 0.0 76.750000 13.250000 0.0 76.750000 13.250000 0.0 62.301468 13.250000 0.0 63.000000 12.000000 0.0 76.333336 12.000000 0.0 76.333336 12.000000 0.0 63.000000 12.000000 0.0 65.400002 8.000000 0.0 75.000000 8.000000 0.0 75.000000 8.000000 0.0 65.400002 8.000000 0.0 69.000000 2.000000 0.0 69.000000 2.000000 0.0 93.863640 26.500000 0.0 72.500000 26.500000 0.0 88.000000 5.000000 0.0 88.000000 5.000000 0.0 55.000000 40.000000 0.0 47.352940 40.000000 0.0 52.941177 30.000000 0.0 85.000000 30.000000 0.0 44.000000 46.000000 0.0 44.000000 46.000000 0.0 47.352940 40.000000 0.0 55.000000 40.000000 0.0