How do you find out if the polygon lies to the right of a regular vertex?
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} &lt; 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-&gt;tail == this */
    double x, y;
};

bool polygon_isleftof(half_edge *he) {
  return he-&gt;next-&gt;tail-&gt;y &gt; he-&gt;tail-&gt;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-&gt;rep;
    //loop over all half-edges with tail equal to v:
    do {
        if (walk-&gt;left == f) break; //exit the loop if we find a half-edge incident f
        walk = walk-&gt;twin-&gt;next; 
    } while (walk != v-&gt;rep);

    //If we didn't find a half-edge incident f and v, then return false:
    if (walk-&gt;left != f) { 
        return false; 
    } else {
        return walk-&gt;next-&gt;tail-&gt;y &gt; walk-&gt;tail-&gt;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.