我有一个G由边{E}和顶点组成的图{V}。中的顶点以{V}二维坐标表示。该图是平面的，这意味着没有两条边相交。
图形G有一些循环，假设一个点位于图形内部，如果它属于 的循环之一G。循环示例可能是、A---B---C---A其中和是顶点并且是边。ABC---
现在给出一个点(x, y)，我怎样才能确定它是在图形内部还是外部？这样做的最好方法或最简单的方法是什么？
我正在使用 Python，如果有帮助的话。
更新：是的，所有的边缘都是直线。
user2881553
问问题
926 次
3 回答
2
@Peter de Rivaz 提供了一个基本的见解，尽管没有证据：如果它位于由图形的外部顶点形成的外壳内部，则该点位于循环内部。我们可以通过证明来证明这一点：
- 船体内部的任何点都在循环内
- 船体外的任何点都不在任何循环内
第一个很容易证明：船体内部的任何点都在一个循环内，因为船体本身就是一个循环。
第二个可以通过reductio ad absurdum来证明。非常非正式地，对于外壳外部的点要在循环内，外壳外部至少需要一个顶点，并且它与循环内至少有两个其他顶点形成一个循环，使得该点是在同一个循环内。但是，循环之外不能有任何顶点，因为根据定义，所有顶点都在循环内部。因此，通过归约荒谬，在任何循环内的外壳之外都没有点。
现在我们确定我们有一个正确的方法来测试我们想要的东西，我们仍然需要一个算法来判断一个点是否在外壳内。这可以通过对光线投射算法的简单扩展来实现。
基本上，我们从所有顶点的列表开始，按垂直坐标排序。然后，对于每对连续的顶点，我们“创建”一条在它们之间的水平线，并检查该线相交的第一条和最后一条边是什么。这两个边缘是船体的一部分。如果测试点位于这两个边缘中的任何一个之间，则它将位于船体内部。
这是前 3 次迭代的图形表示：
于 2013-10-18T10:19:06.040 回答
1
由于图形是平面的，因此您可以通过跟踪每个连接的顶点集的轮廓来执行此操作，然后测试您的点是否在这些多边形中的任何一个内。
这张图片说明了这个想法：
红线是代表左侧连接组件轮廓的多边形，而绿线是代表右侧组件轮廓的多边形。
当且仅当它在轮廓之一内时，您的点才会在循环内。
于 2013-10-18T09:16:01.883 回答
0
首先，我会在我的图表中找到设定的循环（循环）。为此，请参阅此 SO 问题Find all cycles in undirected graphs
然后计算一组最大循环，即那些不包含在另一个循环中的循环（也许您可以同时执行前两个步骤）。
一旦你有了最大的循环，这就是检测多边形内的一个点的问题。存在各种方法，例如 - 画一条线和边缘交叉点的数量 - 从该点到多边形顶点的角度总和（0° -> 外部，360° -> 内部）。
于 2019-09-05T15:49:29.763 回答