CODEWITHSUNDEEP
javascriptcomputational-geometry
philipp
philipp

Reputation: 16485

Numerical precision for test of polygon self-intersection

I have implemented a test for self-intersection of a polygon. Because Performance is not so important i just used the brute force approach and check every segment against each other. To test line-intersection i use the function posted here. This is doing its job quiet fine. In detail the result of the line intersection test also delivers me the vertices of the polygon itself as intersection points. And here my problem comes into play. Sometimes this test fails, because computing the intersection point is only as exact as javascript can be and it is not possible to distinguish the intersection point from the vertex. This leads to a wrong test result, telling me that the polygon self intersects, even it does not.

How can i solve this problem? Does rounding the values for this test also lead to wrong results? How can i overcome this problem properly??

Upvotes: 2

Views: 479

Answers (1)

Andrew Walker
Andrew Walker

Reputation: 42440

The only option I know of to avoid such issues completely is to use an exact math library, or a set of exact geometric predicates. I assume such things exist in javascript, but they may be more practical to do on the server side.

CGAL, one of the best computational geometry libraries (irrespective of language), have a detailed discussion of this issue in their philosophy page, and their FAQ.

Upvotes: 2

Related Questions