Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon)

From Algorithm Wiki

Revision as of 10:53, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of ray direction and how many polygon sides intersect with the ray) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1962 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/368637.368653")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to navigation Jump to search

Time Complexity

$O(n)$

Space Complexity

$O({1})$ words

(Only need to keep track of ray direction and how many polygon sides intersect with the ray)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM

Year

1962

Reference

https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/368637.368653

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Ray_casting_algorithm_Shimrat;_M_(Point-in-Polygon_Point-in-Polygon)&oldid=44987"