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?