确定顶点是否位于集合顶点内

Question

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

例如，如果我有一个图 G1，它是一个正方形，其 'corner' 个顶点（除其他外，但为简单起见减少了）{(1,1), (1,6), (6 ,6), (6,1)}，则由角顶点 {(2,2), (2,5), (5,5), (5,2)} 定义的较小正方形 G2 将位于 G1 内。第三个图 G3 由角 {(3,3), (3,4), (4,4),(4,3)} 定义。我的算法为此配置生成下图：

一个以 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]]]

同样，这给出了如下所示的图表

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

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

这些图是按顺时针方向连接的。我真的不知道如何描述它，但也许 link 中的图表显示了这一点。其中两条线存在错误（如您在右上角的第一个图中所见），但顶点是正确的。

希望对您有所帮助！我可以附上一个完整的可行示例，但它会包括我的整个算法，而且会很长，而且有很多功能！我基本上想将 g1、g2 和 g3 中的任一个输入用于函数（或 e1、e2 和 e3）。该函数会告诉我 g3 包含在 g2 中，g2 包含在 g1 中。

Answer 1

你的问题确实和网络关系不大。从根本上说，您正在尝试确定一个点是否在由有序点列表描述的区域内。最简单的方法是创建 matplotlib Path，它有一个 contains_point 方法（还有一个 'contains_points` 方法可以同时测试多个点）。

#!/usr/bin/env python
"""
Determine if a point is within the area defined by a path.
"""
import numpy as np
import matplotlib.pyplot as plt

from matplotlib.path import Path
from matplotlib.patches import PathPatch

point = [0.5, 0.5]
vertices = np.array([
    [0, 0],
    [0, 1],
    [1, 1],
    [1, 0],
    [0, 0] # NOTE the repetition of the first vertex
])

path = Path(vertices, closed=True)

print(path.contains_point(point))
# True

# plot to check visually 
fig, ax = plt.subplots(1,1)
ax.add_patch(PathPatch(path))
ax.plot(point[0], point[1], 'ro')

请注意，如果一个点直接在路径上，则它不在路径内。但是，contains_point 支持 radius 参数，允许您向区域范围添加增量。您需要正增量还是负增量取决于点的顺序。 IIRC，radius 将路径向左移动，但不要引用我的话。

确定顶点是否位于集合顶点内

Determining if vertices lie within a set vertices

python

graph

vertices

image-segmentation

networkx