1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

Left: $v_{i-1}$ is below $v_i$ so $P$ is on left. Right: $v_{i-1}$ is above $v_i$ so $P$ is on right.

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.