Is the mouse cursor inside this shape? For a rectangle that is four comparisons. Once the shape has dents, say a trigger zone, a region on a map or something drawn freehand, four comparisons are not enough anymore. The classic answer fires a ray from the point and counts how often it crosses the edges.
The mouse cursor is the test point. A dashed ray runs from it to the right, every edge it crosses turns orange, and every crossing gets a marker. The corners can be dragged, a click on an edge adds a new corner, right click or Del removes one (three always stay). The result is at the top left. While you drag, the test point stays where it was, so you can watch the result change as the corner moves.
Counting
An odd number of crossings means inside, an even number means outside. The ray enters or leaves the shape at every crossing, and far to the right it is guaranteed to be outside. What is left to decide is when an edge crosses the ray. First, one end of the edge has to be above and the other below the ray's height:
inline bool spansRow(Vec2 a, Vec2 b, double y) { return (a.y > y) != (b.y > y); }
Then the crossing has to lie to the right of the point. You could compute it and compare. I decide it with the sign of a cross product instead, which drops the division and is exact for whole-number coordinates:
const double cross = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
const bool right = b.y > a.y ? cross > 0.0 : cross < 0.0;
if (right) out.push_back({detail::xAt(a, b, p.y), detail::direction(a, b), i});
I still compute the x position of the crossing, but only so the demo can put the marker there.
The corner
This is the trap, and spansRow above is the answer to it. What happens when the ray runs exactly through a corner? The obvious check with a closed interval (p.y lies between the two y values, ends included) catches the corner for both edges that meet there. If the polygon passes through the ray at that spot, the crossing is counted twice and the parity flips. A horizontal edge at the ray's height makes it worse, because you would divide by zero.
(a.y > p.y) != (b.y > p.y) leaves the interval open on one side. An edge covers the heights from its smaller y up to just below its larger y. You can also think of it like this: a corner that sits exactly on the ray is treated as if it were a hair below it, at a smaller y. The ray never hits a corner anymore, there are only clean crossings. That gives the three cases:
If the polygon passes through the corner, exactly one of the two edges counts. If only a tip touches the ray, either both count or neither, so the parity stays even. A horizontal edge never passes the test and is never counted, its neighbouring edges sort it out on their own.
To try it, use the "Snap ray to corner" chip (key S). The ray then locks onto the height of the nearest corner and the corner gets a ring. On the concave polygon you can see that of the two edges at a pass-through corner only one turns orange. In the test it is the same thing as a diamond whose left and right corners sit exactly at height 0:
const Polygon d{{0, -2}, {2, 0}, {0, 2}, {-2, 0}};
assert(evenOdd(d, {0, 0})); // ray leaves through the right corner: that must count once
assert(!evenOdd(d, {-5, 0})); // ray passes the left corner and the right corner: once each, even
Even-odd or winding number
Instead of just counting, you can give every crossing a direction: +1 if the edge runs towards a larger y, -1 otherwise. The sum is the winding number, and anything other than 0 means inside:
inline int windingNumber(const Polygon& poly, Vec2 p) {
int w = 0;
for (const Crossing& c : rayCrossings(poly, p)) w += c.dir;
return w;
}
On ordinary polygons both give the same answer. The difference shows when the polygon crosses itself. That is why the demo starts with a five-pointed star, where every corner is connected to the one after next. The pentagon in the middle is circled twice by the line. The ray from the center crosses two edges, two is even, so ray casting says "outside" and leaves the middle hollow when filling. With chip 2 (key 2) it counts +1 twice, the winding number is 2 and the middle is "inside". The demo's fill is drawn with the selected rule, so you see the switch right away. SVG and canvas both know the two rules as fill-rule, with nonzero as the default.
Pitfalls
If the test point itself lies exactly on the boundary, the result is a convention. With this rule the sides with the smaller x or y are inside and the ones with the larger x or y are outside. On the square from (0,0) to (4,4), (0,2) is inside and (4,2) is outside. Two polygons that share an edge never both claim the same point that way. With mouse coordinates this rarely happens, which is why the snap chip exists, it sets the ray height to a corner.
Besides hand-computed cases there is a test that mirrors the same polygons and checks that the answer stays the same. A ray to the right in the mirrored polygon is a ray to the left in the original, so that is a second, independent answer to the same question. A polygon with fewer than three corners has no area, rayCrossings returns no hits for it, and deleting stops at three corners.
The code is in the repo under point-in-polygon. The project Game Dev Snippets collects all demos of the series.