我已阅读如何确定 2D 点是否在多边形内？但我不确定该解决方案是否适用于中间被内部段划分的多边形。想想一个正方形的数字 8，或者只是两个相互堆叠的正方形。任何一个正方形内的点肯定会在多边形“内部”，但交叉计数会根据您前进的方向（以及您是否越过该内部段）而有所不同。
我想解决这个问题的一种方法是将多边形视为两个单独的多边形......（在这种情况下，我需要一种算法将一个复杂的多边形划分为一组更简单的多边形？）
或者是否对光线投射算法或其他多边形点算法进行了改进，以处理我描述的情况？
问问题
1919 次
3 回答
2
所描述的算法可以正常工作，因为如果你仔细观察它，你会发现它只是交叉的数量。如果我们从“8”的任何一个“子多边形”开始，我们将在最坏的情况下穿过边缘 3 次，通常是一次。它确实在里面。否则就在外面。
但是，人们可能会假设存在一种特殊情况。如果光线完全通过交叉点。但请注意，在这种情况下，您还会得到 2 个交叉点 :)。
于 2009-12-31T04:25:32.390 回答
0
The referenced intersection algorithm works for any closed polygon, even if concave or self-intersecting. In order for your two-box polygon to be closed (starting and ending at the same point), the middle segment must be traversed twice. That means that your example ray going through the bottom crosses three edges, so it is inside using the odd-even rule.
于 2011-04-22T17:55:00.627 回答
0
我不确定这是否是最佳解决方案；但是光线投射算法适用于任何凸多边形。任何多边形都可以分解成三角形，这些三角形是凸的。（双框不是凸多边形，因为如果你用线段连接两个顶点，在某些情况下你会越过中心边缘。）所以，澄清一下：首先将多边形分解为三角形，然后使用射线-casting 确定该点是否在三角形内。
[编辑：光线投射确实适用于凹多边形。对不起，我弄错了。]
于 2009-12-31T04:25:24.497 回答