Ѕаза знаний студента. –еферат, курсова€, контрольна€, диплом на заказ

курсовые,контрольные,дипломы,рефераты

¬изуализаци€ в √»— при наличии пространственных ограничений — »нформатика, программирование

ѕосмотреть видео по теме –еферата

Ћ. . —амойлов, —.Ћ. Ѕел€ков, ћ.ѕ. —идоренко

¬заимодействие пользовател€ с геоинформационной системой (√»—) осуществл€етс€ чаще всего в диалоговом режиме. —уть диалога заключаетс€ в формировании запросов серверу √»— и получении ответов в виде картографических изображений. Ёффективность диалога определ€етс€ скоростью регенерации изображени€ на экране при переходе между локальными участками электронной карты.† ƒанна€ скорость в значительной степени зависит от числа примитивов, описывающих ответ на запрос пользовател€. «десь предполагаетс€, что электронна€ карта представлена в векторном формате, наиболее распространенном в √»—.

 ак показал анализ, ответы сервера √»— содержат избыточные примитивы. »х по€вление обусловлено тем, что результат выполнени€ запроса €вл€етс€ картой, котора€ содержит кроме непосредственно примитивов выбранных объектов описание окружающего их пространства. Ќасколько обширно последнее описание (и соответствующее количество примитивов) зависит от представлени€ карты. ¬ простейшем случае ответ включает в себ€ полностью карту, в сложных √»— - набор фрагментов (например, стандартных геодезических планшетов), представл€ющих общую карту системы.

¬опрос о том, какие примитивы в ответе сервера считать избыточными, решаетс€ пользователем. √»— должна предоставл€ть средства описани€ примитивов, €вл€ющихс€ существенными в ответе сервера на запрос пользовател€. ¬ данной работе анализируетс€ один из возможных вариантов описани€ существенности - через пространственные ограничени€.

¬ общем виде под задачей визуализации будем понимать следующее: имеетс€ множество примитивов исходной карты G, в результате выполнени€ некоторой процедуры получено множество RG примитивов ответа на запрос. “ребуетс€ найти множество примитивов EGR такое, что |E|min.

¬се пространственные ограничени€ можно классифицировать по нескольким признакам. “ак с точки зрени€ пользовател€ пространственные ограничени€ описывают:

пространственную окрестность дл€ заданной точки в виде окружности с радиусом d. ѕопадание в окрестность любой точки примитива €вл€етс€ критерием отнесени€ его к множеству E. ѕространственные ограничени€ этого типа могут эффективно использоватьс€ при описании примитивов, контур которых представл€ет собой окружность, например колодцы в системах городских коммуникаций;

пространственную окрестность дл€ каждого примитива giR, попадание в которую любого другого примитива gkR, (ki) €вл€етс€ критерием отнесени€ его к множеству E. ƒанный вид ограничений эффективен, например, в задачах, св€занных с коммуникаци€ми: пространственна€ окрестность трубопровода, дороги, энергосети значительно меньше пространства, которые они охватывают;

пространственную окрестность заданного примитива, определ€емую пересекающими его примитивами. ƒанный вид пространственных ограничений можно использовать дл€ описани€ тех ситуаций, когда пользовател€ интересует лишь факт наложени€ примитивов, например, при решении задачи построени€ профил€. —уть данной задачи заключаетс€ в отображении среза коммуникаций по указанной пользователем пр€мой;

пространственную окрестность дл€ объектов - некоторых смысловых объединений примитивов. ѕримером могут служить здани€ и сооружени€, территории, земли. √раница окрестности в этом случае определ€етс€ как описывающий многоугольник объекта;

пространственную окрестность в виде областей на карте, внутри которых предусмотрена визуализаци€ всех примитивов, если, по крайней мере, один из примитивов, принадлежащих множеству R, попадает в область. ƒанна€ ситуаци€ имеет место, например, при изучении чрезвычайной ситуации в некотором районе. ¬ отличие от предыдущего варианта, область ограничений св€зываетс€ с областью существовани€ объектов и, в принципе, может задавать ограничени€ дл€ любого из описанных выше вариантов.

— точки зрени€ способа представлени€ описывающих контуров, все пространственные ограничени€ можно классифицировать на:

1) ограничени€, задаваемые окружност€ми:

 ак видно из рис.1 координаты примитивов множества E дл€ круга должны удовлетвор€ть условию:

,†††††††††††††††††††† (1.а)

.††††††††††††††††††††† (1.б)

где x0, y0- центр круга, вокруг которого вводитс€ пространственна€ окрестность, r - радиус круга, d - длина пространственной окрестности, x, y - координаты рассматриваемого примитива.

