# Point in Polygon

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Problem Description

A polygon is a two-dimensional geometric figure that has a finite number of sides. The sides of a polygon are made of straight line segments connected to each other end to end. The line segments of a polygon are called sides or edges. The point where two line segments meet is called vertex or corners, henceforth an angle is formed. An example of a polygon is a triangle with three sides.

A circle is also a plane figure but it is not considered as a polygon, because it is a curved shape and does not have sides or angles. Therefore, we can say, all the polygons are 2d shapes but not all the two-dimensional figures are polygons.

The problem deals with identifying if a point lies inside a polygon or not.

## Improvement Table

Exp/Factorial
Polynomial > 3
Cubic
nlogn [Swath Method (1978)]
Linear [Ray casting algorithm Shimrat; M (1962)]

[Nordbeck and Rystedt (1967)]

[Sum of area (1962)]

[Wedge (1985)]

[Sign of offset (1987)]

[Intersection sum of angle (1985)]

[Orientation (1962)]

logn