Разбиение невыпуклых многоугольников

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

- для каждой i-й вершины многоугольника надо так ее перенести, чтобы она совпадала с началом координат;

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

- проанализировать знак ординаты (г+-2)-й вершины, если он

неотрицателен, то многоугольник выпуклый в (i+1)-й вершине, если отрицательный - невыпуклый, разбить его;

- многоугольник разрезается вдоль положительной полуоси х, т.е. находятся все его такие стороны, которые пересекаются с осью х, образуется два новых многоугольника: один состоит из вершин лежащих выше оси.г и ближайшей к началу координат точки пересечения с x> xi+1, второй - из вершин лежащих ниже оси х.

Когда после поворота его вершина V2 совпадет с началом координат, Уз ляжет на положительной оси х, знак ординаты V4 будет отрицательным, значит многоугольник невыпуклый. Разрезание его осью х дает многоугольник V3V4V5 ниже оси х и V2V5V1) - выше оси х (рис. 15).

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