Point in Polygon
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.
|Complexity Classes||Algorithm Paper Links||Lower Bounds Paper Links|
|Polynomial > 3|
|nlogn||[Swath Method (1978)]|
|Linear||[Ray casting algorithm Shimrat; M (1962)]
[Nordbeck and Rystedt (1967)]
[Sum of area (1962)]
[Sign of offset (1987)]
[Intersection sum of angle (1985)]