| From: | cheila |
| Date: | 5 May 99 at 17:46:58 |
| Subject: | Re: [amos-list] point in polygon |
From: <cheila@saintolaves.demon.co.uk>
Hi
The simplest way to check if a point is in a polygon is to
draw a line (in any direction) from your point to way
outside the shape. If the number of intersections of this
line with edges of the polygon is odd, then you are in
the shape, otherwise outside (mmm, topology...). You
might have to be careful about corners though, you might
slip through a non-existent gap or cross twice because of
rounding errors.
This might be slow, but you could always pick a simple line
(always horizontal, say) and optimise the line intersection
calculation for that (check y bounding box first, and only
one edge of x box).
I did read a good book on it ages ago, with all the algorithms
you would ever need (including line drawing, polygon filling,
drawing circles, splines, and other mad stuff in 2d and 3d),
I think it was called Fundamentals of Interactive Computer
Graphics but I'm not sure.
Incidentally, are you using integers or floats? I'm not too
good at using integers (need to many "tricks"), but floats
are slow.
Claude
------------------------------------------------------------------------
Join the Star Wars craze!
http://www.onelist.com
Set up your Star Wars list at ONElist.
------------------------------------------------------------------------
Official AMOS WWW: http://members.xoom.com/AmosFactory/front.html