如何确定线是否相交简单多边形？

如果直线与简单多边形相交，我需要知道如何快速确定。它应该在O（log n）时间内工作，其中n是多边形顶点的数量。我在谷歌搜索，但我没有发现任何有用的，也许我是盲目的。 ;）编辑：我使用C++，但我认为语言不是问题，它不是作业，只是做一些算法培训。几何有病。 ;）哦。我忘了它只是在2d。感谢您的未来和实际帮助。如何确定线是否相交简单多边形？

来源

2010-10-16 ChosenOne

需要更多的信息。你使用什么语言，你的对象是什么，等等。这个功课？ – hvgotcodes 2010-10-16 15:08:21

为什么O（lon n）时间要求为“简单多边形”？对于小型多边形来说，任何时间复杂性都会变得缓慢和复杂。 – phkahler 2010-10-18 13:51:49

我发现一个纸谁真快解决了这个问题：

“快速MinimumStorage RayTriangle交会”

http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf

编辑：它甚至包含代码:)

来源

2010-10-16 15:32:21 Bigbohne

如何确定线是否相交简单多边形？

回答

相关问题