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

       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 
       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:

    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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.