Mail Archives: djgpp/1998/03/27/17:45:56
Steve Patton (leaphe AT pemail DOT net) wrote:
: Is there a quick easy way to detect whether a point lies within the
: boundaries of a 2d polygon? Right now I'm dealing with a four sided
: polygon. This shape could be a rectangle (at any rotation angle, or
: distortion), trapazoid, etc, any 4 sided polygon. This has to be checked a
: LOT, so I would appreciate an efficient algorithm. Source code is not
: neccessary, if you can give me an idea, I can run with it. Thanks!
Yes, there is a fast and even elegant method for this. Let Q be the
point possibly within the polygon, and P1, ..., PN the vertices of the
polygon. Let Qx be the ray (half line) extending from the point Q
to infinity in the direction of the positive X axis (or any other
direction). For each side of the polygon P1-P2, P2-P3, ... P(N-1)-PN,
PN-P1, determine whether that side misses Qx, passes through it going
upwards, or passes through it going downwards. Assign the values
0, +1, -1 to each of these cases and add up the values obtained for
each side. If the sum is zero, Q is outside the polygon. If it is
negative, the polygon surrounds Q in a clockwise direction; if positive,
the polygon surrounds Q counterclockwise. There are various special
cases to consider: A side may intersect Q. The polygon may wind around
Q more than once. By the way, that number that you've computed is
known as the winding number. For more details, see a book on
computer graphics, where point/polygon problems are often treated in
detail.
Paul Hughett
- Raw text -