Я пытаюсь взять плотный граф таких точек, как this, и превратить его в график связанных выпуклых многоугольников. Полигоны должны быть как можно большими и простыми, оставаясь при этом подключенными. Полученный граф будет использоваться для поиска пути. Может кто-то указать мне верное направление?Сгенерировать график связанных выпуклых полигонов
Это очень раздражает, что я не могу размещать ссылки. Трудно быть lurker & только случайным участником.
Я закончил с использованием следующих методов:
Во-первых, создать расстояние преобразования. Я использовал описанный здесь алгоритм [не может ссылаться], в результате чего изображение вроде этого [не может быть связано]. Затем создайте преобразование водораздела DT, чтобы разбить его на области. Это требует некоторой работы, но в настоящее время выглядит следующим образом: [невозможно связать]. Затем используйте середины полилиний, соединяющих каждую пару областей, чтобы создать граф путевой точки.
Водораздел перегородки не совершенен, обратите внимание на ступенчатость вызывает полосатость, но я в конечном итоге с 181 районами и 281 путевых точек для этой 128x128 карте.
Это не то, что вы просили, но вот некоторые другие идеи для решения этой 2D задачи планирования пути:
Используйте *. Это дает кратчайший путь столкновения. Производительность может быть в порядке, даже без упрощения растрового изображения.
Использовать sampling-based roadmap. Это другое дискретизированное представление, чем многоугольники. Так как ваше пространство поиска мало, вы можете пересечь все растровое изображение, чтобы убедиться, что каждая точка может быть подключена к дорожной карте. Если важна карта дороги (но короткие пути нет), можно использовать метод visibility roadmap.
Поскольку вы все равно должны иметь дело с представлением графа и графическим поиском, эти методы кажутся намного проще, чем извлечение многоугольника. Я откопал некоторые SO вопросы этой проблемы:
Когда пространство было нанесено на карту многоугольников (возможно, с помощью инструмента), она может быть разбита на выпуклые многоугольники или другое представление, которое можно найти. Это также обсуждается Лаваль:
Я не могу себе представить, что раньше этого не спрашивали. Пожалуйста, сначала найдите SO, это, вероятно, даст вам некоторые идеи. Или вы можете сформулировать свой вопрос лучше, объяснив, почему найденные решения не соответствуют вашим требованиям. –
Выглядит подозрительно, как звездная карта ... –
Это точно карта StarCraft. Это сверху вниз их навигационная сетка, настройка для использования в качестве карты 2D-столкновений. Я могу сделать локальное предотвращение столкновений, используя потенциальные поля, но мне нужно настоящее решение для поиска пути, чтобы избежать локальных оптимумов. По существу мне нужны выпуклые многоугольники, так что я могу использовать средние точки общих ребер для прохода через путь. Треугольники тоже будут работать, но в итоге получатся больше очков. – Anthony