我有一个由边 {E} 和顶点 {V} 组成的图 G。 {V} 中的顶点以二维坐标表示。该图是平面的，这意味着没有两条边相交。
图 G 有一些环，假设一个点落在 G 的环之一中，则它在图中。循环示例可以是 A---B---C---A，其中 A、B 和 C 是顶点，--- 是边。
现在给定一个点(x, y)，我如何确定它是在图内还是在图外？最好或最简单的方法是什么？
如果有帮助的话，我正在使用 Python。
更新:是的，所有的边都是直线。
最佳答案
@Peter de Rivaz 提供了一个基本的见解，尽管没有证据:该点在一个循环内，当且仅当它在由图形的外部顶点形成的外壳内。我们可以通过证明来证明这一点:
- 船体内的任何点都在一个环内
- 船体外的任何点都不在任何环内
第一个很容易证明:船体内部的任何点都在一个环内，因为船体本身就是一个环。
第二个可以用反证法证明。非常非正式地，要使船体外部的点位于环路内，则船体外部至少需要有一个顶点，并且要使其与环路内的至少两个其他顶点形成环路，因此该点是在同一个循环内。但是，循环外不能有任何顶点，因为根据定义，所有顶点都在循环内。因此，通过反证法，在任何环内的船体外没有任何点。
现在我们确定我们有一个正确的方法来测试我们想要的东西，我们仍然需要一个算法来判断一个点是否在船体内部。这可以通过 ray casting algorithm 的简单扩展来实现。 .
基本上，我们从所有顶点的列表开始，按垂直坐标排序。然后，对于每一对连续的顶点，我们“创建”在它们之间的水平线，并且 check what is the first and last edge that the line intersects .这两个边缘是船体的一部分。如果测试点位于这两条边中的任何一条之间，则它将在船体内部。
这是前 3 次迭代的图形表示:
关于python - 一个点在图的内部还是外部(顶点和边)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19445332/