点在图的内部还是外部（顶点和边）？

Question

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

图G有一些循环，假设一个点落在图的内部，如果它落入 的一个循环中G。循环示例可以是A---B---C---A，其中A、B和C是顶点，---是边。

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

我正在使用Python，如果有帮助的话。

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

Answer 1

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

这张图说明了这个想法：

红线是表示左手连通分量轮廓的多边形，而绿线是表示右手连通分量轮廓的多边形。

当且仅当您的点位于其中一个轮廓内时，它才会位于循环内。