Jump to content
  • Advertisement
Sign in to follow this  
coolkehon

Determining if a point is inside of a polygon

This topic is 3262 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

This topic is 3262 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!