Минимизировать вершины многоугольника

Question

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

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

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

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

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

Answer 1

Изменить. О, смотрите, Упрощающие полигоны

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

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

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

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

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

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

Answer 2

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