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

Question

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

例如，如果我有一个图G，它是一个带有（0,0），（0,8），（8,8）和（ 8,0），则由角顶点（2,2），（2,4），（4,4）和（4,2）定义的较小正方形将位于G范围内。很抱歉，如果这很明显问题，我只是不熟悉图形，可以使用一个或两个指针（欢迎使用关键字）。

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

import numpy as np

A = np.zeros((9,9))
    for i in np.arange(1,8):
        for j in np.arange(1,8):
            A[i,j] = 1
    for i in np.arange(2,4):
        for j in np.arange(2,4):
            A[i,j] = 2
    print(A)

产生矩阵：

[[-1. -1. -1. -1. -1. -1. -1. -1. -1.]
 [-1.  1.  1.  1.  1.  1.  1.  1. -1.]
 [-1.  1.  2.  2.  1.  1.  1.  1. -1.]
 [-1.  1.  2.  2.  1.  1.  1.  1. -1.]
 [-1.  1.  1.  1.  1.  1.  1.  1. -1.]
 [-1.  1.  1.  1.  1.  1.  1.  1. -1.]
 [-1.  1.  1.  1.  1.  1.  1.  1. -1.]
 [-1.  1.  1.  1.  1.  1.  1.  1. -1.]
 [-1. -1. -1. -1. -1. -1. -1. -1. -1.]]

创建两个图形：

具有顶点：

V1 = [[(2.0, 1.333333), (1.333333, 3.0), (1.333333, 2.0), (2.0, 3.666667), (3.0, 3.666667), (3.666667, 3.0), (3.666667, 2.0), (3.0, 1.333333)]]
V2 = [[(1.0, 0.5), (0.5, 2.0), (0.5, 1.0), (0.5, 3.0), (0.5, 4.0), (0.5, 5.0), (0.5, 6.0), (0.5, 7.0), (1.0, 7.5), (2.0, 7.5), (3.0, 7.5), (4.0, 7.5), (5.0, 7.5), (6.0, 7.5), (7.0, 7.5), (7.5, 7.0), (7.5, 6.0), (7.5, 5.0), (7.5, 4.0), (7.5, 3.0), (7.5, 2.0), (7.5, 1.0), (7.0, 0.5), (6.0, 0.5), (5.0, 0.5), (4.0, 0.5), (3.0, 0.5), (2.0, 0.5)]]

和边列表：

e1 = [[[1.333333, 2.0], [2.0, 1.333333]], [[1.333333, 3.0], [1.333333, 2.0]], [[2.0, 3.666667], [1.333333, 3.0]], [[2.0, 1.333333], [3.0, 1.333333]], [[2.0, 3.666667], [3.0, 3.666667]], [[3.0, 1.333333], [3.666667, 2.0]], [[3.666667, 3.0], [3.666667, 2.0]], [[3.0, 3.666667], [3.666667, 3.0]]]
e2 = [[[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]], [[0.5, 6.0], [0.5, 5.0]], [[0.5, 7.0], [0.5, 6.0]], [[1.0, 7.5], [0.5, 7.0]], [[1.0, 0.5], [2.0, 0.5]], [[1.0, 7.5], [2.0, 7.5]], [[2.0, 0.5], [3.0, 0.5]], [[2.0, 7.5], [3.0, 7.5]], [[3.0, 0.5], [4.0, 0.5]], [[3.0, 7.5], [4.0, 7.5]], [[4.0, 0.5], [5.0, 0.5]], [[4.0, 7.5], [5.0, 7.5]], [[5.0, 0.5], [6.0, 0.5]], [[5.0, 7.5], [6.0, 7.5]], [[6.0, 0.5], [7.0, 0.5]], [[6.0, 7.5], [7.0, 7.5]], [[7.0, 0.5], [7.5, 1.0]], [[7.5, 2.0], [7.5, 1.0]], [[7.5, 3.0], [7.5, 2.0]], [[7.5, 4.0], [7.5, 3.0]], [[7.5, 5.0], [7.5, 4.0]], [[7.5, 6.0], [7.5, 5.0]], [[7.5, 7.0], [7.5, 
6.0]], [[7.0, 7.5], [7.5, 7.0]]]

我希望将其用于查找更复杂的形状，如下所示：

[在第二张图片中，我在绿色形状的内部是红色。理想情况下，红色形状应位于红色形状之内。

致mkrieger1：我想这要视情况而定。这些图以顺时针方式连接。我真的不知道如何描述它，但是也许链接中的图形显示了这一点。两行都有一个小错误（如右图所示，在第一幅图中可以看到）。

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

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

Answer 1

如Prune所建议的，shapely程序包具有您所需要的。虽然您可以将线环视为图形，但将线环视为嵌入2D平面中的多边形更为有用。