Point-in-Polygon: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/10.1007/BF01934125 Time] | ||
Revision as of 09:24, 10 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
Space Complexity Graph
Time-Space Tradeoff
