OJ Board

Posted: **Sun May 28, 2006 9:55 am**

Hi,

how can i test a point is inside a regular polygon or not?

i was trying to think this way:

#take a random point far away
#make a line with the test point and this random point
#check for intersection between this line and all the edges and count it
#if the count is odd then the point is inside otherwise outside

but i got stuck in the case where my test line will intersect in any of the
vertex of the polygon, now how can i know where the point is?

can anyone help me from here? thanks...

Posted: **Sun May 28, 2006 10:16 am**

You can use the 'winding number' method, which is described here http://softsurfer.com/Archive/algorithm ... m_0103.htm.
This is a great site for other geometry algorithms too.

Posted: **Sun May 28, 2006 10:32 am**

Well, when you go through edges, if they are (p1,p2), you can do >p1, <=p2, that way you count the vertex only once? In other words, consider an edge as a half-open interval (p1,p2] (or something like that)

Posted: **Sun May 28, 2006 9:35 pm**

Hi, little joey and Darko , thanks for the reply.

ya, the link is rich and i hope my problem will be fixed from there.

Well, when you go through edges, if they are (p1,p2), you can do >p1, <=p2, that way you count the vertex only once? In other words, consider an edge as a half-open interval (p1,p2] (or something like that)

well Darko, i thought about that one, but what if the point is outside the polygon? then odd count means it is inside the polygon, isn't it?

Code: Select all


polygon : (0, 0), (10, 0), (10, 10), (0, 10)
test point 1: (10, -10)  and unfortunately if i pick another random point    (-10, 10)   

test point 2: (5,5) and unfortuantely this time my random point is (1000,1000)

Posted: **Tue May 30, 2006 7:47 am**

You can ignore "bad" random points and wait for a "good" one.

Posted: **Tue May 30, 2006 12:31 pm**

http://www.exaflop.org/docs/cgafaq/cga2.html
(no special cases)

OJ Board

Help on testing point inside a polygon

Help on testing point inside a polygon