geometry - Sweep Line Polygon triangulation: How to find edge left to current vertex?

Question

I'm currently writing an y-monotone sweep line algorithm to triangulate non-convex polygons. The first step to achieve this is to make the polygon y-monotone.

Pseudocode of MakeMonotone from the book "Computation Geometry by Mark de Berg" (https://archive.org/details/computationalgeo00berg):

Now to my question:

In that book and all other websites I found, there is no explanation how to exactly sort the edges in the mentioned "binary search tree T". The only thing mentioned in the referenced book is "The left-to-right order of the leaves of T corresponds to the left-to-right order of the edges". But by what properties/attributes the edges are ordered in that tree? It's also unclear to me, how exactly an edge should be represented in the binary tree (start point? end point? combination of both?).

My most naive approach would be to find out for all edges in T the intersection with the sweep and line and the calculate which of them is closest to the current verex. But given that in every book/university slides, the inner working of T is not explained further, it must be way easier.

The binary search tree should support the following operations:

• insert a new edge
• find edge to the left of the vertex currently on the sweep line
• remove an edge

标签： geometrypolygoncomputational-geometrytriangulationnon-convex

Answer 1

T is used to find the edge directly to the left of a query point. So the edges in T need to be horizontally sorted.

The key query on T is to find the edge immediately to the left of a point. For any edge in the tree, find the edge's x-position corresponding to the y-coordinate of the point, and compare it to the x-coordinate of the point. (Alternatively, since only left-bounding edges are stored in the tree, you can just directly evaluate the edge's implicit equation on the coordinates of the point and see if the result is negative or positive.)

In that algorithm, an insertion into T is done by performing such a query and then inserting the new edge directly after the query-returned edge.

In contrast to most other usages of binary trees, there's no way to associate a numeric "key" with each node and sort by the key. If you want an immutable function which you can use to sort, you can do something like this:

def less(e1, e2):
    yMin = max(e1.begin.y, e2.begin.y)
    yMax = min(e1.end.y, e2.end.y)
    y = (yMin + yMax) / 2
    return e1.xAtY(y) < e2.xAtY(y)

That relies on the fact that the edges in this algorithm are known to be non-intersecting, and the fact that the comparison is only used when both edges are active; it is not an ordering over all edges, only over all edges which are active at a particular y.

That's a hack, though. The efficient and correct approach here is to not have a sort function on edges, just a function which compares a vertex to an edge.