Skip to main content
2 of 2
Broken link fixed.
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

This problem is called the point-in-polygon problem in the graphics and computational geometry literature, and searching that phrase will bring you to much discussion and working code. It is rather firmly established that the best method is the ray-shooting algorithm, described, e.g., in Wikipedia here.
      Wikipedia image
Straightforward implementation runs in $O(n)$ time, and you can find this all over the web, including my own implementation here. If you are going to repeatedly query, sophisticated data structures will allow $O(\log n)$ per query.

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958