Can someone please explain the Ray-casting algorithm for point in polygon i.e. containment check?

1.1k views Asked by At

Consider a polygon with two loops i.e. Outer loop& inner loop as shown in the images attached with this question(One can think of an English letter "e" for example). Can someone please explain how exactly the Ray-casting algorithm will work in such cases.? If possible, please put some images/drawings in answer, for better visualization and understanding.

Example enter image description here

enter image description here

1

There are 1 answers

4
AudioBubble On

Imagine a point moving from infinity to the target point along a straight line (will also work with a curve).

The point at infinity is outside the shape. Whenever an outline is met, you switch from outside to inside or conversely. This rule defines internal and external points. In the given case, the inside of the rounded rectangle, inner circles excluded.

enter image description here

Algorithmically, you count the intersections of the segments that define the shape with the half-line to the target.