1
$\begingroup$

How to check if a given point lies inside or outside a polygon with holes?

Does the below algorithm works for polygon with holes?

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

$\endgroup$
1
$\begingroup$

Yes, basically.

That algorithm is called ray casting algorithm, also known as the crossing number algorithm or the even–odd rule algorithm.

Why is it correct? "The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two 'border crossings' the moving point goes outside. This observation may be mathematically proved using the Jordan curve theorem." Note this reasoning works in all basic situations, whether the polygon is convex or not and whether the polygon has holes or not.

However, you should be aware of the degenerate cases as well as the case of a hole inside a hole. For an example of degenerate case, consider a degenerated polygon that are two triangles intersecting only on their only common vertex. Then the algorithm may fail when the ray goes through that common vertex. For the case of a hole inside a hole, you have to define the area inside the smaller area is inside the polygon so as to not invalidate the algorithm.

It is actually not easy to make a rigorous statement mathematically about the general situations when the ray casting algorithm works. For this particular question, let me just say the ray casting algorithm will work for a polygon with separate polygon holes inside it where all line segments of the outer polygon and inner polygons do not intersect each other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.