The algorithm to partition a polygon into y-monotone pieces is as follows:
Input. A simple polygon P stored in a doubly-connected edge list D Output. A partitioning of P into monotone subpolygons, stored in D Process: 1. Construct a priority queue Q on the vertices of P ,use y- coordinates to determine priority.If two points have the same y- coordinate, the one with smaller x-coordinate has higher priority. 2. Initialize an empty binary search tree T 3. While Q is not empty Do 4. remove the vertex vi with the highest priority from Q 5. call the appropriate procedure to handle the vertex, depending on the type of the vertex 6. End Do
An Example process of handling a vertex if it is a merge vertex will be as follows:
HandleMergeVertex(Vi): 1. If helper(ei−1) is a merge vertex 2. insert the diagonal connecting vi to helper(ei−1) in D 3. delete ei−1 from T 4. search in T to find the edge ej directly left of vi 5. If helper(ej) is a merge vertex 6. Insert the diagonal connecting vi to helper(ej) in D 7. helper(ej) = vi
Now in DeBerg's book of computational geometry , he quoted as:
In the approach above, we need to find the edge to the left of each vertex. Therefore we store the edges of P intersecting the sweep line in the leaves of a dynamic binary search tree T. The left-to-right order of the leaves of T corresponds to the left-to-right order of the edges. Because we are only interested in edges to the left of split and merge vertices we only need to store edges in T that have the interior of P to their right. With each edge in T we store its helper. The tree T and the helpers stored with the edges form the status of the sweep line algorithm. The status changes as the sweep line moves: edges start or stop intersecting the sweep line, and the helper of an edge may be replaced
Now my question would be , what is the key of this BST T ? Is it the vertex in consideration , is it the edge ? And how to determine what is the edge at the left of an vertex?