如何确定一个图是否位于另一个图内（笛卡尔网格上的顶点）

Question

在我的算法中，我正在寻找不同阈值的图表。每个图 G = (V,E)。这些是使用广度优先搜索找到的无向图。我想确定另一个图 G' = (V',E') 的顶点是否在图 G 内。我不熟悉图算法，所以如果您想查看代码或更详尽的解释，请告诉我。

例如，如果我有一个图 G，它是一个正方形，具有 'corner' 个顶点（除其他外，但为简单起见减少）（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]]]

我希望用它来寻找更复杂的形状，如下所示：

]

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

我可以附上一个完整的可行示例，但它会包括我的整个算法，而且会很长，而且功能很多！我基本上想将输入 (V1, E1) 和 (V2, E2) 用于函数，这会告诉我一个是否位于另一个中。

Answer 1

您可以使用光线投射来解决这个问题。这是处理此问题的常用方法，因此您也可以在其他地方找到有关它的更多信息。算法的一般描述是这样的：

G1 和 G2 是图，其边缘形成一个简单的 polygon/convex 外壳，我们试图确定 G2 是否在 G1 内部。
在 space 中选择任意方向。
对于 G2 中的每个顶点，向您选择的方向投射一条射线（一条从一个点开始并在一个方向上无限延伸的线）。
如果顶点 (a) 与 G1 的一条边相交奇数次，或者 (b) 位于其中一条边上 --> 顶点在 G1 内部。对于所有其他情况，顶点不在 G1 内部。
G2 在 G1 内部，前提是 G2 的每个顶点都在 G1 内部。

这将涉及以下子任务 -获取G2的顶点列表

-投射光线

-检测并计算交叉点

如果您遍历每个顶点并通过将您用来表示矩阵上 G2 的值添加到您选择的方向上的所有单元格来绘制一条线，则交点值将只是您选择的值的总和用于表示 G1 和 G2。在您当前的情况下，因为您正在制作正方形，所以这有点问题。可能有更好的算法来绘制对象或检测交叉点的更好方法。

最后，为了检测边是否位于图上，您应该运行在遍历顶点之前检查交叉点。如果您的任何顶点在光线投射之前产生交点值，它会告诉您它位于 G1 的边缘。标记该顶点在 G1 内部，将其从需要检查的顶点列表中删除，并记下该值，因此它不会算作所有

的额外交集

您可能需要调整此算法，具体取决于您是要将边上的节点计算为内部还是外部，或者是否需要图形内部的所有顶点，但我希望这是一个有用的开始。

如何确定一个图是否位于另一个图内（笛卡尔网格上的顶点）

How to determine if one graph lies within another (vertices on a Cartesian grid)

python

graph

image-segmentation

networkx

shapely