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

Question

Я искал в интернете несколько дней, но не смог найти хорошего ответа (или хотя бы того, который имел смысл для меня) на то, что, похоже, должно быть обычным вопросом.Как масштабировать произвольный многоугольник?В частности, вогнутые многоугольники.Мне нужен алгоритм, который может обрабатывать вогнутые (определенно) и самопересекающиеся (если это возможно) многоугольники.Очевидный и простой алгоритм, который я использовал для обработки простых выпуклых многоугольников, - это вычисление центроида многоугольника, перевод этого центроида в начало координат, масштабирование всех вершин и перевод многоугольника обратно в исходное местоположение.

Этот подход не работает для многих (или, возможно, всех) вогнутых многоугольников, поскольку центроид часто выходит за пределы многоугольника, поэтому операция масштабирования также приводит к переводу, и мне нужно иметь возможность масштабировать многоугольник "вplace »без перевода конечного результата.

Кто-нибудь знает метод масштабирования вогнутых многоугольников?Или, может быть, способ найти «визуальный центр», который можно использовать в качестве системы отсчета для операции масштабирования?

Просто чтобы уточнить, я работаю в 2D-пространстве и хотел бы масштабировать свои полигоныиспользуя «визуальный центр» в качестве системы отсчета.Поэтому, возможно, еще один способ задать вопрос: как найти визуальный центр вогнутого и / или самопересекающегося многоугольника?

Спасибо!

Answer 1

Я не уверен, в чем ваша проблема.

Вы работаете в аффинном пространстве и ищете аффинное преобразование для масштабирования вашего полигона?

Если яПравильно, просто напишите матрицу преобразования:

• Матрица масштабирования
• Гомотетия

Апреобразовать полигон с помощью матрицы

Вы можете найти матрицу аффинного преобразования.

надеюсь, это поможет

---

РЕДАКТИРОВАТЬ

если вы хотите сохранить тот же «центр», вы можете просто сделать гомотетию параметра лямбда с центром G = барицентр многоугольника:

он проверяет:

G не будет двигаться, так как это центр гомотетии.

Он все равно проверит соотношение ниже, поэтому он все еще будет барицентром.(вы просто умножаете отношение на лямбду)

в вашем случае G легко определить: G (x, y): (среднее из x значений точек, среднее из y значений точек)

и он должен делать то, что вам нужно

Answer 2

Возможно, Крэйг ищет алгоритм «смещения многоугольника» - где каждое ребро в многоугольнике смещено на заданное значение.Например, для многоугольника, ориентированного по часовой стрелке, смещение ребер влево увеличит размер многоугольника.Если это то, что ищет Крэйг, то об этом уже спрашивали и отвечали здесь - Алгоритм накачивания / спуска (смещения, буферизации) полигонов .

Если вы ищетеготовое решение (с открытым исходным кодом), я также создал библиотеку отсечения ( Clipper ), написанную на Delphi, C ++ и C #, которая включает довольно простую функцию смещения полигонов.

Answer 3

Причина, по которой вы не можете найти хороший ответ, заключается в том, что вы не точны в своих требованиях.Сначала четко определите, что вы подразумеваете под «на месте».Что поддерживается постоянным?

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