Найдите наименьший многоугольник с определенным ребром на двумерном графе Дейкстры
Извините за плохой английский. Это как-то называется базой минимального цикла графового алгоритма. В настоящее время я работаю над алгоритмом разделения графа на комнаты. Как пример. У меня есть ссылка на график, подобная той, что слева, я хочу сказать, что на графике есть две комнаты, например, красная область и оранжевая область справа.
До сих пор я пытался пройти кратчайшим путем от края, но это не удалось. Например, на левом изображении я начал с края, отмеченного красным, кратчайший путь будет таким же, как на правом изображении.
Я также старался всегда совершать поворот с наибольшим углом по часовой стрелке. Если бы это работало на одном графике, при запуске в противоположном направлении это не помогло бы.
Есть ли какое-нибудь дешевое решение по этому поводу? В настоящее время я быстро попал в ловушку.
Ответы 4
Я бы, вероятно, попробовал алгоритм, где:
- Я отмечаю каждую сторону каждого края как потенциальное помещение;
- Сгруппируйте эти потенциальные комнаты в наборы, которые на самом деле представляют собой одну и ту же комнату (для этого вы можете использовать уже нарисованные пути).
- Откажитесь от внешней части фигуры
- Рассматривайте каждый оставшийся комплект как комнату
Ваш шаг 2 — отмахнуться от реальной проблемы. Какое отношение кратчайшие пути имеют к определению того, какие полуребра принадлежат какой комнате?
Я думаю, что шаг 2 требует разделения графа перед головой. И трудно определить, находится ли сторона ребра за пределами графа.
Вы могли видеть последний пример, который я сделал по часовой стрелке (наименьший угол со знаком). Начиная с верхнего левого края, разные начальные направления дадут разные результаты.
Поскольку вы всегда делаете самый правый поворот (наибольший угол по часовой стрелке), тогда все правые стороны ребер вашего ориентированного пути находятся в общей комнате (или все они находятся снаружи).
Начните с любого ребра, отслеживая, в каком направлении вы рассматриваете ребро. Найдите вершину в конце ребра, затем найдите вершину, выходящую из ребра, с направлением (из этой вершины), которое дает наибольшую величину. подписанный угол против часовой стрелки с краем направления, с которого вы начали. Например, начиная с черного края, вы можете выбрать синий или зеленый край:
В этом случае угол, образованный синим краем, составляет около 95 градусов, а угол, образованный зеленым краем, — около 150 градусов. Итак, вы переходите к зеленому краю. Продолжайте следовать этому правилу, и в конце концов вы вернетесь на исходную позицию. Эти края, взятые по порядку, образуют «комнату» (грань в геометрическом смысле).
Затем начните с нового края, который вы еще не посещали в этом направлении. Каждое ребро будет посещено дважды, по одному разу в каждом направлении. Это будет новая комната.
После того, как вы все закончите, у вас будет по одной краевой петле для каждой комнаты, а также краевая петля для внешней «комнаты». Отфильтруйте это, если хотите; это единственный с областью с отрицательным знаком.
Я думаю, что это то же самое, что и моя последняя попытка в этом вопросе - брать наибольшую подпись по часовой стрелке или против часовой стрелки. В некоторых сценариях это не сработало, как в примере, который я привел на последнем изображении. В настоящее время я пытаюсь сделать что-то вроде первого поворота с наибольшим беззнаковым углом, а затем к первому повороту решить по часовой стрелке или против часовой стрелки - довольно сложно доказать его стабильность.
Нет, это не то же самое. Не стоит выбирать между движением по часовой стрелке и против часовой стрелки. Всегда выбирайте наибольший угол со знаком, и результат будет идти против часовой стрелки.
С помощью python вы можете создать График , получить Cycle_Basis , а затем полигонизировать его элементы:
import networkx as nx
from shapely import Polygon, polygonize, unary_union
rooms = [
poly
for poly in polygonize(
unary_union(
list(
x.exterior for x in map(Polygon, nx.cycle_basis(nx.Graph(edges)))
)
).geoms
).geoms
]
# [
# <POLYGON ((160 20, 10 100, 100 120, 160 20))>,
# <POLYGON ((160 20, 100 120, 10 100, 30 180, 140 220, 180 140, 160 20))>
# ]
Используемый вход:
edges = [
((10, 100), (30, 180)),
((30, 180), (140, 220)),
((140, 220), (180, 140)),
((180, 140), (160, 20)),
((160, 20), (10, 100)),
((10, 100), (100, 120)),
((100, 120), (160, 20)),
]
Спасибо. Хотя я не использую Python, я бы рассматривал исходный код Shapely в крайнем случае.
Наконец-то у меня есть принципы. Для ребра внутри графа, которое должно быть общим для двух базисов окружностей, определение приоритета наибольшего угла со знаком (против часовой стрелки) позволит найти одно из них, ребра которого идут против часовой стрелки. А если отдать приоритет самому маленькому (по часовой стрелке), то будет найдено другое (ребра идут по часовой стрелке). Так что оба варианта будут правильными.
Но для ребра на «ребре» графа, которое содержалось только в одном базисе круга, один из базисов не должен существовать. Таким образом, один из способов расстановки приоритетов даст неправильный результат.
В этом сценарии вы можете найти многоугольник, в результате чего его направление по часовой стрелке не соответствует приоритету поиска пути. Чтобы вы могли изменить расстановку приоритетов и получить правильный результат.
Способ определения того, расположен ли многоугольник по часовой стрелке, можно найти ниже. Как определить, расположен ли список точек многоугольника по часовой стрелке?
Вам нужно только посчитать количество комнат?