Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon)
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/doi/pdf/10.1145/368637.368653")
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