Визуализация в ГИС при наличии пространственных ограничений (стр. 2 из 3)
Определяется множество V1 точек пересечения соседних отрезков и множество V2 точек пересечения отрезков и соответствующих окружностей, полученных из неравенств на шаге 3.
Последовательно обходя контур, из множеств V1 и V2 формируется искомое множество V вершин многоугольника, описывающего пространственную окрестность заданного объекта.
В итоге, любой примитив, попадающий в окрестность объекта, должен удовлетворять хотя бы одному из условий:
примитив попадает или пересекает многоугольник, составленный из вершин множества V;
координата примитива удовлетворяет одному из условий неравенств, полученных из неравенств на шаге 3.
Если примитив пересекает контур пространственной окрестности, то его необходимо разрезать в точках пересечения, пользуясь обобщенными на случай разрезаемого примитива алгоритмами разрезания произвольной прямой произвольным многоугольником. Данные алгоритмы описаны в [1] и [2], а более полный анализ приведен в [3]. Представим результаты анализа таких алгоритмов, приведенные в [3].
Таблица 1.
Разрезание отрезков прямой многоугольным окном
| Название метода | Окно | Элементарная операция | Сложность |
| Сазерленда (дихотомический вариант) | Прямоугольное | Сравнение положения точки и контура (с кодированием)Вычисление середины отрезка | O(Log2 (размер отрезка)) |
| Сазерленда-Коэна | Прямоугольное и выпуклое | Кодирование точки относительно контураВычисление точки пересечения отрезков прямых | O(2n),где n - число ребер контура |
| Павлидиса | Прямоугольное и выпуклое | Сравнение точка-отрезок (однородные координаты)Вычисление точки пересечения отрезков прямых | O(n) |
| Прослеживание контура | Произвольной формы | Сравнение положения точки по отношению к прямойПересечение прямой с отрезком другой прямой | O(n) |
Как видно из таблицы 1, при разрезании отрезка многоугольным произвольным контуром необходимо пользоваться алгоритмом прослеживания контура. Ж.Эгрон отмечает, что в частном случае, когда окно имеет форму прямоугольника, метод Сазерленда (дихотомический вариант) наилучшим образом приспособлен для реализации на жесткой логике. В ином случае аппаратная реализация на программируемом устройстве лучше согласуется с алгоритмом Павлидиса, причем степень преимущества определяется характеристиками сцены (содержанием в ней вершин и горизонтальных линий). Следовательно, если многоугольник выпуклый, то целесообразно пользоваться более специализированными алгоритмами, например алгоритмом Павлидиса [2,3]. Если же многоугольник представляет собой прямоугольник, стороны которого параллельны осям координат (далее по тексту просто ”прямоугольник”), то процесс определения факта нахождения примитива в многоугольнике пространственной окрестности сводится к элементарным операциям сравнения координат и вычисления середины отрезка.
Проведем сравнительный анализ вариантов описания пространственной окрестности. Оценку способов представления описывающих контуров будем производить с точки зрения времени формирования пространственной окрестности Tф. Процесс формирования пространственной окрестности можно разделить на несколько составляющих:
построение уравнений ограничений;
анализ примитивов на попадание в заданную пространственную окрестность и, если это необходимо, их последующее разрезание.
Время Tур, затрачиваемое ГИС на построение уравнений ограничений, различается для каждого из способов. Так при построении уравнений окружностей (1.а, 1.б) затраты времени минимальны по сравнению с другими методами. Для второго и третьего способов затраты времени почти не отличаются от первого, т.к. количество проводимых вычислений (инициализации соответствующих коэффициентов в уравнениях 2.а, 2.б, 3) пренебрежительно мало. По-другому обстоит дело с формированием уравнений ограничений произвольными многоугольниками. Как видно из предложенного алгоритма, процесс формирования многоугольников контура пространственной окрестности занимает некоторое, значительно превышающее для первых трех случаев, время. И чем больше вершин содержит описываемый контур, тем больший промежуток времени занимает этот процесс. Таким образом, соотношение времен, затрачиваемых на построение уравнений ограничений, имеет следующий вид:
Tур1< Tур2< Tур3<< Tур4, (4)
где Tурi - время формирования уравнений ограничений i-м (
) способом представления описывающих контуров.Время Tа, затрачиваемое на анализ и разрезание примитивов для формирования пространственной окрестности, зависит от нескольких факторов, среди которых, помимо заданных уравнений ограничений, огромную роль играет тип и количество анализируемых примитивов. Так, например, наиболее простым для анализа примитивом является отрезок, а самым сложным - полилиния (примитив, сочетающий в себе свойства отрезка и дуги окружности - термин векторного графического редактора). Будем считать, что характеристики анализируемого пространства электронной карты одинаковы для каждого из оцениваемых способов. Тогда, исходя из анализа уравнений (1.а, 1.б, 2.а, 2.б, 3), можно утверждать, что среди первых трех способов представления описывающих контуров справедливо следующее соотношение:
Tа1< Tа2< Tа3, (5)
где Tаi - время анализа и разрезания примитивов для формирования пространственной окрестности i-м (
) способом представления описывающих контуров.Более сложно оценивать способ представления описывающих контуров произвольным многоугольником, так как время анализа и разрезания примитивов для формирования пространственной окрестности при таком способе пропорционально числу вершин в этом многоугольнике. Крайним случаем является описание пространственной окрестности при помощи прямоугольника. При этом предельно упрощается процедура поиска точек пересечения примитивов и контура пространственной окрестности, поэтому
Tпр< Tа1< Tа2< Tа3, (6)
где Tпр - время анализа и разрезания примитивов для формирования контура пространственной окрестности представленной прямоугольником.
Для выпуклых многоугольников, в общем случае, невозможно пользоваться специализированными алгоритмами (три первых в табл. 1), т.к. эти случаи не позволяют эффективно работать с кривыми второго порядка. Поэтому для произвольного многоугольника (за исключением рассмотренного выше случая) при разрезании необходимо пользоваться алгоритмом прослеживания контура. Как видно из табл.1, время анализа и разрезания примитивов для формирования пространственной окрестности Tмн в этом случае прямо пропорционально числу вершин контура окрестности, т.е. чем больше вершин в многоугольнике, ограничивающем пространственную окрестность, тем больше временные затраты на ее формирование. Таким образом, с учетом (6), получаем следующее соотношение:
Tпр< Tа1< Tа2< Tа3< Tмн. (7)
Неравенства (4) и (7) описывают соотношение времен, составляющих процесс формирования пространственной окрестности:
Tф= Tур+ Tа. (8)
Для построения обобщающего неравенства необходимо допустить, что число анализируемых и разрезаемых примитивов при формировании пространственной окрестности достаточно велико, чтобы соблюдалось условие:
Tпр+Tур4< Tа1+ Tур1. (9)
На самом деле, это допущение естественно, т.к. если бы число анализируемых примитивов было несущественно малым, то не существовало бы задачи построения пространственных ограничений. Поэтому, с учетом (8) и (9), соотношение времен формирования пространственной окрестности имеет следующий вид:
Tф.пр< Tф1< Tф2< Tф3<< Tф.мн, (10)
где Tфi - время формирования пространственной окрестности i-м (
) способом представления описывающих контуров,Tф.пр - время формирования пространственной окрестности при помощи прямоугольника,
Tф.мн - время формирования пространственной окрестности при помощи произвольного многоугольника.
Как видно из (10), наиболее предпочтительными с точки зрения времени формирования пространственной окрестности являются первые три способа представления описывающих контуров (см. классификацию по способам представления описывающих контуров) и особенно способ формирования пространственной окрестности при помощи прямоугольника, стороны которого параллельны осям координат. Исходя из этих позиций, чрезвычайно привлекательно аппроксимировать контур объекта прямоугольником, окружностью или эллипсом и задать пространственные ограничения при помощи соответствующих уравнений. Но это ”огрубление” в результате ведет к появлению примитивов, которые не должны попадать во множество E примитивов пространственной окрестности. То есть аппроксимация контура объекта приводит к появлению избыточности результата, которая напрямую зависит от ”степени огрубления” этого контура. Задача состоит в том, чтобы определить: можно ли аппроксимировать контур объекта таким образом, чтобы время формирования результата с аппроксимируемым контуром не превышало времени формирования результата с первоначальным (неаппроксимированным) контуром. Такую постановку задачи можно обобщить следующим образом: необходимо определить, не превысит ли время формирования результата заданного значения:
Tдоп= Tф+ Tпр, (11)
где Tдоп - предполагаемое время формирования результата при построении ограничений для объекта с первоначальным контуром,