Отсечение отрезков и многоугольников

Алгоритм Цируса-Бека

Алгоритм Цируса-Бека [25] отсекает отрезок P1P2, используя его параметрическое представление:

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

Рассмотрим отдельно ребро Ei отсекающего многоугольника. Нормаль к нему ориентируем во внешнюю сторону отсекающего многоугольника, для этого удобно считать, что точки отсекающего контура обходятся против часовой стрелки; тогда если ребро - это $$\overrightarrow{P_{Ei1}P_{Ei2}}$$, то нормаль NEi будет пропорциональна (yEi2-yEi1, xEi1- xEi2), см. рис. 5.3.

Тогда область, отсекаемая прямой, на которой лежит ребро (обозначим ее Li ), соответствует точкам P, для которыхЗдесь и далее (x, y) - скалярное произведение векторов x и y. (P-PEi),NEi) > 0, где PEi - любая точка на ребре Ei. Точка пересечения прямой, на которой лежит отрезок с отсекающей прямой Li, находится из уравнения

((Ps(t) - PEi),NEi) = 0.

Разрешая его, получаем, что

в том случае, если $$(P_2 - P_1,N_{Ei}) \ne 0$$. Если же ((P2 - P1),NEi) = 0 это означает, что отсекаемый отрезок параллелен Li и не существует единственной точки их пересечения. Такие случаи алгоритм игнорирует.

Для алгоритма Цируса-Бека также важно в каком направлении (внутрь отсекающего многоугольника или из него) проходит точка при движении по отрезку от P1 к P2, т.е. при изменении t от 0 до 1. Это определяется знаком ((P2 - P1),NEi). Будем обозначать такие точки пересечения как:

После того как рассчитаны координаты t для всех возможных пересечений с прямыми Li, следует выбрать максимальную координату из потенциально входящих пересечений tВхMax и минимальную из потенциально выходящих tВыхMin. Если прямая, на которой лежит отрезок P1P2, пересекает отсекающий многоугольник, то tВхMax < tВыхMin. В этом случае, если пересечение $$[t_1, t_2] = [t_{ВхMax}, t_{ВыхMin}] \cap [0, 1]$$ непусто, то Ps(t1)Ps(t2) будет искомым отсеченным отрезком. В противном случае отрезок полностью лежит вне отсекаемой области.

Вычислить NEi и взять PEi = PEi1 для каждого ребра.

Отсечь(отрезок P1P2)
{
   if(P1 == P2)
      отсечь как точку;
   else
     {
          D = P2 - P1;
          t_Вх = 0;
          t_Вых = 1;

          foreach( ребро Ei из отсекающего многоугольника )
          {
              dp = (D,NEi);
              if( dp != 0 ) // случай dp == 0 игнорируется
              {

if( dp < 0 )
             {
                 if( t > t_Вх )
                 t_Вх = t;
              }
                   else // dp > 0
                   {
                        if( t < t_Вых )
                        t_Вых = t;
                          }
                  }
        }

          if( t_Вх < t_Вых )
              return отрезок Ps(t_Вх)Ps(t_Вых);
          else
             return '
      }
}

Алгоритм Цируса-Бека также может быть обобщен до случая отсечения отрезка произвольным выпуклым многогранником в трехмерном пространстве.

Алгоритм Лианга-Барского

Алгоритм Лианга-Барского [39] является более эффективным вариантом алгоритма Цируса-Бека в случае, если отсекающий многоугольник - это прямоугольник со сторонами, параллельными осям координат. В этом случае вычисление промежуточных величин упрощается ( P1 = (x1, y1),P2 = (x2, y2) ):

// (xлево, yниз, xправо, yверх) - отсекающий прямоугольник;

