多边形自交测试的数值精度
我已经实现了多边形自相交的测试。因为性能并不是那么重要，所以我只是使用了蛮力方法并相互检查每个部分。为了测试线交点，我使用发布的函数 这里。这很好地完成了它的工作。详细来说，线相交测试的结果还向我提供了多边形本身的顶点作为相交点。这时候我的问题就出现了。有时此测试会失败，因为计算交点只能与 javascript 一样精确，并且无法区分交点和顶点。这会导致错误的测试结果，告诉我多边形自相交，即使它没有。
我该如何解决这个问题？对该测试的值进行四舍五入是否也会导致错误的结果？我怎样才能正确克服这个问题？
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??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
据我所知，完全避免此类问题的唯一选择是使用精确的数学库或一组精确的几何谓词。我假设 JavaScript 中存在这样的事情，但它们在服务器端可能更实用。
CGAL，最好的计算几何库之一（无论语言如何），在其 < a href="http://www.cgal.org/philosophy.html" rel="nofollow">哲学页面，以及他们的常见问题解答。
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.