1
$\begingroup$

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?

$\endgroup$

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.