Figure 2. point-in-poly tests
Input is a contour based description of a multi-island polygon with holes and a virtual point (VP), all in 2d space with integer coordinates. The virtual point is infinitely close, but is shifted a tiny bit left and up or down from RP; RP is a point specified by integer coordinates RPx and RPy. The location of VP relative to RP is specified by an input direction vector, whose scale is ignored but angle is used.
The output is a boolean value that is true if VP is in a solid ("filled") portion of the input polygon.
The algorithm casts an infinite horizontal ray from RP to the right and counts how many edge segments of the polygon it would hit if it was cast from VP.
Set up a counter CNT with initial value 0. In arbitrary order take each contour segment SEG the ray intersects and:
Note: orientation of SEG or whether it's a polygon hole or outer contour does not matter; it is assumed there are no overlapping segments or odd stubs and there are no zero length segments. There are no open loops in the input.
Note: the ray is traveling on a non-integer y coordinate (topologically speaking) so it never actually hits a vertex, only SEGs, sometimes very close to their endpoints.
After dealing with all intersection the result is:
Note: in practice this test is ran on a rightmost point of a polybool2 face contour with a direction vector pointing inside the face.
Note: value 0 is considered an even number.
On the figure below, the integer coordinate grid is drawn with thin black lines and an input polygon with a single hole is drawn in red. Straight line segments making up the outer contours and hole contours are labeled with green integers. Test RPs are marked with blue crosses and are labeled from A..J.
From RP 'A', with a direction vector pointing up-left 45 degrees: RP falls on the endpoint of segment 0 and 1. Segment 0 is ignored because of [H2.1] (segment going down from RP, direction pointing up). Segment 1 increases CNT because of [H2.2] as the end of the upward pointing direction vector is left of it. Then the ray is crossing edges 2 and 4 in the middle, each increasing CNT because of [H3]. CNT is 0+1+1+1=3 at the end. 3 is odd, VP (the point very close to but up-left of 'A') is inside the solid of the red polygon.
From RP 'B' with a direction vector pointing up-left 45 degrees: RP is at the shared endpoint of 1 and 2. They are both ignored because of [H2.1]: (SEGs are pointing downward, dir vector upward). Then the ray crosses 4 in the middle so CNT is increased according to [H3]. CNT is 0+0+1=1 at the end. 1 is odd, VP (the point very close to but up-left of 'B') is inside the solid of the red polygon.
From RP 'B' with a direction vector pointing down-left 45 degrees:
Resulting CNT is 2, even: VP down-left of 'B' is outside of the solid red (sitting in the hole).
From RP 'C' dir pointing left-up or left-down: RP is not on any vertex; ray hits midpoint 2 (CNT++) then midpoint 4 (CNT++); Final CNT is 2 which is even: VP is outside (as it is sitting in a hole).
From RP 'D' dir pointing left-up:
Resulting CNT is 2, even: VP left-up of 'D' is outside of the solid red (sitting in the hole).
From RP 'D' dir pointing left-down: same as the previous example, except seg 2 is ignored and seg 3 is intersected because the ray is now a tiny bit under their shared vertex. Same result.
From RP 'F', dir left-up or left-down: RP is not on a vertex; normal [H3] mid-crossing for seg 7 and 10; resulting CNT is 2, even, VP is outside (sitting in the hole on the left side of seg 7).
From RP 'G' dir pointing up-left:
Resulting CNT is 3, VP is in solid red.
From RP 'H' dir pointing up-left:
Resulting CNT is 2, VP is outside (sitting in the hole above H)
From RP 'J' dir pointing up-left 45 degree:
Resulting CNT is 2, VP is outside (sitting in the hole above J, left of 8)
From RP 'J' dir pointing up-left 1 degree (almost vertical): same as the previous example, except seg 8 is ignored because the dir endpoint is on the right side of it so the final CNT is 1 and the result is "inside the red solid": VP is above J, between seg 8 and the vertical black grid line crossing J, close to the grid line.
From RP 'K' dir pointing up-left or down-left: RP is not on vertex; 16 is ignored ([H1] horizontal). [H3] middle crossing for 11, 19 and 20; resulting CNT is 3, odd, VP is inside the red solid.
From RP 'L' left-up or left down: same, except the ray is not hitting 11 so the resulting CNT is 2, even, VP is outside the red solid.
From RP 'M' left-up:
Resulting CNT is 2 (outside)
From RP 'M' left-down near-vertical:
Resulting CNT is 3 (inside)
The reset of the points are marked and labeled to serve as an exercise for the reader.