Редактировать: О, смотри, Упрощение полигонов
Вы упомянули обнаружение столкновений. Вы можете пойти очень просто и рассчитать ограничивающую выпуклую оболочку вокруг него.
Если вы заботились о вогнутых областях, вы можете рассчитать вогнутую оболочку, взяв центр тяжести своего многоугольника и выбрав точку для начала. От начальной точки вращайтесь вокруг центроида, находя каждую вершину, которую хотите сохранить, и назначая ее в качестве следующей вершины в ограничивающем корпусе. Сложность алгоритма зависит от того, как вы определили, какие вершины сохранить, но я уверен, что вы уже подумали об этом. Вы можете выбросить все свои вершины в ведра в зависимости от их расположения относительно центроида. Когда сегмент заполнен больше чем произвольным числом вершин, вы можете разделить его. Затем возьмите среднее значение вершин в этом ведре в качестве вершины для использования в вашем ограничивающем корпусе. Или забудьте про ведра, и когда вы двигаетесь вокруг центроида, выбирайте точку, только если она находится на расстоянии, превышающем заданное расстояние от последней точки.
На самом деле, вы могли бы просто использовать все вершины в вашем многоугольнике как «облако точек» и вычислить вогнутую оболочку вокруг этого. Я поищу ссылку на алгоритм. В худшем случае это будет полностью выпуклый многоугольник.
Другая альтернатива - начать с ограничивающего прямоугольника. Для каждой вершины в прямоугольнике найдите расстояние от точки до многоугольника. Для самой дальней вершины разделите ее на две дополнительные вершины и переместите их в некоторые. Повторяйте, пока не будет достигнута некоторая доля вершин или области. Я должен подумать о деталях этого немного больше.
Если вы заботитесь о том, чтобы многоугольник действительно выглядел одинаково, даже в случае самопересекающегося многоугольника, тогда потребовался бы другой подход, но он не похож на тот, который необходим, поскольку вы спрашивали об обнаружении столкновения.
Эта запись содержит некоторые подробности о выпуклой части корпуса.