Создать график связанных выпуклых многоугольников

Question

Я пытаюсь взять плотный граф точек, таких как this , и превратить его в граф связанных выпуклых многоугольников. Полигоны должны быть максимально большими и максимально простыми, оставаясь подключенными. Результирующий граф будет использоваться для поиска пути. Кто-нибудь может указать мне правильное направление?

Answer 1

Очень раздражает, что я не могу публиковать ссылки.Трудно быть скрытным и единственным случайным участником.

В итоге я использовал следующие приемы:

Сначала создайте дистанционное преобразование.Я использовал алгоритм, описанный здесь [не могу связать], в результате чего получилось изображение, похожее на это [не могу связать].Затем создайте преобразование DT в водораздел, чтобы разделить его на области.Это требует некоторой работы, но в настоящее время выглядит следующим образом [невозможно связать] Затем используйте средние точки полилиний, соединяющих каждую пару областей, для создания графика путевых точек.

Результат

Разделение водораздела еще не является идеальным, обратите внимание, что псевдоним вызывает полосу, но я получаю 181 область и 281 путевую точку для этой карты 128x128.

Answer 2

Это не то, что вы просили, но вот некоторые другие идеи для решения этой проблемы планирования 2D-маршрута:

• Используйте A *. Это дает кратчайший путь без столкновений. Производительность может быть в порядке, даже без упрощения растрового изображения.

• Используйте дорожную карту на основе выборки . Это другое дискретное представление, чем полигоны. Поскольку ваше пространство поиска мало, вы можете пройтись по всему растровому изображению, чтобы убедиться, что каждая точка может быть подключена к дорожной карте. Если compact дорожная карта важна (но короткие пути не важны), можно использовать технику visibility roadmap .

Так как вам все равно приходится иметь дело с представлением и поиском графиков, эти методы кажутся намного проще, чем извлечение полигонов. Я выкопал несколько вопросов по этой проблеме:

• Преобразовать растровое изображение в полигон
• Как преобразовать растровое изображение простой формы в вектор

Когда пространство отображено полигонами (возможно, с помощью инструмента), оно может быть разбито на выпуклые полигоны или другое представление, которое можно искать. Это также обсуждается LaValle:

• Вертикальное (трапециевидное) разложение клеток
• дорожные карты по кратчайшему пути