Determining If a Given Point Lies inside a PolygonDate: 12/27/2005 at 05:55:30 From: Kapil Subject: Point in polygon or not I have a finite number of points that constitute a polygon, and a point p(x,y). I want to know if point p lies inside the polygon. Date: 12/27/2005 at 10:29:16 From: Doctor Floor Subject: Re: Point in polygon or not Hi, Kapil, Thanks for your question. You will need to have formulas for the sides, something like: y = 2x + 4 from starting point (1,6) to endpoint (3,10). This is because points alone are not enough to define a polygon. See for instance this polygon: +-------+ | | | | | | | + | | / \ | | / \ | |/ \| + + which has the same vertices as, but is a different polygon from: +-------+ \ | \ | \ | + | / | / | / | +-------+ Provided that you have the formulae for the sides, make the formula for a line p(x,y) that does not pass through one of the vertices (points) of the polygon. Intersect this line with all sides. Count the number of intersections (only if they are between the starting point and endpoint of the sides!) on the left hand side and right hand side of p. If they are both even: p is outside of the polygon both odd: p is inside of the polygon Do you see why this is true? Examples: BOTH SIDES ODD \ / +\-------/-----------------+ / \ / / / \ / / / \ / / ------------p---------------------- / / \ / / / \ / +-------/-----\-----------+ / \ BOTH SIDES EVEN _.-' +_.-'---------------------+ _.-' / \ _.-' / / --p------------------------------------------ \ / / \/ / /\ / +--\----------------------+ \ If you have more questions, just write back. Best regards, - Doctor Floor, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/