如何判断直线是否与简单多边形相交？
我需要知道如何快速确定线是否与简单多边形相交。 它应该在 O(log n) 时间内工作，其中 n 是多边形顶点的数量。 我在谷歌上搜索过，但没有找到任何有用的东西，也许我是盲目的。 ;) 编辑：我正在使用C++，但我认为语言不是问题，也不是家庭作业，只是做一些算法训练。几何有病。 ;) 哦。我忘了这只是二维的。 感谢您未来和实际的帮助。
I need to know how to determine fast if line intersects simple polygon.
It should work in O(log n) time, where n is number of polygon's vertexes.
I searched in google, but I didn't find anything useful, maybe I'm blind. ;)
Edit: I'm using C++ but I think language isn't a problem, and it isn't homework, just doing some algorithms training. Geometry is sick. ;)
Oh. I forgot it's only in 2d.
Thanks for future and actual help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我发现一篇论文可以非常快地解决这个问题：
“Fast MinimStorage RayTriangle Intersection”
http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf< /a>
编辑：它甚至包含代码:)
I've found a paper who solves this problem really fast:
"Fast MinimumStorage RayTriangle Intersection"
http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf
EDIT: It even contains code :)