Как определить, лежит ли один граф внутри другого (вершины на декартовой сетке)

Question

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

Например, если у меня есть граф G, представляющий собой квадрат с «угловыми» вершинами (среди прочего, но уменьшенный для простоты) из (0,0), (0,8), ( 8,8) и (8,0), то меньший квадрат, определенный угловыми вершинами (2,2), (2,4), (4,4) и (4,2), будет l ie в пределах 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]]]

Я надеюсь использовать его для поиска более сложных фигур, таких как:

]

На втором рисунке у меня красная фигура внутри зеленой фигуры. В идеале, красные фигуры должны быть l ie внутри красных фигур.

Я могу приложить полный работоспособный пример, но он будет включать весь мой алгоритм и будет длиной в страницы, со многими функциями! В основном я хочу использовать вход (V1, E1) и (V2, E2) в функции, которая скажет мне, находится ли один внутри другого.

Answer 1

Вы можете использовать приведение лучей, чтобы понять это. Это распространенный метод решения этой проблемы, поэтому вы можете найти дополнительную информацию о нем и в других местах. Общее описание алгоритма таково:

• G1 и G2 - графы, ребра которых образуют простой многоугольник / выпуклый корпус, где мы пытаемся определить, находится ли G2 внутри G1.
• Выберите произвольное направление в вашем пространстве.
• Для каждой вершины в G2 наведите луч (линию, начинающуюся от одной точки и продолжающуюся бесконечно в одном направлении) в выбранном вами направлении.
• Если вершина (a) пересекает ребро G1, то нечетное количество раз OR (b) лежит на одном из этих ребер -> вершина находится внутри G1. Для всех остальных случаев вершина не находится внутри G1.
• G2 находится внутри G1, если только если каждая вершина G2 находится внутри G1.

Это будет включать Следующие подзадачи -Получить список вершин для G2

-Кастинг лучей

-Обнаружение и подсчет пересечения

Если вы l oop через каждую вершину и провести линию добавив значение, которое вы используете для представления G2 в вашей матрице, во все ячейки в выбранном вами направлении, значение пересечения будет просто суммой значений, которые вы используете для представления G1 и G2. В вашем текущем случае, потому что вы делаете квадраты, это немного проблематично c. Может быть лучший алгоритм для рисования объектов или лучший способ обнаружения пересечений.

Наконец, для определения, лежит ли край графа на графе, вы должны выполнить проверку на пересечения ДО того, как вы проведете oop через вершины. Если какая-либо из ваших вершин выдает значение пересечения до наведения луча, она скажет вам, что она находится на краю G1. Отметьте, что эта вершина находится внутри G1, удалите ее из списка вершин, которые необходимо проверить, и запишите это значение, чтобы оно не считалось дополнительным пересечением для всех

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