Point in Polygon
GeometryHardVerify point containment in closed shapes using Ray Casting sweeps.
Alt+Shift+P
Ray Casting Crossing Grid (Drag Test Point P or polygon corners)
Containment Result:INSIDE POLYGON
Ray Crossings Log:
• Ray crossed edge between B and C. Status toggled: INSIDE
Time Complexity
O(N) linear sweep of edges
Space Complexity
O(1) auxiliary
Conceptual Overview
Point in Polygon checks if a coordinate lies inside a closed polygon using the Ray Casting algorithm (even-odd rule).
Mathematical Formula
\text{Cross check: } y_{1} > y_{P} \ne y_{2} > y_{P} \text{ and } x_{P} < \frac{(x_2-x_1)(y_P-y_1)}{y_2-y_1} + x_1
Source: CP-Algorithms geometry reference