Point in Polygon
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.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| 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 |