Point in Polygon

From Algorithm Wiki
Revision as of 13:45, 15 September 2021 by Yashsherry (talk | contribs) (→‎Problem Description)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Point in polygonBoundsChart.png

Step Chart

Point in polygonStepChart.png

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