Определение, если вершины l ie в пределах набора вершин

Question

В моем алгоритме я нахожу графики на разных порогах. Каждый граф G = (V, E). Это неориентированные графики, найденные с использованием поиска в ширину. Я хотел бы определить, есть ли вершины другого графа G '= (V', E ') l ie в графе G. Я не знаком с алгоритмами графа, поэтому, пожалуйста, дайте мне знать, если вы хотите увидеть код или более подробное объяснение.

Например, если у меня есть граф G1, представляющий собой квадрат с «угловыми» вершинами (среди прочего, но уменьшенный для простоты) {(1,1), (1,6), (6,6), (6,1)}, тогда меньший квадрат G2, определенный угловыми вершинами {(2,2), (2,5), (5,5), (5,2)}, будет l ie в пределах 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]]] 

Опять же, это дает графики, которые выглядят следующим образом

Это реальные данные, над которыми я работаю. Более сложные формы.

Вот, например, внутри у меня красная фигура внутри зеленой фигуры. В идеале, красные фигуры будут в пределах красных фигур. Они будут сгруппированы в один объект (скажем, массив графиков).

Графики связаны по часовой стрелке. Я действительно не знаю, как это описать, но, возможно, графики в ссылке показывают это. На двух линиях есть ошибка (как вы можете видеть на первом графике, в верхнем правом углу), но вершины верны.

Надеюсь, это поможет! Я могу приложить полный работоспособный пример, но он будет включать весь мой алгоритм и будет длиной в страницы, со многими функциями! Я в основном хочу использовать либо входные данные g1, g2 и g3 в функцию (или e1, e2 и e3). Функция скажет мне, что g3 содержится в 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, который позволяет добавить приращение к экстенту области. Нужно ли вам положительное или отрицательное приращение зависит от порядка точек. IIR C, radius сдвигает путь влево в направлении пути, но не указывайте меня на этом.