Point-in-Polygon: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE: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 == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Ray casting algorithm Shimrat; M (Point-in-Polygon...") |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: number of edges of polygon | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 18: | Line 18: | ||
| [[Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon)|Ray casting algorithm Shimrat; M]] || 1962 || $O(n)$ || $O({1})$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/368637.368653 Time] | | [[Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon)|Ray casting algorithm Shimrat; M]] || 1962 || $O(n)$ || $O({1})$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/368637.368653 Time] | ||
|- | |- | ||
| [[Nordbeck and Rystedt (Grid Method) (Point-in-Polygon Point-in-Polygon)|Nordbeck and Rystedt (Grid Method)]] || 1967 || $O( | | [[Nordbeck and Rystedt (Grid Method) (Point-in-Polygon Point-in-Polygon)|Nordbeck and Rystedt (Grid Method)]] || 1967 || $O(n)$ || $O(n)$ || Exact || Deterministic || [https://doi.org/10.1007/BF01934125 Time] & [https://ir.nctu.edu.tw/bitstream/11536/749/1/A1997WM15100010.pdf Space] | ||
|- | |- | ||
| [[Salomon (Swath Method) (Point-in-Polygon Point-in-Polygon)|Salomon (Swath Method)]] || 1978 || $O( | | [[Salomon (Swath Method) (Point-in-Polygon Point-in-Polygon)|Salomon (Swath Method)]] || 1978 || $O(n\log n)$ || $O(n^{2})$ || Exact || Deterministic || [https://doi.org/10.1016/0098-3004(78)90085-7 Time] & [https://ir.nctu.edu.tw/bitstream/11536/749/1/A1997WM15100010.pdf Space] | ||
|- | |- | ||
| [[Nordbeck and Rystedt (Sum of area) (Point-in-Polygon Point-in-Polygon)|Nordbeck and Rystedt (Sum of area)]] || 1967 || $O(n)$ || $O({1})$ || Exact || Deterministic || [https://doi.org/10.1007/BF01934125 Time] | | [[Nordbeck and Rystedt (Sum of area) (Point-in-Polygon Point-in-Polygon)|Nordbeck and Rystedt (Sum of area)]] || 1967 || $O(n)$ || $O({1})$ || Exact || Deterministic || [https://doi.org/10.1007/BF01934125 Time] | ||
| Line 34: | Line 34: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Point-in-Polygon - Time.png|1000px]] | [[File:Point-in-Polygon - Time.png|1000px]] | ||
Latest revision as of 09:11, 28 April 2023
Description
With a given polygon $P$ and an arbitrary point $q$, determine whether point $q$ is enclosed by the edges of the polygon.
Parameters
$n$: number of edges of polygon
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(n)$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Salomon (Swath Method) | 1978 | $O(n\log n)$ | $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
