How do you find out if the polygon lies to the right of a regular vertex?

Question

In section 3.2 of the book Computational Geometry: Algorithms and Applications (by Berg et al.), the authors describe a procedure to make a polygon y-monotone. The algorithm distinguishes vertices into $5$ different types: "start", "end", "regular", "split" and "merge" vertices.

A regular vertex is a vertex which has one of its neighboring vertices above it, and the other neighbor below it. A regular vertex can be on the left or right chain of the polygon.

Given a regular vertex $v$, how do I find out if the polygon lies to the right or left of $v$?

The polygon is stored in a doubly-connected edge list. The vertices have coordinates and are stored in a normal DCEL data structure along with the half-edges and polygons. It seems reasonable to expect an elegant solution that uses the DCEL.

Answer 1

I'm going to assume that your DCEL is counter-clockwise (ccw) oriented, meaning that if we traverse the list of half-edges incident the polygon's interior in order we make a counter-clockwise walk of the polygon. (This is standard.)

Let $v_i$ be your vertex, from the DCEL you can easily obtain $v_{i-1}$ and $v_{i+1}$, the vertices immediately preceding and following (resp.) $v_i$ in the ccw walk of the polygon. (The DCEL will have an edge $e_{i-1}$ with target $v_i$ and an edge $e_{i}$ with source $v_i$ both incident to the polygon $P$, and that $source(e_{i-1}) = v_{i-1}$ and $target(e_i) = v_{i+1}$.)

If $v_{i-1}$ is below $v_i$ (and $v_{i+1}$ is above $v_i$) then $P$ is to the left of $v_i$. Otherwise it is to the right. You can see this by drawing out the two possible cases. The point is that locally as you travel from $v_{i-1}$ to $v_{i+1}$ the polygon is on your left, so if you are traveling from a vertex above $v_i$ to a vertex below it, in your view the polygon is on your left, but in the "global" view, the polygon is on the right. However, if you are traveling from a vertex below $v_i$ to a vertex above it, then your view and the local view both have the polygon on the left. And by the definition of a regular vertex, those are the only two things we need to check.

Of course since you already know that one of $v_{i-1}$, $v_{i+1}$ is above and the other is below you only need to check for one. Something like, if $v_{i-1,x} < v_{i,x}$ then $P$ is left, otherwise right.

Here is a sketch:

I saw the code base you are using in your other posting on DCELs, so here is the code version:

First you will need to augment your vertex data structure to have fields for x and y:

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
    double x, y;
};

bool polygon_isleftof(half_edge *he) {
  return he->next->tail->y > he->tail->y;
}

By the way, when dealing with DCELs I have found that for many applications it is best to work with half-edges directly rather than vertices (in other words, if you want to pass a vertex to a function, just pass one of the half-edges for which it is a tail/source). That way you get two pieces of information: 1.) the vertex you are interested in and 2.) the face your are interested in. So in the code above my polygon_isleftof tells you whether the vertex which is the tail of he is to the right of the face which is incident to he. If I instead passed a vertex and a face the code would be much slower:

bool polygon_isleftof_slow(vertex *v, face *f) {
    //first we need to find a half-edge incident both f and v
    half_edge *walk = v->rep;
    //loop over all half-edges with tail equal to v:
    do {
        if (walk->left == f) break; //exit the loop if we find a half-edge incident f
        walk = walk->twin->next; 
    } while (walk != v->rep);

    //If we didn't find a half-edge incident f and v, then return false:
    if (walk->left != f) { 
        return false; 
    } else {
        return walk->next->tail->y > walk->tail->y;
    }
}

Notice that in the first case, polygon_isleftof is $O(1)$ whereas in the second case polygon_isleftof_slow is $O(n)$. And since you are probably traversing the polygon using half-edges anyway, there is no reason not to just operate on half-edges and only access the vertices as needed in functions.