指向一个自相交/复杂多边形

我读过How can I determine whether a 2D Point is within a Polygon?但我不确定该解决方案是否适用于由内部细分中间的多边形。想想一个方形图8或简单地两个方块堆叠在一起。任何一个正方形内的一个点肯定会在多边形“内部”，但交叉点数会根据您所走的方向（以及您是否越过该内部线段）而有所不同。指向一个自相交/复杂多边形

sample polygon

我想处理这个问题的方法之一是把多边形作为两个单独的多边形...（在这种情况下，我需要一个算法，一个复杂的多边形分成一组简单的人的？）

或者是否有对光线投射算法或另一个点多边形算法进行改进来处理我描述的情况？

来源

2009-12-31 emh

有很多不同的方法可以使事情在这种情况下工作，但他们都严重依赖于你如何解释这种情况。更具体地说，你如何表示这样的“多边形”？使用什么数据结构？你可以有多个内部细分？如果是这样，内部部分可以相互交叉？ – AnT 2011-04-22 18:50:55

基本上，在这个时候看起来你所拥有的只是一个问题的草图。您尚未完成制定*问题*。当问题本身没有完全阐明时，寻求解决方案为时尚早。 – AnT 2011-04-22 18:53:28

我不确定这是否是最佳解决方案;但光线投射算法适用于任何凸多边形。任何多边形都可以分解为凸面的三角形。（双框不是凸多边形，因为如果用线段连接两个顶点，在某些情况下，您将跨越中心边缘。）所以，为了澄清：首先将多边形分解为三角形，然后使用ray - 确定点是否在三角形内。

[编辑：光线投射确实适用于凹多边形。对不起，我错了。]

来源

2009-12-31 04:25:24 RMorrisey

op描述了一个多于凹的多边形，它是退化的;> – 2009-12-31 04:26:29

实际上，算法不仅适用于凸多边形，也适用于凹多边形和复杂多边形。我的理解是复杂的多边形是多边形相交的地方。（而不是2个堆叠的方块想象2个堆叠的三角形站在一个点上）。我还将研究多边形三角测量法作为将复杂多边形分解为一组凸面的方法。 – emh 2009-12-31 18:29:27

你说得对，对不起，我的错误 – RMorrisey 2010-01-03 17:43:19

所描述的算法会正常工作，因为如果你仔细看看它，你会发现它只是计数的交叉点数。如果我们从“8”的“子多边形”开始，我们将在最坏的情况下跨越3次，通常是一次。这是真的，它在里面。否则它在外面。

然而，人们可能会认为有一个特殊情况。如果光线通过交叉点完全通过。但请注意，在这种情况下，你还会得到2个交点:)。

来源

2009-12-31 04:25:32

你会如何跨越3次？如果我的观点是在顶部广场，我画出我的光线指向我穿过一次（所以点在里面），但如果我画我的光线，我穿过两次：一次穿过中央部分，一次穿过底部部分。 – emh 2009-12-31 18:11:34

我认为你需要发布一张图片来澄清事情。 – 2009-12-31 20:25:34

上面添加的图像 - 根据您走向哪个方向，了解光线将如何交叉一次或两次？ – emh 2010-01-05 19:14:36

参考交点算法适用于任何封闭的多边形，即使凹或自相交。为了让你的双盒多边形被关闭（在同一点开始和结束），中间部分必须被遍历两次。这意味着您的示例射线穿过底部时会穿过三条边，所以它使用奇偶规则。

来源

2011-04-22 17:55:00 xan

指向一个自相交/复杂多边形

回答

相关问题