Re: Polygon filling? Winding rule?

Bint wrote:
> >> there's two types:
> >>
> >> Non-zero winding rule:
> >> Start with 0 on the left, Add up 1 when crossing an edge that
> >> goes up,substract 1 when crossing an edge that goes down.
> >> Whenever the result equals 0 you fill the interior up till the
> >> next edge.
....
>
> Thanks! How can I tell if the edge is going up or down? Just a
> simple comparison of the start and end y value? Do you ignore
> horizontals?

In brief, yes and yes. But "up" and "down" don't express the idea
correctly. The idea is to count the number of edges a ray crosses.
If the ray is drawn horizontally (as this poster assumes), then the
incident edge's orientation can be called "up" or "down", but what
you're really testing is whether the edge is drawn from "left-to-
right" or "right-to-left" relative to the direction of the ray.

Now, as for whether an edge crosses an arbitrary ray from "left-to-
right" or "right-to-left", that's defined by the edge's orientation
(as the polygon is drawn).

The test of orientation (relative to that arbitrary ray) is the
signed area of the triangle formed by the test point ("a") and the
endpoints of the edge ("b" and "c", as they're oriented within the
polygon; i.e., b = vrtx; c = vrtx->next;):

double AreaTri2d(point *a, point *b, point *c)
{
return (double) (b->x - a->x) * (c->y - a->y) -
(double) (c->x - a->x) * (b->y - a->y);
}

If the return value > 0, the edge crosses the ray right-to-left.

Else if return value < 0, the edge crosses the ray left-to-right.

Else (the return value == zero), the three points are colinear and
thus this edge is coincident with the ray. If the edge and ray are
coincident, then simply ignore this edge since the change of
winding value is determined by the previous and next edges of the
polygon.

But things ARE simpler if the ray is horizontal (or "vertical" as
below):

/*****************************************************************************
FUNCTION : int CPolygon::Winding(Pnt2dl *p)
INPUTS : Point being tested if within polygon.
OUTPUT : Returns winding value.
PURPOSE : Determine if the point is within the polygon.
*****************************************************************************/
int CPolygon::Winding(Pnt2dl *p)
{
int winding = 0;

assert(vrtx0);
Vrtx *tmpV = vrtx0;
do
{
winding += CrossRay(p, tmpV);
tmpV = tmpV->next;
} while (tmpV != vrtx0);

return winding;
}



/*****************************************************************************
FUNCTION : int CPolygon::CrossRay(Pnt2dl *p, Vrtx *v)
INPUTS : Point and the current polygon edge.
OUTPUT : Returns the increment/decrement value
PURPOSE : Determine if the point is a "crossing" of this edge.
*****************************************************************************/
int CPolygon::CrossRay(Pnt2dl *p, Vrtx *v)
{
if ((v->x <= p->x) && (p->x < v->next->x))
{
if ((p->y < v->y) && (p->y < v->next->y))
return 1;
double a = (double)(v->y - v->next->y) / (v->x - v->next->x);
double projY = a * (p->x - v->x);
if ((p->y - v->y) < projY)
return 1;
if ((p->y - v->y) == projY)
{
(p->y)--; // "Wiggle" point 1 foot south
return CrossRay(p, v); // One recursion assured
}
}
else if ((v->next->x <= p->x) && (p->x < v->x))
{
if ((p->y < v->y) && (p->y < v->next->y))
return -1;
double a = (double)(v->y - v->next->y) / (v->x - v->next->x);
double projY = a * (p->x - v->x);
if ((p->y - v->y) < projY)
return -1;
if ((p->y - v->y) == projY)
{
(p->y)--; // "Wiggle" point 1 foot south
return CrossRay(p, v); // One recursion assured
}
}
return 0;
}

Bob

.

Loading