0

We have a set of polygons, and a point we can assume is in one of the polygons. I'd need a solid algorithm that tells me which of the polygon the point is in. I've tried some things, but the floating point precision was a problem at the edges, and i need something that works fine, possibly a robust c/c++ library to do the job, any ideas? Or maybe it's better to implement known algorithms using "infinite precision" libraries?

tuccio
  • 333
  • 3
  • 10
  • 4
    Floating point precision isn't usually fixed by changing the algorithm… use a fuzz factor to "expand" the polygon by a few epsilon. If you really need an arbitrary-precision hit test, you must already have arbitrary-precision points… – Potatoswatter Nov 30 '11 at 18:41
  • Related: http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test – lhf Nov 30 '11 at 18:43
  • See also http://lin-ear-th-inking.blogspot.com/2007/07/ultimate-point-in-polygon.html and http://dx.doi.org/10.1111/j.1467-8659.2009.01481.x – lhf Nov 30 '11 at 18:44
  • 2
    It's very unlikely that floating point precision is your problem. [This answer](http://stackoverflow.com/a/2922778/233201) details a very good method for testing points against polygons - the zero-crossings test. – James Nov 30 '11 at 18:53

0 Answers0