Re: Clicks inside a polygon

Jean-Francois Groff (jfg@infodesign.ch)
Thu, 11 Nov 93 01:27:48 +0100


>>> On Tue, November 9, Ari Luotonen said:
>
> Is there a public domain implementation of resolving if a point
> is inside or outside of a polygon such that it could be part of
> the CERN daemon distribution.

Here is the algorithm used by PostScript, which is to my knowledge
the best combination of reliability and ease of coding :

From the point to test, draw a line in any direction. Count the
times the path of the shape crosses this line. Add 1 each time the
path crosses your line from left to right, substract 1 each time it
crosses it from right to left. If the result is non-zero, the point is
inside the path. If a path segment happens to be tangent or colinear
to your test line, change the direction of that line and try again.

This algorithm works for any kind of shape, not just polygons, and
even if the drawing path crosses itself (e.g. when you draw a 5-branch
star in one stroke with just five lines). With doughnut-like shapes,
points inside the doughnut hole are considered outside the doughnut
iff the interior path is drawn in the opposite direction of the
exterior path. For more details, read the Postscript Reference Manual
(a.k.a. Red Book), second edition, section 4.5.2. "Filling".

In the case of polygons, I can implement it for you if you like, as
I already have routines to check line intersections.

Till later...

Jean-Francois