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

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]]]

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

]

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

我可以附上一个完整的可行示例，但是它将包括我的整个算法，并且页面长，并且具有许多功能！我基本上想在函数中使用输入（V1，E1）和（V2，E2），这将告诉我一个是否在另一个内部。

Answer 1

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

• [G1和G2是其边缘形成简单多边形/凸包的图形，我们试图确定G2是否在G1内。
• 在您的空间中选择任意方向。
• 对于G2中的每个顶点，朝您选择的方向投射射线（从一个点开始并在一个方向上无限延伸的线）。>
• [如果顶点（a）与G1的边缘相交，而OR（b）位于这些边缘之一上的次数是奇数倍->顶点在G1的内部。对于所有其他情况，顶点不在G1内。
• [仅当G2的每个顶点都在G1内时，G2才在G1内。

这将涉及以下子任务-获取G2的顶点列表-投光-检测和计数交叉点

如果您遍历每个顶点并通过将用于表示矩阵上G2的值添加到您选择的方向上的所有像元来画一条线，则交集值将只是用于计算的值之和代表G1和G2。在当前情况下，该值将为1，与空白空间相同。如果只允许正值或负值代表图形，而0代表空白，则可以解决此问题。

最后，要检测en边缘是否位于图形上，应在遍历顶点之前运行相交检查。如果您的任何一个顶点在射线投射之前产生了相交值，它将告诉您它在G1的边缘上。标记此顶点在G2内，将其从需要检查的顶点列表中删除，并记下该值，这样它就不会算作所有的额外交集

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