Минимизировать вершины многоугольника - PullRequest
9 голосов
/ 05 марта 2009

Каков хороший алгоритм для уменьшения количества вершин в многоугольнике без изменения его внешнего вида?

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

Вывод: многоугольник с гораздо меньшим количеством вершин, который все еще очень похож на оригинал: например, что-то пригодное для обнаружения столкновений (не обязательно выпуклое).

Редактировать: решение этого было бы похоже на поиск многосегментной линии наилучшего соответствия на графике. Это называется Сегментированные наименьшие квадраты в моей книге алгоритмов.

Edit2: алгоритм Дугласа Пекера - это то, чего я действительно хочу.

Ответы [ 2 ]

5 голосов
/ 05 марта 2009

Редактировать: О, смотри, Упрощение полигонов

Вы упомянули обнаружение столкновений. Вы можете пойти очень просто и рассчитать ограничивающую выпуклую оболочку вокруг него.

Если вы заботились о вогнутых областях, вы можете рассчитать вогнутую оболочку, взяв центр тяжести своего многоугольника и выбрав точку для начала. От начальной точки вращайтесь вокруг центроида, находя каждую вершину, которую хотите сохранить, и назначая ее в качестве следующей вершины в ограничивающем корпусе. Сложность алгоритма зависит от того, как вы определили, какие вершины сохранить, но я уверен, что вы уже подумали об этом. Вы можете выбросить все свои вершины в ведра в зависимости от их расположения относительно центроида. Когда сегмент заполнен больше чем произвольным числом вершин, вы можете разделить его. Затем возьмите среднее значение вершин в этом ведре в качестве вершины для использования в вашем ограничивающем корпусе. Или забудьте про ведра, и когда вы двигаетесь вокруг центроида, выбирайте точку, только если она находится на расстоянии, превышающем заданное расстояние от последней точки.

На самом деле, вы могли бы просто использовать все вершины в вашем многоугольнике как «облако точек» и вычислить вогнутую оболочку вокруг этого. Я поищу ссылку на алгоритм. В худшем случае это будет полностью выпуклый многоугольник.

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

Если вы заботитесь о том, чтобы многоугольник действительно выглядел одинаково, даже в случае самопересекающегося многоугольника, тогда потребовался бы другой подход, но он не похож на тот, который необходим, поскольку вы спрашивали об обнаружении столкновения.

Эта запись содержит некоторые подробности о выпуклой части корпуса.

1 голос
/ 05 марта 2009

Там много материала. Просто поищите в Google такие вещи, как «уменьшение сетки», «упрощение сетки», «оптимизация сетки» и т. Д.

...