Trouble understanding a constant work-space algorithm for trapezoidal decomposition

Question

I'm looking at an algorithm for trapezoidal decomposition of a simple polygon in constant work-space shown in this paper. (page 51, section 3.2).

The idea of the algorithm is to traverse the polygon vertices left to right (as a plane-sweep).

At each point qi they determine whether there is a trapezoid to the right of qi. The first thing that confuses me is the test they use for this determination. They do so using this claim:

At each vertex qi, we check if there is a trapezoid to the right of qi incident to qi. This happens precisely if at least one of the two edges incident to qi has an endpoint to the right of qi.

It makes sense at first, but (from what I can see) the very example they use in the illustration at page 52 contradicts this.

This example is supposed to represent a point qi which has a trapezoid to its right. However, both edges incident to qi do NOT have any endpoints to the right of qi (note that these are not eA and eB, they are displayed for another reason which I'll mention below).

Setting this aside, the second thing that confuses me is finding eA and eB which I noted above. After determining that qi has a trapezoid to its right, the following is stated:

If the test is positive, we first compute two polygon edges: eA just above qi and eB just below qi. This is done by traversing all of P. Here, an edge e is above qi if it intersects the upward vertical ray from qi, or, in case that e is incident to qi, if e has an endpoint to the right of qi and the interior of the polygon lies below e. An edge e being below qi is defined analogously.

The first case here is clear to me, we can easily check if an edge is above qi by intersecting a vertical line defined by qi and the edge itself, and then taking the edge which minimizes the y-value of the intersection. What's a little unclear is the special case with the incident edges:

in case that e is incident to qi, if e has an endpoint to the right of qi and the interior of the polygon lies below e.

How would it be possible for e not to have an endpoint to the right of qi, because had that been false, the initial test of whether we would consider qi would have failed. A followup question - how would we check whether the interior of the polygon lies below the edge?

Thanks in advance.

EDIT: More info about the follow-up question of "how would we check whether the interior of the polygon lies below the edge?". Thanks to @didc I've fixed the first part of my algorithm, but I'm having some issues with this one. Namely the question of "does the interior of the polygon lie above or below a certain edge" does not seem easy to answer at all? If the edge we're looking at is e=p1,p2, checking orientations of triples (p1, p2, qi) or (p1, p2, p3) where p3 is the next point in order seems pointless, also I've tried some cross-product magic which didn't work and some line-equation magic as well. Any ideas here?

Answer 1

My intuition is that the confusion partially comes from the overloaded meaning of qi, which represents both the vertex and the vertical line (or segment denoted by its endpoints eA and eB). If you think of qi as the vertical line in certain sentences of the algorithm description, then the incident (word which is usually not used for dimensionless objects like points) lines to qi are indeed those overdrawn in blue, rather than those on the left side of the qi vertex.

The second part uses the wording "incident to qi" which should probably be read ""incident to [the vertical line passing through qi on] qi".

As for determining if the trapezoid is above or below on of its vertex, I guess it should be easy enough to check if one of the edges (e in this case) it belongs to is above or below, which could be done by checking the position of any other vertex of the trapezoid not on e relatively to the line the edge e lies over:

• compute the equation of the line supporting e, based on qi and the other vertex of e,

• plug the coordinates of the other endpoint of the other edge qi belongs to (thus eB here), and check the sign of the result.

I'll leave as an exercise to the reader how the sign should be interpreted, depending on the way the line equation has been computed and the orientation of the space basis.