   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 
