Определите, есть ли вершины l ie внутри набора вершин - PullRequest
Новая
       5

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

0 голосов
/ 25 марта 2020

Как я могу определить, лежит ли один граф в другом?

Мой алгоритм работает на следующей матрице: 

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

Чтобы создать два графика:

enter image description here

С вершинами: 

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

1 Ответ

1 голос
/ 30 марта 2020

Как предлагает Prune, пакет shapely имеет то, что вам нужно. Хотя ваши линейные петли можно рассматривать как график, более полезно рассматривать их как многоугольники, встроенные в 2D-плоскость.

Создав Polygon объекты из ваших точек и сегментов ребер, вы можете использовать contains метод, при котором все shapely объекты должны проверять, находится ли один внутри другого.

Вам необходимо отсортировать сегменты ребер по порядку. По часовой стрелке или против часовой стрелки, вероятно, не имеет значения, поскольку shapely, вероятно, обнаруживает внутри и снаружи, создавая точку на бесконечности и гарантируя, что она находится "снаружи".

Вот полный пример с оригинальной парой квадратов из Ваше сообщение: 

from shapely.geometry import Polygon

p1 = Polygon([(0,0), (0,8), (8,8), (8,0)])
p2 = Polygon([(2,2), (2,4), (4,4), (4,2)])

print(p1.contains(p2))

Документация для объекта Polygon: https://shapely.readthedocs.io/en/latest/manual.html#Polygon

и для метода contains в https://shapely.readthedocs.io/en/latest/manual.html#object .Contains

...