Point-in-Polygon (Point-in-Polygon)

Description

With a given polygon $P$ and an arbitrary point $q$, determine whether point $q$ is enclosed by the edges of the polygon.

Parameters

No parameters found.

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Ray casting algorithm Shimrat; M	1962	$O(n)$	$O({1})$	Exact	Deterministic	Time
Nordbeck and Rystedt (Grid Method)	1967	$O(a)$	$O({1})$	Exact	Deterministic	Time
Salomon (Swath Method)	1978	$O(nlogn)$	$O(n^{2})$	Exact	Deterministic	Time & Space
Nordbeck and Rystedt (Sum of area)	1967	$O(n)$	$O({1})$	Exact	Deterministic	Time
Preparata and Shamos (Wedge)	1985	$O(n)$	$O(n)$	Exact	Deterministic	Time & Space
Saalfeld (Sign of offset)	1987	$O(n)$	$O({1})$	Exact	Deterministic	Time
Preparata and Shamos (Intersection sum of angle)	1985	$O(n)$	$O({1})$	Exact	Deterministic	Time
Nordbeck and Rystedt (Orientation)	1967	$O(n)$	$O({1})$	Exact	Deterministic	Time

Time Complexity graph

Space Complexity graph

Pareto Decades graph