Образовательный портал Claw.ru
Всё для учебы, работы и отдыха
» Шпаргалки, рефераты, курсовые
» Сочинения и изложения
» Конспекты и лекции
» Энциклопедии

O(n)

Прослеживание контура

Произвольной формы

Сравнение положения точки по отношению к прямой

Пересечение прямой с отрезком другой прямой

O(n)

Как видно из таблицы 1, при разрезании отрезка многоугольным произвольным контуром необходимо пользоваться алгоритмом прослеживания контура. Ж.Эгрон отмечает, что в частном случае, когда окно имеет форму прямоугольника, метод Сазерленда (дихотомический вариант) наилучшим образом приспособлен для реализации на жесткой логике. В ином случае аппаратная реализация на программируемом устройстве лучше согласуется с алгоритмом Павлидиса, причем степень преимущества определяется характеристиками сцены (содержанием в ней вершин и горизонтальных линий). Следовательно, если многоугольник выпуклый, то целесообразно пользоваться более специализированными алгоритмами, например алгоритмом Павлидиса [2,3]. Если же многоугольник представляет собой прямоугольник, стороны которого параллельны осям координат (далее по тексту просто ”прямоугольник”), то процесс определения факта нахождения примитива в многоугольнике пространственной окрестности сводится к элементарным операциям сравнения координат и вычисления середины отрезка.

Проведем сравнительный анализ вариантов описания пространственной окрестности. Оценку способов представления описывающих контуров будем производить с точки зрения времени формирования пространственной окрестности Tф. Процесс формирования пространственной окрестности можно разделить на несколько составляющих:

построение уравнений ограничений;

анализ примитивов на попадание в заданную пространственную окрестность и, если это необходимо, их последующее разрезание.

Время Tур, затрачиваемое ГИС на построение уравнений ограничений, различается для каждого из способов. Так при построении уравнений окружностей (1.а, 1.б) затраты времени минимальны по сравнению с другими методами. Для второго и третьего способов затраты времени почти не отличаются от первого, т.к. количество проводимых вычислений (инициализации соответствующих коэффициентов в уравнениях 2.а, 2.б, 3) пренебрежительно мало. По-другому обстоит дело с формированием уравнений ограничений произвольными многоугольниками. Как видно из предложенного алгоритма, процесс формирования многоугольников контура пространственной окрестности занимает некоторое, значительно превышающее для первых трех случаев, время. И чем больше вершин содержит описываемый контур, тем больший промежуток времени занимает этот процесс. Таким образом, соотношение времен, затрачиваемых на построение уравнений ограничений, имеет следующий вид:

Tур1< Tур2< Tур3

Скачали данный реферат: Shubkin, Jasin, Садовский, Свалов, Анфима, Блохин, Jalunin.
Последние просмотренные рефераты на тему: реферат эволюция, реферат, сочинение ревизор, конспект.



Категории:




Предыдущая страница реферата | 1  2  3  4


Поделитесь этой записью или добавьте в закладки

   



Рефераты от А до Я