Невыпуклые отсекающие области. Алгоритм Вейлера - Айдертона

Внешняя граница обходится по часовой стрелке, а внутренняя - против.

При обходе вершин многоугольника в порядке их следования в соотв. списке внутр. обл. будут расположены справа от границы.

Если границы пересекаются, то точки пересечения образуют пары. Одно пересечение - когда ребро обр. многоугольника входит внутрь отсекателя, а другое - когда оно выходит из отсекателя.

Основная идея:

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

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

C₁ C₂ C₃ C₄ - отсекатель

S - исходный многоугольник

I - точки пересечения

Вершина исходного

многоугольника Вершина отсекателя

S₁ C₁

I₂ I₁

I₃ I₂

S₂ C₂

I₄ I₃

S₃ I₄

I₅ C₃

S₄ I₅

I₆ I₆

I₇ C₄

S₅ I₇

I₈ I₈

S₆ C₁

I₁

S₇

S₁

I₂ I₃ I₄ S₃ I₅ I₆ I₇ I₈ S₆ I₁ I₂ - Результат внутреннего отсечения

Отсечение происходит таким образом, что число многоугольников минимально.

Дата добавления: 2014-01-07