Продолжает идею алгоритма Лианга-Барски для окна видимости в виде выпуклого многоугольника с вершинами F1 … Fn, расположенными по часовой стрелке.
Основан на параметрическом представлении отрезка. Строим n неравенств Pit≤Qi для n-угольника.
Рассмотрим i-ю сторону: [Fi,Fi+1].
Находим внутреннюю нормаль Ni.
(Ni,FiFi+1) = 0
nx(xi+1-xi)+ny(yi+1-yi) = 0
Положим nx=1; ny=(xi-xi+1)/(yi+1-yi). (Знаменатель может быть 0, если грань горизонтальная, нормаль вертикальная).
После нахождения нормали нужно определить, внутренняя она или внешняя.
Если (N, Fi-1Fi) < 0 то нормаль внутренняя. Если >0, умножаем нормаль на -1.
Нашли внутреннюю нормаль.
Pi=(Ni,(V1-V0))
Если (Pi > 0) то увеличиваем t0, иначе уменьшаем t1.
Если Pi = 0, то грань коллинеарна с вектором.
Qi(t)=(V(t)-Fi, N)
Qi(t)<0; угол больше 90’, точка снаружи
Qi(t)>0; точка внутри
Qi(t)=0; точка лежит на стороне многоугольника.
Решая уравнение Qi(t)=0, получим t, обозначающее пересечение отрезка с гранью.
Если Pi>0, то это t — минимальное t0.
Если Pi<0, то это t — максимальное t1.
Если Pi=0, то отрезок параллелен.
Qi > 0 — продолжаем, переходим к следующему неравенству.
Qi < 0 — отрезок невидим.
Qi=(V0-Fi, Ni)
Отсечение выпуклым многоугольником любого многоугольника.
В цикле рассмотрим стороны отсекающего многоугольника. Каждый раз отрезаем по кусочку прямой. Во внутреннем цикле рассмотрим вершины отсекаемого многоугольника и формируем новый массив вершин.
У каждого ребра может быть четыре состояния:
● Ребро видимо
● Ребро выходит из области видимости
● Ребро невидимо
● Ребро входит в область видимости.
На каждом шаге рассматриваем Pi-1,Pi. S — последняя добавленная в результат вершина. Если [S,Pi] полностью видимо, добавляем Pi в результат, S=Pi. (P1P2 - полностью видимо).
Если отрезок выходит, точку пересечения (A) добавляем как S. (P2P3).
Если ребро невидимо, ничего не добавляем (P3P4).
Если ребро входит, добавляем и точку пересечения (B), и конец ребра (P4,P5).