Отсечение отрезка на плоскости

По прямоугольнику (xmin,ymin,xmax,ymax).

Самое простое – последовательное отсечение по всем сторонам прямоугольника. Сначала – проверка, пересекает или нет, потом деление, в конце – замена координат одной из вершин отрезка на новые.

Уравнение прямой, проходящей, через две точки. , тогда, координата пересечения с вертикальной границей окна:

y=y1+(y2-y1)*(xmin-x1)/(x2-x1).

Алгоритм половинного деления

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

Алгоритм Сазерленда-Коэна

Для ускорения отсечение предлагается ввести коды для точек отрезка (YmaxYminXmaxXmin). Затем, если логическое «И» над кодами отрезка не равно нулю, то отрезок полностью невидим. Если оба кода (логическое «ИЛИ») равны 0 то отрезок полностью внутри окна, иначе – нужно отсекать по тем сторонам, для которых биты логического «ИЛИ» кодов единичные. При получении очередной точки для нее считается код и история повторяется.

Алгоритм Кируса-Бэка

Наиболее распространенный алгоритм, подходит для выпуклого окна произвольной конфигурации. Отрезок отсекают последовательно по всем сторонам окна. Для точек отрезка находят расстояние до прямой, если оба положительные, то отрезок полностью невидим, если оба отрицательные, то он не пересекается с этой прямой, иначе – нужно найти точку пересечения, коэффициент k=d1/(d1-d2). P=A+k*(B-A).

Коэффициент k получается из подобия треугольников. , , ,

Невыпуклые окна разбивают на выпуклые и производят отсечение по ним.

Но можно и не вычислять точки пересечения при каждом пересечении. Достаточно только вычислить значение параметра, в котором происходит пересечение (k) и укорачивать интервал, который соответствует части отрезка, находящейся внутри окна. В начале этот интервал k1=0, k2=1, затем при пересечении в точке k, модифицируется коэффициент, соответствующий той точке, которая лежит вне окна (di>0) либо k1=max(k1,k), либо k2=min(k2,k). Если после пересечения окажется, что k1>k2, значит, отрезок находится полностью вне окна. После того, как обработаны все границы окна – следует рассчитать точки для k1,k2. Экономим на расчете точек, теряем на лишних расчетах коэффициентов пересечения.

Отсечение полигона выпуклым окном

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

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

Алгоритм Вейлера-Азертона

Это алгоритм отсечения полигона произвольным окном, можно сказать отсечение одного полигона другим. Сначала находятся все точки пересечения ребер полигонов. Они делятся на входящие (в окно) и выходящие (относительно границ окна). Эти точки разделяют ребра окна и полигона на несколько ребер. Затем, начиная с одной из точек пересечения последовательно заносим ребра в новый полигон. Если это точка входа – берутся ребра с полигона, иначе - с окна. Если встречается точка пересечения – происходит переключение полигона, с которого берутся ребра (точки всегда чередуются). Так происходит до тех пор, пока не встретится точка, с которой был начат обход. Т.к. внутренних контуров может быть несколько, то следует проверить, все ли точки пересечения были пройдены, и если не все, то может понадобится несколько таких циклов.

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

Алгоритм разбиения произвольного полигона на выпуклые

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

1. Полигон представляется, как набор контуров. Каждый контур – циклический список ребер. Может быть много внутренних и внешних контуров, в конце должны получиться только контуры выпуклых полигонов.

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

3. Если не найдено ни одного вогнутого угла – завершаем работу.

4. Создаем два противоположно направленных ребра и добавляем их к контурам. Нужно отметить, что если мы соединяем точки одного контура, то он разделяется на два контура, а если точки с разных контуров – два контура сливаются в один.

5. Продолжаем искать хорды.

В худшем случае алгоритм требует времени O(N³), где N – количество ребер в полигоне, но если алгоритм немного модифицировать (например, обходить не все вершины, а только вогнутые) то он становится достаточно эффективным.