# 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.

## 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 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 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 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.

This topic is now closed to further replies.

1. 1
Rutin
25
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 14
• 11
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
631754
• Total Posts
3002104
×