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

Определение факта выпуклости многоугольника

Внутреннее и внешнее отсечение

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

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

Для работы с алгоритмом Кируса–Бека надо прежде всего убедиться, что окно является выпуклым, а потом вычислить внутренние нормали к каждой его стороне. Факт выпуклости или невыпуклости окна можно установить путем вычисления векторных произведений его смежных сторон (рис.14).

Выводы, которые можно сделать из анализов знаков этих произведений:

- все знаки равны нулю – многоугольник вырождается в отрезок;

- есть как положительные, так и отрицательные знаки – многоугольник не выпуклый;

- все знаки неотрицательные – многоугольник выпуклый, а внутренние нормали ориентированны влево от его контура;

все знаки неположительные – многоугольник выпуклый, а внутренние нормали ориентированны вправо от его контура.

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

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

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

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

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

Когда после поворота его вершина V₂ совпадет с началом координат, V₃ ляжет на положительной оси x, знак ординаты V₄ будет отрицательным, значит многоугольник невыпуклый. Разрезание его осью x дает многоугольник V₃V₄V₅ ниже оси x и V₂V₅V₁ – выше оси x (рис.15).

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