ѕримитив, попавший в пространственную окрестность заданного объекта (примитива) может иметь большую пространственную прот€женность. —ледовательно, имеет смысл разрезать его в точке пересечени€ с ограничивающей окружностью. ѕоэтому предлагаетс€ следующий пор€док отбора примитивов. ¬начале координаты примитива анализируютс€ на выполнение соответствующего услови€ (1.а) или (1.б). ≈сли условие выполн€етс€, то считаетс€, что примитив принадлежит множеству E. ¬ противном случае анализируетс€ вариант пересечени€ примитива и окружности, полученной по неравенству (1.а) или (1.б) соответственно. ≈сли и это условие не выполн€етс€, то примитив исключаетс€ из рассмотрени€, иначе примитив разрезаетс€ в точке его пересечени€ с ограничивающей окружностью, и оставша€с€ в пространственной окрестности часть примитива приписываетс€ к множеству E. —оответствующий алгоритм разрезани€ описан в [3].

2) ограничени€, задаваемые эллипсами:

 оординаты примитивов множества E дл€ эллипса должны удовлетвор€ть следующим услови€м:

,††††††††††††††††††††††††††† 2.а)

.††††††††††††††††††††††††† (2.б)

где x0, y0 - центр круга, вокруг которого вводитс€ пространственна€ окрестность, a, b - больша€ и фокальна€ полуоси описываемого эллипса соответственно, d - длина пространственной окрестности, x, y - координаты рассматриваемого примитива.

 ак видно из сравнени€ формул (1.а, 1.б) и формул (2.а, 2.б), задание пространственных ограничений эллипсами аналогично предыдущему случаю, поэтому здесь справедливо все вышесказанное по отношению к ограничени€м окружност€ми.

3) ограничени€, задаваемые дугами окружностей:

Ётот случай аналогичен первому, только здесь ввод€тс€ еще два ограничени€, св€занных с углом к центру дуги окружности. “аким образом, примитивы множества E пространственной окрестности дуги должны удовлетвор€ть условию:

,††††††††††††††††††††† (3)

где C=(x0, y0) - центр дуги, вокруг которой вводитс€ пространственна€ окрестность,

r - радиус дуги,

d -длина пространственной окрестности,

x, y - координаты рассматриваемого примитива,

A - точка, расположенна€ в начале дуги,

B - точка, расположенна€ в конце дуги,

D - точка, расположенна€ на одной оси с точкой СCТ со смещением

вправо, например (x0+1, y0).

ќпределение факта попадани€ примитива в пространственную окрестность, заданную дугами окружностей, при разрезании примитивов аналогично пространственным ограничени€м из окружностей.

4) ограничени€, задаваемые произвольными многоугольниками:

 ак видно из рис.4-5 многоугольник, описывающий пространственную окрестность, не может быть получен простым масштабированием исходного контура (контура, описывающего заданный объект) по двум причинам:

a) дл€ произвольного многоугольника, в общем случае, невозможно найти такую точку, котора€ была бы равноудалена от всех вершин этого многоугольника. —ледовательно, нет такой точки, относительно которой операци€ масштабировани€ отодвинула бы стороны многоугольника, задающего пространственные ограничени€, от сторон многоугольника-контура объекта на одинаковые рассто€ни€.

b) стороны многоугольника, описывающего пространственную окрестность, как демонстрируют рис.4 и рис.5, ограничены дугами окружностей на внутренних углах, меньших .

»сход€ из этих причин, предлагаетс€ следующий алгоритм, который учитывает все особенности преобразовани€ контуров. —уть алгоритма заключаетс€ в следующем:

»з исходного множества вершин P (|P|=N) контура, описывающего заданный объект, стро€тс€ уравнени€ пр€мых (соответствующие формулы широко освещаютс€ во всех печатных издани€х по машинной графике и аналитической геометрии, например, в [1-4]).

—огласно результатам, полученным в предыдущем пункте, стро€тс€ уравнени€ пр€мых многоугольника, задающего пространственные ограничени€. ƒанные пр€мые смещены в направлении от контура объекта (см. случай, изображенный на рис. 5) и к контуру объекта (см. случай, изображенный на рис. 4). ”равнени€ пр€мых, параллельных ребрам многоугольного контура, можно построить по [4].

ѕо формуле, аналогичной (1.б), определ€ютс€ неравенства, ограничивающие отрезки полученного многоугольника в его углах.

ќпредел€етс€ множество 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доп - предполагаемое врем€ формировани€ результата при построении ограничений дл€ объекта с первоначальным контуром,

