Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Уайлера Атертона

Алгоритм Уайлера — Атертона используется в компьютерной графике для клиппинга отсекаемого многоугольника по отсекающему многоугольнику, также называемому окном. Отсекаемый и отсекающий многоугольники могут быть невыпуклыми. Алгоритм применим только для плоских фигур.

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

Алгоритм может быть модифицирован для объединения двух многоугольников.

Алгоритм

• Из координат вершин многоугольников A и B составляются два списка.
• Вершины в каждом из списков помечаются в соответствии с тем, находятся ли они внутри другого многоугольника или нет.
• В оба списка добавляются точки пересечения многоугольников; между совпадающими точками в разных списках устанавливаются двусторонние связи.
• Если ни одного пересечений не найдено, возникает одна из следующих ситуаций:
  • A внутри B — вернуть A при отсечении, B при объединении.
  • B внутри A — вернуть B при отсечении, A при объединении.
  • A и B не пересекаются — вернуть пустое множество при отсечении, A&B при объединении.
• Составляется список точек пересечения, в которых граница многоугольника A при обходе входит в многоугольник B. Следуя из каждой такой точки по часовой стрелке вдоль границ обоих многоугольников A и B, можно найти множество областей пересечения. В случае, когда A и B выпуклы, многоугольник пересечения только один. Таким же образом можно найти и объединение многоугольников, в этом случае обход нужно начинать с выходных точек.