русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритм Сазерленда-Ходжмена


Дата добавления: 2013-12-23; просмотров: 1573; Нарушение авторских прав


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

Продолжает идею алгоритма Лианга-Барски для окна видимости в виде выпуклого многоугольника с вершинами 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).

Так идём до конца.



<== предыдущая лекция | следующая лекция ==>
Алгоритм Лианга-Барски | Фрактальная графика


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.