一个点是在图形（顶点和边）内还是在外？

Question

我有一张由边{E}和顶点{V}组成的图G。这些顶点在二维坐标系中表示。该图是平面图，这意味着没有两条边相交。

图G有一些环，如果一个点在其中一个环内，则称该点在图内。一个环的例子可以是A---B---C---A，其中A、B和C是顶点，---是一条边。

现在给定一个点(x, y)，如何确定它是在图内还是在图外？最好的方法或最简单的方法是什么？

我正在使用Python。

更新： 是的，所有的边都是直线。

- user2881553

---

循环如何表示？如果它们是圆形，最好问如何检测点是否在圆内。 - loopbackbee

@mavErick：所有的边都是直线吗？ - Ankur Ankan

@HighPerformanceMark 在问题中完美地定义了他所说的“图形内/外”（假设（v1，v2）是它们之间的直线）。 - amit

我指的是几何表示法。图形是一个数学概念，顶点、边和环也是如此。询问如何检测点是否在图形/环内是没有意义的。如果您正在尝试解决几何问题，应该将其描述为这样。 - loopbackbee

@AnkurAnkan 是的，一切都很顺利。 - user2881553

Answer 1

@Peter de Rivaz提供了一个基本见解，尽管没有证明：如果一个点在图形的外部顶点形成的凸壳内，则该点位于循环内。我们可以通过以下证明来证明这一点：

• 任何在凸壳内的点都在循环内
• 任何在凸壳外的点都不在任何循环内

第一个很容易证明：任何在凸壳内的点都在循环内，因为凸壳本身就是一个循环。

第二个可以通过反证法来证明。非常简单地说，对于一个在凸壳外的点要想在循环内，需要至少有一个顶点在凸壳外面，并且它与至少两个在循环内的其他顶点形成一个循环，使得该点在同一个循环内。然而，不能有任何顶点在循环外，因为按定义，所有顶点都在循环内。因此，通过反证法，没有任何在凸壳外的点在任何循环内。

既然我们确信有一种正确的方法来测试我们想要的内容，我们仍然需要一种算法来判断一个点是否在凸壳内。这可以通过扩展射线投射算法来实现。

基本上，我们从所有顶点的列表开始，按垂直坐标排序。然后，对于每对连续的顶点，我们“创建”一个横跨它们之间的水平线，并检查该线相交的第一条和最后一条边。这两条边是凸壳的一部分。如果被测试的点在这两条边之间，它就在凸壳内。

以下是前3个迭代的图形表示：

- loopbackbee

Answer 2

由于图形是平面的，因此您可以通过跟踪每个连通顶点集的轮廓，然后测试您的点是否在这些多边形内来完成此操作。

这张图片说明了这个想法：

红线是左手连通组件轮廓的多边形表示，绿线是右手组件轮廓的多边形表示。

如果您的点在其中一个轮廓内部，则该点将处于循环内部。

- Peter de Rivaz

Answer 3

首先，我会在我的图中找到一组循环。为此，请参阅此SO问题查找无向图中的所有循环

然后计算最大循环的集合，即那些不包含在另一个循环中的循环（也许您可以同时完成这两个步骤）。

一旦您拥有了最大循环，就可以检测一个点是否在多边形内。存在各种方法，例如： - 画一条线和边交点的数量 - 从点到多边形顶点的角度之和（0°->外部，360°->内部）。

请参阅如何确定2D点是否在多边形内？

- François Legras