Алгоритмы отсечения многоугольников

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

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

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

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

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

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

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

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

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

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

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

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