自相交/复杂多边形中的点

Question

我已经阅读了如何确定2D点是否在多边形内部?，但我不确定解决方案是否适用于被内部线段分成两部分的多边形。 想象一个方形的数字8或仅仅是两个正方形叠在一起。 任何一个正方形内部的点肯定都在多边形“内部”，但穿越计数会根据您走的方向（以及是否穿过该内部线段）而有所不同。

我想，处理这种情况的一种方法是将多边形视为两个单独的多边形...（在这种情况下，我需要一种算法将复杂多边形分成一组更简单的多边形吗？）

还是说，有没有对射线投射算法进行改进，或者其他点在多边形内的算法来处理我描述的情况？

- emh

---

有很多不同的方法可以使事情在这种情况下正常运作，但它们都关键取决于您如何解释这种情况。更具体地说，您如何表示这样的“多边形”？使用什么数据结构？您可以拥有多个内部线段吗？如果可以，内部线段是否会相交？ - AnT stands with Russia

基本上，目前看来你只是对问题有一个草图而已。你还没有完全阐述这个问题。当问题本身没有完全陈述时，寻找解决方案还为时过早。 - AnT stands with Russia

Answer 1

描述的算法很好，因为如果你仔细看它，你会发现只有交叉点的数量才是重要的。如果我们从“8”的任何一个“子多边形”开始，最坏情况下我们将穿过边界3次，通常只穿过一次。而且它在内部是正确的。否则就在外面。

然而，可以假设存在一个特殊情况。如果光线恰好通过交叉点。但请注意，在这种情况下，您也将得到2个交点：)。

- Kornel Kisielewicz

---

你怎样跨越三次？如果我的点位于顶部正方形中，我画的线指向上方则交叉一次（因此点在内部），但是如果我画的线向下，则会穿过中心线段一次和底部线段一次共交叉两次。 - emh

看上面添加的图片 - 看到光线会交叉一次或两次，这取决于你选择的方向吗？ - emh

啊，原来是这样...在这种情况下，你有一些明显是“内部”的边缘。将它们标记为内部，并且不要包含在内部性测试中。 - Kornel Kisielewicz

请原谅我问一个愚蠢的问题，但是如何通过算法来测试一条边是否为内部边呢？（我考虑过通过测试线段的中点是否在多边形内部来判断，但是遇到了一个进退两难的情况，特别是当存在多个内部边时）。到目前为止，我的谷歌搜索没有找到任何相关结果。 - emh

Answer 2

我不确定这是否是最优解决方案，但射线投射算法适用于任何凸多边形。任何多边形都可以分解成三角形，而三角形是凸的。（双框不是凸多边形，因为如果您用线段连接两个顶点，在某些情况下会越过中心边。）因此，要澄清：首先将多边形分解为三角形，然后使用射线投射来确定点是否在三角形内。

[编辑：射线投射确实适用于凹多边形。抱歉，我弄错了。]

- RMorrisey

---

该操作描述的是一个多边形，它甚至比凹多边形更为退化。 - Kornel Kisielewicz

实际上，该算法不仅适用于凸多边形，而且也适用于凹和复杂多边形。我理解的复杂多边形是指多边形与自身相交。（想象一下两个直角三角形顶点对齐的情况，而不是两个重叠的正方形）我还会研究多边形三角剖分作为一种将复杂多边形分解为一组凸多边形的方法。 - emh

Answer 3

所提到的交点算法适用于任何闭合多边形，即使是凹多边形或自相交多边形也可以。为了使您的两个框多边形闭合（起点和终点相同），中间段必须被遍历两次。这意味着您的示例射线穿过底部时会穿过三条边，因此使用奇偶规则内部。

- xan