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

Question

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

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

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

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

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

Answer 1

Edit: О, смотрите, Simplifying Polygons

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

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

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

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

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

В этом post есть некоторые сведения о выпуклой части корпуса.

Answer 2

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