Центральный Дом Знаний - Алгоритм Уайлера — Атертона

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Уайлера — Атертона

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

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

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

  • Из координат вершин многоугольников A и B составляются два списка.

  • Вершины в каждом из списков помечаются в соответствии с тем, находятся ли они внутри другого многоугольника или нет.

  • В оба списка добавляются точки пересечения многоугольников; между совпадающими точками в разных списках устанавливаются двусторонние связи.

  • Если ни одного пересечений не найдено, возникает одна из следующих ситуаций:

    • A внутри B — вернуть A при отсечении, B при объединении.

    • B внутри A — вернуть B при отсечении, A при объединении.

    • A и B не пересекаются — вернуть пустое множество при отсечении, A&B при объединении.

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

Loading

Календарь

«  Сентябрь 2019  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
30

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24