如何检查线段是否与简单多边形相交
How to check if a line segment intersects a simple polygon
我正在尝试实现 De Berg 等人的计算几何书中的可见性图算法。您可以在此处找到算法：http://cs.smith.edu/~streinu/Teaching/Courses/274/Spring98/Projects/Philip/fp/algVisibility.htm
我在使用 VISIBLE 算法的第一行时遇到问题：
if pwi intersects the interior of the obstacle of which wi is a vertex, locally at wi then return false
书上说它应该花费 O(lg n) 时间（其中 n 是平面上的所有点），但它没有解释如何进行检查。我发现的算法花费的时间与多边形的顶点数有关。
感谢任何帮助。
我相信你所关注的步骤最多需要 O(log n) 时间，
因为你可以在 wi 是顶点的障碍物上使用二进制搜索。
我正在尝试实现 De Berg 等人的计算几何书中的可见性图算法。您可以在此处找到算法：http://cs.smith.edu/~streinu/Teaching/Courses/274/Spring98/Projects/Philip/fp/algVisibility.htm
我在使用 VISIBLE 算法的第一行时遇到问题：
if pwi intersects the interior of the obstacle of which wi is a vertex, locally at wi then return false
书上说它应该花费 O(lg n) 时间（其中 n 是平面上的所有点），但它没有解释如何进行检查。我发现的算法花费的时间与多边形的顶点数有关。
感谢任何帮助。
我相信你所关注的步骤最多需要 O(log n) 时间， 因为你可以在 wi 是顶点的障碍物上使用二进制搜索。