[Solved]: How do you find out with a DCEL if the face is to the right of a vertex?

Problem Detail: 

I would like to find for any given vertex in a polygon stored in a doubly-connected edge list if the polygon is to its right or not. How do I do that without having a bunch of nested if statements?

It seems reasonable to expect a more elegant solution that uses the DCEL.

Thank you.

EDIT: the vertices have coordinates and are stored in a normal DCEL data structure along with the half edges and polygons.

Asked By : Sioma Dukh

Answered By : jcb

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18092

 Ask a Question

 Download Related Notes/Documents