Tпр,- врем€, затрачиваемое системой на поиск объекта, прорисовку и пр.

ѕоставленную задачу предлагаетс€ решить через определение предполагаемого времени формировани€ пространственной окрестности заданного объекта:

Tф Tдоп- Tпр,††††††††††††††††††††††† ††††††††††††††(12)

ƒл€ оценки Tф необходимо проанализировать ее составл€ющие (8). ¬рем€ Tур, затрачиваемое √»— на построение уравнений ограничений, можно оценить по результатам исследований, проведенных во врем€ построени€ √»—. ќценку же второй составл€ющей предлагаетс€ производить через величину площади S, занимаемой анализируемым объектом и его предполагаемой пространственной окрестностью. ƒл€ этого необходимо иметь дополнительную информацию о плотности †анализируемого участка электронной карты (число примитивов на единицу площади), которую можно хранить и периодически обновл€ть во врем€ функционировани€ √»—. ќпределив таким образом значение Tа как:

,

где Tа.пр. -†††††††††† среднее врем€ анализа и разрезани€ одного примитива дл€ формировани€ пространственной окрестности представленной анализируемым способом, по формуле (8) необходимо определить величину Tф. ≈сли же выполн€етс€ условие неравенства (12), то можно говорить о том, что врем€ формировани€ пространственной окрестности дл€ объекта с аппроксимированным контуром не превышает времени формировани€ пространственной окрестности дл€ объекта с первоначальным контуром. —ледовательно, контур объекта необходимо аппроксимировать.

«адача определени€ допустимости аппроксимации аналогична задачи анализа временных затрат на процесс формировани€ результата. ¬ этом случае в роли Tдоп может выступать временное ограничение, налагаемое пользователем на процесс диалога с системой.

“аким образом, на основании проведенного анализа можно утверждать, что наиболее эффективными способами представлени€ описывающих контуров €вл€ютс€ ограничений, задаваемые пр€моугольниками, окружност€ми и эллипсами. — помощью ограничений, задаваемых произвольными многоугольниками, возможно гибкое описание пространственной окрестности любой формы. јппроксимаци€ же пр€моугольником, окружностью и эллипсом позвол€ет существенно снизить временные затраты на формирование пространственной окрестности. јппроксимаци€ возможна только в тех случа€х, когда врем€ формировани€ пространственной окрестности (определенное по формуле 8) удовлетвор€ет условию (12).

—писок литературы

ѕавлидис “. јлгоритмы машинной графики и обработки изображений: ѕер. — англ. - ћ.: –адио и св€зь, 1986.

‘оли ƒж., ƒэм ј. ќсновы интерактивной машинной графики: ¬ 2-х книгах. ѕер с англ. - ћ.: ћир, 1985.

Ёгрон ∆. —интез изображений. Ѕазовые алгоритмы: ѕер. с франц. - ћ.: –адио и св€зь, 1993.

Ѕугров я.—., Ќикольский —.ћ. Ёлементы линейной алгебры и аналитической геометрии: ”чебник дл€ студентов инж.-техн. спец. вузов.- 3-е изд., испр. и доп., ћ.: Ќаука, 1988.



«аказывайте: рефераты - 150 р. курсовые - 700 р. дипломы - 2500 р. Ћ. . —амойлов, —.Ћ. Ѕел€ков, ћ.ѕ. —идоренко ¬заимодействие пользовател€ с геоинформационной системой (√»—) осуществл€етс€ чаще всего в диалоговом режиме. —уть диалога заключаетс€ в формировании запросов серверу √»— и получении ответов в виде ка

 

 

 

¬нимание! ѕредставленный –еферат находитс€ в открытом доступе в сети »нтернет, и уже неоднократно сдавалс€, возможно, даже в твоем учебном заведении.
—оветуем не рисковать. ”знай, сколько стоит абсолютно уникальный –еферат по твоей теме:

Ќовости образовани€ и науки

«аказать уникальную работу

ѕохожие работы:

¬ариационный подход к сглаживанию и определению характерных точек черно-белых изображений
√енетический алгоритм глобальной трассировки
ћодели теории графов дл€ выделени€ контуров по градиентному изображению
√енетические алгоритмы
 омпьютерные вирусы. јнтивирусные программы
—ессии в PHP
»ерархи€ каталогов и файловых систем в Linux
ћодели IP протокола (Internet protocol) с учЄтом защиты информации
”сложнение решающего правила при управлении в задачах распознавани€ образов
»стори€ информатики как науки о знани€х и технологи€х

—вои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru