From: wilson@web.ctron.com (David Wilson)
Newsgroups: sci.math
Subject: Re: Polygon point enclosure
Date: 1 Sep 92 18:26:25 GMT
Reply-To: wilson@web.ctron.com (David Wilson)
Organization: Cabletron Systems INc.



    Given a point P and polygon POLY in a plane, to determine if the
    point lies inside, outside, or on POLY to within a tolerance TOL.
    The following is a suped-up version of ray-crossing algorithm.

    -------------------------------------------------------------------

    Translate POLY so that P is at the origin, that is, translate POLY
    by -P.

    Let A be the closed halfplane y >= 0, and let B be the open
    halfplane y < 0.  Let PARITY be the parity of the number of times
    POLY crosses from A to B to the right of P.  Initialize PARITY to
    0.

    Loop through each edge E of POLY

	If the origin is within tolerance of E, then the point is
	on POLY, and we are done.*

	If one endpoint of E is in A, and the other is in B, then
	locate the x-intercept of E.  If its x-coordinate is positive,
	complement PARITY (i.e., let PARITY = 1-PARITY).

    end loop

    If PARITY is 0, then the point is outside POLY, if odd,
    the point is inside POLY, and we are done.

    -------------------------------------------------------------------

    Since we count crossings from A to B rather than crossing of the
    positive x-axis, we avoid the messiness associated with polygon
    vertices on the x-axis.

    If you need to determine if the point is on the polygon to within
    tolerance, then most of the work of the algorithm will be done in
    trying to decide if the origin is within tolerance of an edge.
    Preliminary extents checking will reduce the number of times the
    perpendicular distance from the origin to the edge segment need be
    calculated, but this calculation cannot be entirely avoided.  If
    you are not fussy about the polygon vertices, you may use the L1
    norm in lieu of the L2 norm, or omit testing the polygon vertices
    altogether.  Otherwise, you can avoid retesting vertices by
    ordering the edges in polygon order and checking only one vertex
    per edge (the second vertex of that edge will then be the first
    vertex of the next edge, and will be tested in the next loop).

    If you are satisfied with an inside/outside answer, that is, you do
    not care if the point is on the polygon, you can dispense with
    checking the edge against the origin altogether (which means that
    the tolerance is unnecessary).  This is accomplished by omitting
    the line with the asterisk from the above algorithm.  This omission
    results in significant speedup of the loop.

    In higher dimensions, we first test if P is in the plane of the
    polygon to within tolerance.  If not, clearly P is not in the
    polygon.  Otherwise, project both P and the polygon to two
    dimensions and perform the above algorithm on the projected point
    and plane.  Judicious choice of the projection plane, reduces the
    projection to selection of two coordinates from each projected
    point.


-- 
David W. Wilson (wilson@web.ctron.com)

Disclaimer: "Truth is just truth...You can't have opinions about truth."
- Peter Schikele, introduction to P.D.Q. Bach's oratorio "The Seasonings."
Newsgroups: sci.math