Как избежать сложного многоугольника при оптимизации его вершин?

Question

Предположим, есть набор двумерных точек, представляющих исходный простой многоугольник. Теперь я хочу оптимизировать позиции каждой точки в соответствии с некоторой функцией стоимости. Но это может сделать комплекс многоугольника, то есть многоугольник пересекается с самим собой. Как я могу избежать этого? Спасибо!

Answer 1

Если многоугольник можно считать выпуклым, то это просто.Просто рассчитайте углы между каждой стороной и следующей стороной.Каждый угол должен быть от 0 до 180 градусов для выпуклого многоугольника.Сумма этих углов хорошо известна для замкнутого многоугольника с N сторонами.Это приведет к простой ограниченной оптимизации.(На самом деле, вы можете записать эти ограничения в «более простой» форме, чем вычисление углов с помощью тригонометрической функции. Перекрестных произведений будет достаточно.)

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