Я ищу способ автоматического определения районов в городах как полигонов на графике.
Мое определение окрестности состоит из двух частей:
- Блок : область, заключенная между количеством улиц, где количество улиц (ребер) и перекрестков (узлов) составляет минимум три (треугольник).
- Окрестности : для любого данного блока, все блоки, непосредственно прилегающие к этому блоку и сам блок.
Смотрите эту иллюстрацию для примера:
Например, B4 - это блок, определяемый 7 узлами и 6 ребрами, соединяющими их. Как большинство примеров здесь, другие блоки определяются 4 узлами и 4 ребрами, соединяющими их. Кроме того , соседство из B1 включает B2 (и наоборот) , а B2 также включает в себя B3 .
Я использую osmnx для получения уличных данных из OSM.
- Используя osmnx и networkx, как я могу пройти по графику, чтобы найти узлы и ребра, которые определяют каждый блок?
- Как найти соседние блоки для каждого блока?
Я работаю над частью кода, который принимает график и пару координат (широта, долгота) в качестве входных данных, идентифицирует соответствующий блок и возвращает многоугольник для этого блока и окрестности, как определено выше.
Вот код, используемый для создания карты:
import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt
G = ox.graph_from_address('Nørrebrogade 20, Copenhagen Municipality',
network_type='all',
distance=500)
и моя попытка найти клики с разным количеством узлов и степеней.
def plot_cliques(graph, number_of_nodes, degree):
ug = ox.save_load.get_undirected(graph)
cliques = nx.find_cliques(ug)
cliques_nodes = [clq for clq in cliques if len(clq) >= number_of_nodes]
print("{} cliques with more than {} nodes.".format(len(cliques_nodes), number_of_nodes))
nodes = set(n for clq in cliques_nodes for n in clq)
h = ug.subgraph(nodes)
deg = nx.degree(h)
nodes_degree = [n for n in nodes if deg[n] >= degree]
k = h.subgraph(nodes_degree)
nx.draw(k, node_size=5)
Теория, которая может быть актуальной:
Ответы:
Поиск городских кварталов с помощью графика на удивление нетривиален. По сути, это сводится к поиску наименьшего набора наименьших колец (SSSR), что является NP-полной проблемой. Обзор этой проблемы (и связанных с ней проблем) можно найти здесь . На SO, есть одно описание алгоритма, чтобы решить это здесь . Насколько я могу сказать, нет соответствующей реализации в
networkx
(или в Python в этом отношении). Я кратко попробовал этот подход, а затем отказался от него - у меня сегодня не до мозга костей для такой работы сегодня. Тем не менее, я назначу награду любому, кто может посетить эту страницу позже, и опубликую протестированную реализацию алгоритма, который находит SSSR в python.Вместо этого я придерживался другого подхода, используя тот факт, что граф гарантированно является плоским. Вкратце, вместо того, чтобы рассматривать это как проблему с графом, мы рассматриваем это как проблему сегментации изображения. Сначала мы находим все связанные области на изображении. Затем мы определяем контур вокруг каждой области, преобразуем контуры в координатах изображения обратно в долготы и широты.
Имеются следующие определения импорта и функции:
Загрузите данные. Кэшируйте импорт, если проверяете это повторно, иначе ваш аккаунт может быть заблокирован. Говоря из опыта здесь.
Удалите узлы и ребра, которые не могут быть частью цикла. Этот шаг не является строго необходимым, но приводит к более приятным контурам.
Преобразуйте график в изображение и найдите связанные регионы:
Для каждой маркированной области найдите контур и преобразуйте координаты пикселя контура обратно в координаты данных.
Определите все точки исходного графика, которые попадают внутрь (или на) контура.
Выяснить, являются ли два блока соседями, довольно легко. Просто проверьте, имеют ли они общий узел:
источник
Я не совсем уверен, что
cycle_basis
это даст вам окрестности, которые вы ищете, но если это так, то получить граф окрестностей очень просто:источник
nx.Graph(G)
я теряю много информации (Направленность и типа мультиграфа) , так что я имею трудное время проверки вашего ответа, поскольку я не могу показаться , чтобы связать новый графI
с мой оригинальный графикG
.У меня нет кода, но я предполагаю, что как только я окажусь на тротуаре, если я продолжу поворачивать вправо в каждом углу, я буду циклически проходить по краям моего блока. Я не знаю библиотек, поэтому я просто поговорю здесь.
На самом деле это алгоритм, который можно использовать для выхода из лабиринта: держите правую руку на стене и ходите. Это не работает в случае петель в лабиринте, вы просто зацикливаетесь. Но это дает решение вашей проблемы.
источник
Это реализация идеи Хашеми Эмада . Это работает хорошо, если исходная позиция выбрана таким образом, что существует способ сделать шаг против часовой стрелки в крутом круге. Для некоторых ребер, в частности вокруг карты, это невозможно. У меня нет идеи, как выбирать хорошие стартовые позиции или как фильтровать решения - но, может быть, у кого-то еще есть такая.
Рабочий пример (начиная с ребра (1204573687, 4555480822)):
Пример, где этот подход не работает (начиная с края (1286684278, 5818325197)):
Код
источник