Point-in-Polygon: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision 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 37: | Line 37: | ||
[[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
