🚀 go-pugleaf

In article <1992Aug25.195204.28914@eng.ufl.edu> Ed Deeters:
> Hi, does anyone know a fast way to determine if a point(x,y) is inside
> or outside of a polygon when the polygon is defined by n points(x,y)
> given in a clockwise manner?

If the polygon is convex, or if you are trying to check if the given
point is inside the convex hull of the given points then you can use
linear programming to do so.
Assume that the coordinates of point i are given by the vector x(i)
then the formulation would be:
x = c(i) * x(i)
sum_i c(i) = 1
c(i) >= 0

x is the coordinate vector of the point you are trying to see whether
it is inside or outside the polygon. c(i) is the unknown. Use linear
programming to see if the problem has a feasible solution or not.
-Samer

I acknowledge my error the polygon must be convex for my 
suggestion to work.

Patrick

In article <1992Sep9.141511.23893@dutrun2.tudelft.nl>, rcpshdb@dutrun2.tudelft.nl (Han de Bruijn) writes:
|> In article <1992Aug25.195204.28914@eng.ufl.edu> Ed Deeters:
|> > Hi, does anyone know a fast way to determine if a point(x,y) is inside
|> > or outside of a polygon when the polygon is defined by n points(x,y) 
|> > given in a clockwise manner?
|> 
|> [.....]
|> 
|> What do you want? In-out algorithms are _either_ fast XOR reliable!
|> 
|> [.....]
|> 
|> Reliable algorithm (NOT cheap):
|> ------------------
|> Instead, determine the _angle_ between ai and bi (: quite expensive!).
|> The sum of all these angles (FOR i=1 to N-1) divided by  2.pi  equals
|> the so called "winding number" for  p . If the winding number is < 0.5
|> then  p  is outside the polygon. The higher the point's winding number,
|> the more it is enclosed by the polygon.

According to conventional wisdom the ray crossing method (see Preparata
and Shamos for the general idea) is faster (I've never checked this myself)
and is also reliable. The details of the special cases can be a little messy
but there is a trick, which I don't remember right now, which makes for clean,
fast, reliable code (if you are desperate, e-mail me and I'll take a look at
the code to refresh my memory). This should be in the FAQ(s) since this is
asked every month or two.

Larry Edwards
edwards@sunrise.stanford.edu

In article <1992Sep9.141511.23893@dutrun2.tudelft.nl> rcpshdb@dutrun2.tudelft.nl (Han de Bruijn) writes:
> In article <1992Aug25.195204.28914@eng.ufl.edu> Ed Deeters:
>> Hi, does anyone know a fast way to determine if a point(x,y) is inside
>> or outside of a polygon when the polygon is defined by n points(x,y) 
>> given in a clockwise manner?

> [...] determine the _angle_ between ai and bi (: quite expensive!).
> The sum of all these angles (FOR i=1 to N-1) divided by  2.pi  equals
> the so called "winding number" for  p . If the winding number is < 0.5
> then  p  is outside the polygon. The higher the point's winding number,
> the more it is enclosed by the polygon.

The simplest algorithm (and easiest to believe in, at least for me)
is to shoot a ray in an arbitrary direction from your point and
count the number of polygon edges you cross.

Exactly what you do with your count depends on how you want to treat
self-intersecting polygons.  If you use the even/odd rule (the polygon
cancels out XOR-fashion when it intersects itself) then you're inside
the polygon if and only if you cross an odd number of edges.  If you
use the winding-number rule (inside a self-intersecting part still
counts as inside), then count +1 for every edge that crosses going
to the right (as viewed by the ray) and -1 for every edge that crosses
going to the left; you're inside if the final count is nonzero.  It
doesn't matter which way you go around the polygon, since if you get
left and right backwards the final nonzero-ness test comes out the
same.

If you don't expect to have self-intersections, then the even/odd test
will do the job and is probably simpler.

Since this works for rays in any direction, you can choose one
of the four directions that parallel the x or y axes.  For these
directions, the math for the intersection test becomes extremely
simple and fast.

The only tricky part is, what happens if your ray goes exactly
*through* one of the points in the polygon?  There are two answers:
Either refine your test to take care of all the various tricky cases
that can arise here, or, more simply, choose another ray and hope
for better luck.  After all, if you have a finite number of points
in your polygon, there must be *some* direction you can go and not
intersect any point.

It might be easiest to try, say, east- and north-going rays in turn;
if both run into trouble, use the much slower angle-oriented test
that Han de Bruijn describes.  All these tests are quite simple to
code, and Han's computation-intensive test will only rarely need to
be used.  In C, the "atan2" library function does most of the work
of Han's test.

If for some reason Han's test is not practical, then I'd suggest
trying rays in easy directions, then in random hard directions
until you find a case where you don't run into any vertices.  The
intersection test is trickier for arbitrary rays, though, and
roundoff issues make the question of when you've hit a vertex
somewhat less clear-cut.  Another problem with trying random
directions is that there is no guaranteed upper bound on the
amount of time the algorithm takes.

								-- Dave
--
Dave Gillespie
  daveg@synaptics.com, uunet!synaptx!daveg
  or: daveg@csvax.cs.caltech.edu

pa@verano.sba.ca.us (Pierre Asselin) writes:
>In <Jmv-D2=@engin.umich.edu> takriti@engin.umich.edu (samer Takriti) writes:
>
>>Linear programming does that very simply.
>[Linear program deleted]
>
>Only for convex polygons.  Your LP determins whether the point is
>interior to the convex hull of the polygon, not the polygon itself.

Right, and if you do have the convex polygon with vertices in sorted order,
you can use binary search (assuming constant access time, i.e. not a linked
list) to determine point inclusion in O(log N) time...That has to beat solving
for the convex combination of the vertices with a simple application of linear
programming...

-- 
 -- Erick, the perfect square  :-)