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

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)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Real RAM

Year

1962

Reference

https://dl.acm.org/doi/pdf/10.1145/368637.368653