🚀 go-pugleaf

In article <70n516$31l$1@news01.btx.dtag.de>,
  einhardschule@t-online.de (Rudolf Polzer) wrote:
> Rich Pasco <pasco@best.com> schrieb im Beitrag <362C91A2.7F40@best.com>...
> > If you define the area as a polygon, then the point is "in" the area
> > if it is on the correct side of each of the sides of the polygon, e.g.
>
> Then the polygon has to be convex.
>
> Example: a concav (or concave?) polygon
>
> +++++    +++++
> +   +    +   +
> +   +    + p +
> +   xxxxxx   +
> +            +
> ++++++++++++++
>
> Now we check if the point p is on the correct side of xxxxxx.
> It isn't, is it?
>
> The point is that your rule doesn't work in a concav polygon, but only in
> convex ones.

I think if you look up Sedgewick's "algorithms" (which is in Pascal) or
"algorithms in c" (a later version, using ---) you will find a positive
algorithm which counts the intersections of the perimeter with a sufficiently
extended line through the point.  That is not quite right, but go look it up.
 I don't have the book handy right now.  The only gotcha is perimeter
intersections that are double valued, i.e. line passing thru a cusp.

--
    Chuck Falconer (Charles_Falconer@NOSPAMapsnet.com)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own