确定顶点是否在一组顶点内

Question

在我的算法中，我发现处于不同阈值的图形。每个图G =（V，E）。这些是使用广度优先搜索找到的无向图。我想确定另一个图G'=（V'，E'）的顶点是否在图G内。我不熟悉图算法，因此，如果您想查看代码或更详尽的解释，请告诉我。

例如，如果我有一个图G1，它是一个带有（{为其他原因，但为了简化而简化的））角为{{1,1，（1,6），（6,6），（ 6,1）}，则由角顶点{（2,2），（2,5），（5,5），（5,2）}定义的较小正方形G2将位于G1内。由角{（3，3），（3，4），（4，4），（4，3）}定义的第三图G3。我的算法为此配置生成下图：

阈值为2的正方形，被t = 1包围，被t = 0包围。 （我需要固定边缘，但顶点是正确的）

我的算法适用于以下矩阵：

import numpy as np

    A = np.zeros((7,7))
    #A[A<1] = -1
    for i in np.arange(1,6):
        for j in np.arange(1,6):
            A[i,j] = 1
    for i in np.arange(2,5):
        for j in np.arange(2,5):
            A[i,j] = 2
    for i in np.arange(3,4):
        for j in np.arange(3,4):
            A[i,j] = 3
    print(A)

要创建三个图，第一个处于阈值2，第二个处于阈值1，第三个处于阈值0。

v1 = [[(3.0, 2.25), (3.0, 3.75), (2.25, 3.0), (3.75, 3.0)]]
v2 = [[(2.0, 1.333333), (1.333333, 3.0), (1.333333, 2.0), (1.333333, 4.0), (2.0, 4.666667), (3.0, 4.666667), (4.0, 4.666667), (4.666667, 4.0), (4.666667, 3.0), (4.666667, 2.0), (4.0, 1.333333), (3.0, 1.333333)]]
v3 = [[(1.0, 0.5), (0.5, 2.0), (0.5, 1.0), (0.5, 3.0), (0.5, 4.0), (0.5, 5.0), (1.0, 5.5), (2.0, 5.5), (3.0, 5.5), (4.0, 5.5), (5.0, 5.5), (5.5, 5.0), (5.5, 4.0), (5.5, 3.0), (5.5, 2.0), (5.5, 1.0), (5.0, 0.5), (4.0, 0.5), (3.0, 0.5), (2.0, 0.5)]]

和边列表：

e1 = [[[2.25, 3.0], [3.0, 2.25]], [[3.0, 3.75], [2.25, 3.0]], [[3.0, 2.25], [3.75, 3.0]], [[3.0, 3.75], [3.75, 3.0]]]
e2 = [[[1.333333, 2.0], [2.0, 1.333333]], [[1.333333, 3.0], [1.333333, 2.0]], [[1.333333, 4.0], [1.333333, 3.0]], [[2.0, 4.666667], [1.333333, 4.0]], [[2.0, 1.333333], [3.0, 1.333333]], [[2.0, 4.666667], [3.0, 4.666667]], [[3.0, 1.333333], [4.0, 1.333333]], [[3.0, 4.666667], [4.0, 4.666667]], [[4.0, 1.333333], [4.666667, 2.0]], [[4.666667, 3.0], [4.666667, 2.0]], [[4.666667, 4.0], [4.666667, 3.0]], [[4.0, 4.666667], [4.666667, 4.0]]]
e3 = [[[0.5, 1.0], [1.0, 0.5]], [[0.5, 2.0], [0.5, 1.0]], [[0.5, 3.0], [0.5, 2.0]], [[0.5, 4.0], [0.5, 3.0]], [[0.5, 5.0], [0.5, 4.0]], [[1.0, 5.5], [0.5, 5.0]], [[1.0, 0.5], [2.0, 0.5]], [[1.0, 5.5], [2.0, 5.5]], [[2.0, 0.5], [3.0, 0.5]], [[2.0, 5.5], [3.0, 5.5]], [[3.0, 0.5], [4.0, 0.5]], [[3.0, 5.5], [4.0, 5.5]], [[4.0, 0.5], [5.0, 0.5]], [[4.0, 5.5], [5.0, 5.5]], [[5.0, 0.5], [5.5, 1.0]], [[5.5, 2.0], [5.5, 1.0]], [[5.5, 3.0], [5.5, 2.0]], [[5.5, 4.0], [5.5, 3.0]], [[5.5, 5.0], [5.5, 4.0]], [[5.0, 5.5], [5.5, 5.0]]] 

同样，给出的图形如下：>

这是我正在处理的真实数据。更复杂的形状。

例如，在这里，我在绿色形状的内部是红色。理想情况下，红色形状应位于红色形状内。它们将被组合在一个对象中（例如一组图形）。

图形以顺时针方向连接。我真的不知道如何描述它，但是也许链接中的图形显示了这一点。这两行有一个错误（如您在右上角的第一个绘图中所见），但是顶点是正确的。

希望这会有所帮助！我可以附上一个完整的可行示例，但是它将包括我的整个算法，并且页面长，并且具有许多功能！我基本上想使用将g1，g2和g3之一输入到函数（或e1，e2和e3）中。该函数将告诉我g3包含在g2中，而g2包含在g1中。

在我的算法中，我发现处于不同阈值的图形。每个图G =（V，E）。这些是使用广度优先搜索找到的无向图。我想确定另一个顶点的顶点是否...

Answer 1

您的问题实际上与网络关系不大。从根本上讲，您试图确定点是否在点的有序列表所描述的区域内。最简单的方法是创建具有Path方法的matplotlib contains_point（还有一个“ contains_points”方法可同时测试许多点）。