Point in polygon

In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographic information systems (GIS), motion planning, and computer-aided design (CAD).

The status of a point on the edge of the polygon depends on the details of the ray intersection algorithm.

If implemented on a computer with finite precision arithmetics, the results may be incorrect if the point lies very close to that boundary, because of rounding errors.

For some applications, like video games or other entertainment products, this is not a large concern since they often favor speed over precision.

In other cases, when polygon sides are computed from other types of data, other tricks must be applied for the numerical robustness of the algorithm.

Sunday's algorithm works by considering an infinite horizontal ray cast from the point being checked.

[6] Similar methods are used in SVG for defining a way of filling with color various shapes (such as path, polyline, polygon, text etc.).

One solution using the even-odd rule is to transform (complex) polygons into simpler ones that are even-odd-equivalent before the intersection check.

It is less expensive to use the fast non-zero winding number algorithm, which gives the correct result even when the polygon overlaps itself.

The triangle case can be solved easily by use of a barycentric coordinate system, parametric equation or dot product.

An example of a simple polygon
The number of intersections for a ray passing from the exterior of the polygon to any point: If odd, it shows that the point lies inside the polygon; if even, the point lies outside the polygon. This test also works in three dimensions.
Visualization of Dan Sunday's winding number algorithm. A winding number of 0 means the point is outside the polygon; other values indicate the point is inside the polygon