Sign in to follow this  
coolkehon

Determining if a point is inside of a polygon

Recommended Posts

i searched all over google and found a couple of algorithms to determine if a point is inside of a polygon. A lot of them say that it works for a polygon that has holes in it as well. How can i use the formula here http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/ to determine if a point exist in a polygon in c/c++. What I really want is an explanation. Also how can I give it the points for a polygon with holes in it such as this below. http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/insidepoly3.gif http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

Share this post


Link to post
Share on other sites
I'm not sure if this is the simplest answer, so wait for other replies too.

I skimmed the functions you linked to. They take lists (or, arrays really) of vertices, and it looks like most of them assume that consecutive vertices are connected by edges. One thing you could do is to add a pair of edges between the outer polygon's outer boundary and inner hole that "cancel each other out."

Example: Polygon with vertices (say, sorted in CCW order) {p1, p2, p3, p4} and hole inside with vertices {h1, h2, h3}. Combine these into a single polygon {p1, p2, p3, p4, h1, h2, h3, h1, p4}. It will have edges,

p1 -> p2
p2 -> p3
p3 -> p4
p4 -> h1
h1 -> h2
h2 -> h3
h3 -> h1
h1 -> p4
p4 -> p1 (implied that first and last are connected).

Now say you do the odd/even ray test. The bold edge is represented twice, so it will add two to the intersection count, which does not effect whether it is even or odd.

I don't know if this is the "standard" way to do it, but it seems simple enough and only the tiniest bit inefficient (you duplicate two vertices for each hole. Compared to the storage requirements (including pointers) of a more elaborate data structure with separate "holes," etc, I think this is a net win).

See what others have to say too.

Share this post


Link to post
Share on other sites
Please see the link in the Forum FAQ (look for "point in" or "ptinpoly").

This is an extremely common question, answered above and in my prior forum postings. I'm closing the thread. The above should answer the question or you can use the search feature to find past discussions.

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this