How do you determine if a point is inside a polygon (programmatically)? This is difficult!
Craig Manley
Hello Gurus,
Can anyone explain the working of the "alternating rule" to me so that
I can implement it in some of my none-Java programs. This function is
built in in Java in Java.awt.Polygon.inside. What it does is return true
if a point is inside a polygon else false. Sounds simple but it isn't.
I've tried decompiling the class in question but it is too difficult for
me to decipher the logic in the function because there are for example
"for" loops without bodies, variables that never change value, and
variable names that all look alike. I've tried e-mailing the writer of
this function but the e-mail address doesn't exist anymore.
This is the J++ explanation:
************************************************************************
public boolean inside(int x, int y)
Determines if the specified point is inside this polygon. This method
uses an even-odd insideness rule (also known as an "alternating rule")
to determine whether the point (x,y) is inside this polygon.
It is based on code by Hanpeter van Vliet (hvv...@inter.nl.net).
Parameters:
x - the x coordinate of the point to be tested
y - the y coordinate of the point to be tested
Returns:
true if the point (x,y) is inside this polygon; false otherwise.
************************************************************************
Thanks,
|\
_ \ \
\ \ _\ \__
-------- Craig Manley ----------- /_/\_/ /__>
/ /
|/
E-mail : c.ma...@tip.nl
Homepage: http://www.flnet.nl/~0manley01
http://www1.tip.nl/users/t960341
*---\ ___ _
\ / \ | |
\---| \ / / |
*-------------| *----- /
|----
Wayne Cochran - CS
See FAQ.
-- wayne
Wayne O. Cochran
wcoc...@eecs.wsu.edu
http://www.eecs.wsu.edu/~wcochran
Ecclesiastes 3:11
Mr Jama
The alternating rule means you take the point you are checking and shoot
off a ray in any direction in the plane of the polygon. You then count
the number of times you intersect your polygon. If you intersect an odd
number of times, your inside - intersect an even number - and you're
outside. Try it - its very easy.
The only problems you run into are degenerate cases like having a point
exactly on the polygon or having your ray go through a vertex of the
polygon. None of these problems is too tough to fix however.
Jama
Rarius
Craig Manley <c.ma...@tip.nl> wrote in article <336FA4...@tip.nl>...
> Hello Gurus,
>
> Can anyone explain the working of the "alternating rule" to me so that
> I can implement it in some of my none-Java programs. This function is
> built in in Java in Java.awt.Polygon.inside. What it does is return true
> if a point is inside a polygon else false. Sounds simple but it isn't.
> I've tried decompiling the class in question but it is too difficult for
> me to decipher the logic in the function because there are for example
> "for" loops without bodies, variables that never change value, and
> variable names that all look alike. I've tried e-mailing the writer of
> this function but the e-mail address doesn't exist anymore.
>
> This is the J++ explanation:
> ************************************************************************
> public boolean inside(int x, int y)
>
> Determines if the specified point is inside this polygon. This method
> uses an even-odd insideness rule (also known as an "alternating rule")
> to determine whether the point (x,y) is inside this polygon.
>
> It is based on code by Hanpeter van Vliet (hvv...@inter.nl.net).
>
> Parameters:
>
> x - the x coordinate of the point to be tested
> y - the y coordinate of the point to be tested
>
> Returns:
>
> true if the point (x,y) is inside this polygon; false otherwise.
It would take too long to go into all of the math here, but here's an
outline of how it works.
First you need a point known to be outside the polygon.... first point +
twice maximum height is good.
Next you need a routine to tell if two lines (defined as pairs of points)
cross.
Construct a line (lets call it A) between the point to be tested (x,y) and
the point outside the polygon.
Compare line A with each side of the polygon and count how many edged it
crosses.
If this count is zero or even then the point is outside the polygon, if it
is odd the point must be inside the polygon.
I hope this helps
Rarius