Алгоритм перекоса полигонов

Question

Какой алгоритм я могу использовать для наклона многоугольника?
Как и перекос следующего:

 ____
|   _|
|__|

В нижнем правом углу вы получите

 ____
|    \
|     \
 \    _|
  \__|

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

Answer 1

Я думаю, что этот алгоритм, который я только что придумал, сделает это:

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

Тогда для каждой вершины:

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

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

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