Отсечь(отрезок P1P2)
{
    dx = P2.x - P1.x;
    dy = P2.y - P1.y;
 
      if( dx == 0 AND dy == 0 )
         отсечь как точку;
      else
      {
          t_Вх = 0;
          t_Вых = 1;
        
         // Отсечь_t может модифицировать t_Вх и t_Вых
        // ( означает передачу по адресу)
        if( Отсечь_t( dx, xлево - P1.x, t_Вх, t_Вых ) )
          if( Отсечь_t( -dx, P1.x - xправо, t_Вх, t_Вых ) )
          if( Отсечь_t( dy, yниз - P1.y, t_Вх, t_Вых ) )
          if( Отсечь_t( -dy, P1.y - yверх, t_Вх, t_Вых ) )
                {
                    if( t_Вх > 0 )
                     {

                           P1.x = P1.x + dx*t_Вх;
                           P1.y = P1.y + dy*t_Вх;
                      }
                               if( t_Вых < 1 )
                                 {
                                    P2.x = P1.x + dx*t_Вых;
                                    P2.y = P1.y + dy*t_Вых;
                                  }
                                      return отрезок P1P2;
                                        }
             return '
       }
}

// Проверить пересечение с ребром
// denom, num - 'знаменатель' и 'числитель' выражения (5.2)
// t_Вх и t_Вых передаются по адресу (обозначено *),
// они могут быть модифицированы;
// возвращает логическую переменную:
// true - продолжать отcечение
// false - закончить отcечение,
// отрезок полностью вне прямоугольника
bool Отсечь_t( denom, num, *t_Вх, *t_Вых )
{
       if( denom > 0 ) // Потенциально входящее пересечение
       {
              t = num / denom;
              if( t > t_Вых )
                     // t_ВхMax > t_ВыхMin: отрезок полностью снаружи
                     return false;
              else if( t > t_Вх ) // Модифицируем t_Вх
                     t_Вх = t;
       }
       else if( denom < 0 ) // Потенциально выходящее пересечение
       {
       t = num / denom;
       if( t < t_Вх )
              // t_ВхMax > t_ВыхMin: отрезок полностью снаружи
              return false;
       else if( t < t_Вых ) // Модифицируем t_Вых
              t_Вых = t;
       }
       else if( num > 0 )
              // отрезок параллелен ребру и полностью снаружи
              return false;

       return true;
}

Эксперименты, проведенные авторами на случайных наборах данных [39], показали, что их алгоритм на 25-62% быстрее алгоритма Сазерлэнда-Коэна. Поэтому в настоящее время алгоритм Лианга-Барского получил большее распространение.

5.3. Отсечение многоугольников

Рассмотрим теперь задачу отсечения многоугольника относительно прямоугольника и алгоритм Сазерлэнда-Ходжмана [48], позволяющий проводить такое отсечение.

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

Пусть многоугольник задан своими вершинами: P1P2 . . . PN. $$\overrightarrow{P_1P_2}, . . . \overrightarrow{P_kP_{k+1}}, . . . \overrightarrow{P_{N-1}P_N}, \overrightarrow{P_NP_1}$$ - направленные ребра этого многоугольника.

Относительно произвольной полуплоскости $$\Pi$$ каждое направленное ребро $$\overrightarrow{P_kP_{k+1}}$$ может находиться в следующих положениях:

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

Отсечь P[1]...P[N] относительно полуплоскости
{
       //L - граница полуплоскости
       for( i = 1; i <= N; i++ )
       {
              j = i+1;
              if( j == N+1 )
                     j = 1;
              if( P[i]P[j] пересекает L )
             {
                     I = пересечение( P[i]P[j], L );
                     вывести(I);
              }
              if( P[j]видима )
                     вывести(P[j]);
       }
}

Данный алгоритм выводит вершины отсеченного многоугольника в порядке обхода. Пример работы алгоритма Сазерлэнда-Ходжмана приведен на рис. 5.5.

После проведения отсечения четырьмя полуплоскостями получается многоугольник, отсеченный относительно прямоугольника. Заметим, что данный алгоритм очевидным образом применим для отсечения любого выпуклого многоугольного окна - достаточно представить это окно в виде пересечений полуплоскостей.

Практически единственным недостатком алгоритма Сазерлэнда-Ходжмана является не совсем корректная обработка случаев, когда результатом отсечения являются несколько изолированных многоугольников. Результат алгоритма Сазерлэнда-Ходжмана в этом случае содержит многоугольники и связывающие их отрезки (рис. 5.6).