ФОРМАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ХАРАКТЕРИСТИК ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННЫХ ОБЪЕКТОВ
Формальное представление характеристик пространственно-распределенных объектов 25
УДК 680.5.01:621.384
Д. Е. АНДРИАНОВ, С. С. САДЫКОВ, В. В. ФРОЛОВ
ФОРМАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ХАРАКТЕРИСТИК ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННЫХ ОБЪЕКТОВ
Рассматривается подход к формальному описанию данных о пространственнораспределенных объектах муниципальных геоинформационных систем. Предложено характеризовать пространственное положение объекта в трехмерном пространстве на основе семи топологических отношений, которые позволяют сформировать структуру из шестнадцати бинарных элементов. На основе этих формализаций возможно описать топологическое положение объекта в виде структур, позволяющих классифицировать пространственный объект.
Ключевые слова: пространственно-распределенный объект, топологическое отношение, муниципальные геоинформационные системы, матрица шестнадцати пересечений.
Для эффективного управления муниципальными образованиями и динамично разви-
вающимися регионами необходимо иметь достоверные данные об объектах и протекающих
на их территории процессах, а также передовые технологии накопления, обработки и пред-
ставления информации. Современные географические информационные системы (ГИС) по-
зволяют наглядно отобразить и осмыслить информацию о конкретных объектах, процессах и
явлениях в их совокупности. Геоинформационные системы позволяют выявлять взаимосвязи
и пространственные отношения, поддерживать коллективное использование данных и их
объединение в единый информационный массив.
Определим виды пространственно-распределенных объектов и их взаимоотношения [1].
Точечный объект — это малоразмерный объект, который характеризуется координатами
p = (x, y)∈R2 p = (x, y)∈R2 ,
(1)
линия описывается уравнением
f (x, y) = 0 ,
(2)
линейный сегмент задается координатами
ls ={( p1, p2 )} ,
(3)
где p1 = ( x1, y1 ) , p2 = ( x2 , y2 ) — точечные объекты.
Линейный объект представляет собой последовательность линейных сегментов:
t ={( p1, p2 ), ( p2 , p3 ), ..., ( pk−1, pk )} (k =1, 2, ...) .
(4)
Полигональный объект — это двумерный объект, образованный замкнутой последова-
тельностью линейных сегментов, т.е.
h ={( p1, p2 ), ( p2 , p3 ), ..., ( pk , p1)} (k =1, 2, ...) .
(5)
На основании полученных выражений возможно описать тематический слой карты.
Слоем карты назовем сочетание картографических объектов, выделенных из карты K по за-
данным условиям так, что
s ={Xi ∈K | Xi удовлетворяет заданным условиям} (i =1, 2, ..., n) .
(6)
Например, из всех объектов карты можно выделить слои дорог, школ, жилых помеще-
ний, стадионов, водоемов, электросетей и т.д.
Между пространственными объектами существуют сложные взаимосвязи. Для фор-
мального описания связей будем использовать топологические отношения, так как они наи-
более полно отражают взаимодействие объектов в пространстве [1].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
26 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
Топологическим отношением между любыми двумя множествами X и Y называется такое отношение, которое при аффинных или топологических преобразованиях будет сохраняться.
Введем определения для формального описания следующих топологических отношений: 1) между частями пространственных объектов; 2) между пространственными объектами; 3) между слоями пространственных объектов. 1. Отношение, сохраняющееся между элементами x1∈ X и x2 ∈ X картографического объекта X при различных аффинных и топологических преобразованиях, назовем топологическим ϕэл . Топологическое отношение между элементами обозначается следующим образом: x1ϕэл x2 , т.е. элемент x1 имеет топологическое отношение ϕэл с элементом x2 . Следует указать, что противоположное отношение может и не иметь места. 2. Топологическим отношением ϕоб между картографическими объектами X1∈K и X 2 ∈K карты K будем называть отношение, которое сохраняется между данными объектами при различных аффинных и топологических преобразованиях. Топологическое отношение между объектами одного слоя обозначается следующим образом: X1ϕоб X2 (картографический объект X1 имеет топологическое отношение ϕоб с объектом X 2 ). Противоположное отношение может и не иметь места. 3. Топологическим отношением ϕсл между слоями s1∈S и s2 ∈S назовем отношение, которое сохраняется между данными слоями при различных аффинных и топологических преобразованиях между объектами, находящимися в слоях s1 и s2 соответственно: s1ϕсл s2 (слой s1 имеет топологическое отношение ϕсл со слоем s2 ). Обратная запись может и не иметь места. Рассмотрим следующие типы топологических отношений между картографическими объектами: соседство, изолированность, близость, вложенность и др. Эти топологические отношения наиболее полно отражают взаимодействие пространственных объектов. Отношение „Соседство“. Картографический объект X1∈K находится в соседстве с объектом X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Соседство“ α , т.е. X1αX2 тогда и только тогда, когда картографические объекты X1 и X 2 имеют общую граничную точку или линию, т.е. если есть совпадение координат точек обоих объектов. Отношение „Соседство“ выполняется ( X1αX2 ), если оно антирефлексивно, симметрично, транзитивно и пересечение картографических объектов X1 и X 2 есть непустое множество, т.е. X1 ∩ X 2 = A , A ≠ Ø и непустое множество А должно состоять только из граничных точек картографических объектов X1 и X 2 . Отношение „Изолированность“. Картографический объект X1∈K изолирован от объекта X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение изолированности δ , т.е. X1δX 2 тогда и только тогда, когда объекты X1 и X 2 не пересекаются друг с другом. Отношение „Изолированность“ выполняется ( X1δX 2 ), если оно антирефлексивно, симметрично, транзитивно и при этом выполняется условие X1 ∩ X 2 = Ø . Отношение „Близость“. Картографический объект X1∈K находится в близости к картографическому объекту X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Близость“ β , т.е. X1βX 2 тогда и только тогда, когда картографический объект X1 расположен на заданном расстоянии от картографического объекта X 2 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Формальное представление характеристик пространственно-распределенных объектов 27
Отношение „Близость“ выполняется ( X1βX 2 ), если оно антирефлексивно, симметрично,
транзитивно и при этом выполняется следующее условие: картографические объекты X1 и
X 2 не должны пересекаться между собой, т.е. X1 ∩ X 2 = Ø . Минимальное расстояние между
граничными точками объектов X1 и X 2 не превышает заданного расстояния ρз , т.е.
min ρ(a, b) ≤ ρз , где a, b — граничные точки картографических объектов X1 и X 2 соответственно; ρ(a, b) — расстояние между граничными точками а и b.
Отношение „Вложенность“. Картографический объект X1∈K вложен в картографи-
ческий объект X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Вложенность“ γ , т.е. X1γX 2 тогда и только тогда, когда все элементы объекта X1 находятся
внутри объекта X 2 .
Отношение „Вложенность“ выполняется ( X1γX 2 ), если оно рефлексивно, асимметрично,
нетранзитивно и при этом X2 ⊆ X1.
Отношение „Пересечение“. Картографический объект X1∈K пересекается с картогра-
фическим объектом X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Пересечение“ χ , т.е. X1χX 2 .
Отношение „Пересечение“ выполняется ( X1χX 2 ), если оно рефлексивно, симметрично,
транзитивно и X1 ∩ X 2 = Ø . Для более полного описания положения объекта городской инфраструктуры введем от-
ношения, которые характеризуют геометрическое расположение пространственных объектов:
параллельность и перпендикулярность.
Картографический объект X1∈K параллелен объекту X 2 ∈ K , или между X1 и X 2 установлено геометрическое отношение „Параллельность“ η, т.е. X1ηX 2 тогда и только тогда,
когда в объектах X1 и X 2 можно найти по одному линейному сегменту, которые параллельны между собой, т.е.
(∃xk ∈ X1, ∃xl ∈ X 2 ): xk || xl ,
(7)
где xk , xl — линейные сегменты.
Объект X1∈K перпендикулярен картографическому объекту X 2 ∈ K , или между X1 и X 2 установлено геометрическое отношение „Перпендикулярность“ µ , т.е. X1µX 2 тогда и
только тогда, когда в объектах X1 и X 2 можно найти по одному линейному сегменту, которые перпендикулярны друг другу, т.е.
(∃xk ∈ X1, ∃xl ∈ X 2 ): xk ⊥ xl .
(8)
При анализе карты города было выявлено, что часть пространственных объектов по
различным признакам сгруппирована в отдельные структуры. Следует отметить, что в струк-
туру могут входить объекты не только из одного, но и из разных слоев. В результате если
формально описать такие структуры, то карта будет представлять собой совокупность струк-
тур с учетом взаимосвязей входящих в них объектов.
Топологическая структура — это совокупность картографических объектов, связанных
между собой топологическими и геометрическими отношениями, она задается следующим
образом:
T = (W , Π, Φ) ,
(9)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
28 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
где W ={X1, X2 , ..., Xn} — подсистема картографических объектов из разных слоев, n — ко-
личество объектов подсистемы; Π ={ρk } (k =1, 2, ..., h) — множество типов топологических
и
геометрических
отношений
в
подсистеме
W,
h
—
количество
отношений;
Φ
=
⎣⎡ϕi(jk
)
⎤ ⎦
(i, j =1, 2, ..., n) — матрица топологических отношений между объектами из подсистемы W .
Элемент ϕi(jk) = 0 , если не существует взаимодействия между объектами Xi и X j . Эле-
мент ϕi(jk) есть топологическое отношение k-го типа, если существует связь между слоями
Xi и X j .
Рассмотрим простейший пример расположения объектов в двумерном пространстве
(рис. 1). Здесь показаны отношения объектов A и В1, В2, В3, В4 (объекты A и В1 не вложены
друг в друга, A и В1 — соприкасаются, A и В3 — пе-
B4 B3
A—
B1 A°
ресекаются, A и В4 — один объект включает в себя другой).
Когда рассматривается отношение объектов трехмерном пространстве, необходимо анализировать и высотную составляющую объектов. На рис. 2
B2 ∂A
показаны возможные комбинации расположения объектов А и Вn по высоте, где n — один из воз-
Рис. 1
можных вариантов расположения объекта В (первый вариант — один объект включает в себя другой,
второй и седьмой — один объект находится на некотором удалении по высоте от другого,
третий и шестой — касание границы, четвертый и пятый — пересечение границы [2]).
A–3u В3
В4
В2 ∂uA
В1 A°3
В5
В6 A–3d
∂dA В7
Рис. 2
В основу метода описания трехмерных топологических отношений положим математическую модель „девяти пересечений“ Эгенгофера [3], которая использует пересечения различных составных элементов объектов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Формальное представление характеристик пространственно-распределенных объектов 29
Часть точек пространства в множестве A, расположенная во внутренней части объекта и
обозначенная А°, является объединением всех открытых множеств в A. Замкнутое выражение
A, обозначенное A⎯, является пересечением всех замкнутых множеств A. Внешняя часть A, относящаяся к вложенному пространству R2, обозначенному A⎯, является множеством всех точек R2, не содержащихся в A. Граница A, обозначенная ∂A, является пересечением замкнутого выражения А и замкнутого выражения внешней части A. Тем самым выполняется фор-
мальная характеристика расположения объектов на плоскости.
Для описания положения объекта в трехмерном пространстве введем дополнительные
обозначения. Часть точек трехмерного пространства, расположенную во внутренней части объекта, обозначим как А°3. Внешняя часть объекта будет представлять собой две непересекающиеся области A⎯3u (над объектом) и A⎯3d (под объектом). Верхняя граница A, обозна-
ченная ∂uA, является пересечением замкнутого выражения А и замкнутого выражения верх-
ней внешней части A. И соответственно нижняя граница A, обозначенная ∂dA, является пересечением замкнутого выражения А и замкнутого выражения нижней внешней части A.
Таким образом, пространственная область определена как трехмерное множество точек,
которое является гомеоморфным к пяти областям, т.е. каждая из восьми объектных частей
области в трехмерном пространстве (внутренняя часть, граница и внешняя часть) — непустая
и связанная.
Бинарное топологическое отношение между двумя областями А и B характеризуется как
сравнение границы (∂A), внутренней части (А°), внешней части (A⎯) на горизонтальной плоскости и верхней, нижней границ (∂uA, ∂dA), внутренней части (А°3), верхней и нижней внешних частей (A⎯3u, A⎯3d) в вертикальной плоскости объекта A с границей (∂В), внутренней частью (B°), и внешней частью (В⎯) на горизонтальной плоскости и верхней, нижней границ (∂uВ, ∂dВ) внутренней части (В°3), верхней и нижней внешних частей (В⎯3u, В⎯3d) в вертикальной плоскости объекта B. Эти четырнадцать объектных частей объединены так, что меж-
ду ними существует шестнадцать пересечений, которые представляют топологические отно-
шения между этими двумя объектами.
Естественно, это не все возможные комбинации топологических характеристик, но рас-
смотрев рис. 2, будем считать, что этими отношениями можно описать взаимодействие
объектов в дополнение к плоскости в трехмерном пространстве.
Топологическое отношение между областями А и B кратко может быть представлено
как матрица 4×4, назовем ее „16 пересечений“.
⎡ ∂A∩∂B
⎢
R16
(
A,
B)
=
⎢ ⎢
⎢
Ao ∩∂B A− ∩∂B
⎢⎣∂uA∩∂dB
∂A∩ Bo Ao ∩ Bo A− ∩Bo
∂dA∩∂uB
∂A∩ B− Ao ∩ B− A− ∩B− ∂dA∩ Bo3
A−3d ∩ Bo3 ⎤
A−3u ∩ Bo3 ∂uA∩ Bo3
⎥ ⎥ ⎥ ⎥
.
Ao3 ∩ Bo3
⎥ ⎦
Топологические отношения характеризуются топологическими инвариантами „16 пере-
сечений“, т.е. свойствами, которые сохраняются при топологических преобразованиях. Со-
держание этих шестнадцати пересечений было идентифицировано как самый простой и об-
щий топологический инвариант, хотя другие могут быть полезны как компоненты пересече-
ния и их измерения. Инвариант содержания характеризует каждое из этих шестнадцати пере-
сечений значением „пустое“ (∅) или „непустое“ (¬∅). С различением „пустое/непустое“ этих шестнадцати пересечений потенциально можно получить 216 различных топологических от-
ношений. Два из этих топологических отношений сохраняются между любыми двумя областя-
ми. Шестнадцать пересечений „пустое/непустое“ описывают набор отношений, которые обес-
печивают полный охват — три объектные части: граница, внутренняя часть и внешняя часть.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
30 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
Содержания их пересечений такие, что любое множество является или пустым, или непустым. Фактическое число возможных отношений зависит от измерения пространства относительно объектов и от топологических свойств объектов, вложенных в это пространство. Например, граница линии (нециклической), т.е. множество ее начальных и конечных точек, является разделенной, тогда как граница области без отверстий является соединенной, и различие в этих топологических свойствах влияет на то, какие топологические отношения могут быть реализованы.
Для хранения в памяти одного топологического отношения между картографическими объектами достаточно шестнадцати бит. Формализованная выше структура будет состоять из набора бинарных таблиц, достаточно простых в хранении и анализе.
СПИСОК ЛИТЕРАТУРЫ
1. Еремеев С. В., Садыков С. С. Автоматический контроль размещения пространственных объектов на цифровой карте с использованием топологических отношений // Информационные технологии. 2005. № 8. С. 6—9.
2. Андрианов Д. Е. Создание метода представления топологических отношений в трехмерном пространстве для задач городских ГИС // Геоинформатика. М.: ВНИИгеосистем, 2007. № 2. С. 1—3.
3. Egenhofer M. J. and Franzosa R. D. Point-set topological spatial relations // Int. J. of Geographical Inf. Systems. 1991. Vol. 5, N 2. Р. 161—176.
Дмитрий Евгеньевич Андрианов Султан Садыкович Садыков Владислав Валерьевич Фролов
Сведения об авторах — канд. техн. наук, доцент; Муромский институт (филиал) Владимир-
ского государственного университета, кафедра информационных систем; E-mail: AndrianovDE@inbox.ru — д-р техн. наук, профессор; Муромский институт (филиал) Владимирского государственного университета, кафедра информационных систем; E-mail: SadykovSS@yandex.ru — аспирант; Муромский институт (филиал) Владимирского государственного университета, кафедра информационных систем; E-mail: AndrianovDE@inbox.ru
Рекомендована кафедрой информационных систем
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 680.5.01:621.384
Д. Е. АНДРИАНОВ, С. С. САДЫКОВ, В. В. ФРОЛОВ
ФОРМАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ХАРАКТЕРИСТИК ПРОСТРАНСТВЕННО-РАСПРЕДЕЛЕННЫХ ОБЪЕКТОВ
Рассматривается подход к формальному описанию данных о пространственнораспределенных объектах муниципальных геоинформационных систем. Предложено характеризовать пространственное положение объекта в трехмерном пространстве на основе семи топологических отношений, которые позволяют сформировать структуру из шестнадцати бинарных элементов. На основе этих формализаций возможно описать топологическое положение объекта в виде структур, позволяющих классифицировать пространственный объект.
Ключевые слова: пространственно-распределенный объект, топологическое отношение, муниципальные геоинформационные системы, матрица шестнадцати пересечений.
Для эффективного управления муниципальными образованиями и динамично разви-
вающимися регионами необходимо иметь достоверные данные об объектах и протекающих
на их территории процессах, а также передовые технологии накопления, обработки и пред-
ставления информации. Современные географические информационные системы (ГИС) по-
зволяют наглядно отобразить и осмыслить информацию о конкретных объектах, процессах и
явлениях в их совокупности. Геоинформационные системы позволяют выявлять взаимосвязи
и пространственные отношения, поддерживать коллективное использование данных и их
объединение в единый информационный массив.
Определим виды пространственно-распределенных объектов и их взаимоотношения [1].
Точечный объект — это малоразмерный объект, который характеризуется координатами
p = (x, y)∈R2 p = (x, y)∈R2 ,
(1)
линия описывается уравнением
f (x, y) = 0 ,
(2)
линейный сегмент задается координатами
ls ={( p1, p2 )} ,
(3)
где p1 = ( x1, y1 ) , p2 = ( x2 , y2 ) — точечные объекты.
Линейный объект представляет собой последовательность линейных сегментов:
t ={( p1, p2 ), ( p2 , p3 ), ..., ( pk−1, pk )} (k =1, 2, ...) .
(4)
Полигональный объект — это двумерный объект, образованный замкнутой последова-
тельностью линейных сегментов, т.е.
h ={( p1, p2 ), ( p2 , p3 ), ..., ( pk , p1)} (k =1, 2, ...) .
(5)
На основании полученных выражений возможно описать тематический слой карты.
Слоем карты назовем сочетание картографических объектов, выделенных из карты K по за-
данным условиям так, что
s ={Xi ∈K | Xi удовлетворяет заданным условиям} (i =1, 2, ..., n) .
(6)
Например, из всех объектов карты можно выделить слои дорог, школ, жилых помеще-
ний, стадионов, водоемов, электросетей и т.д.
Между пространственными объектами существуют сложные взаимосвязи. Для фор-
мального описания связей будем использовать топологические отношения, так как они наи-
более полно отражают взаимодействие объектов в пространстве [1].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
26 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
Топологическим отношением между любыми двумя множествами X и Y называется такое отношение, которое при аффинных или топологических преобразованиях будет сохраняться.
Введем определения для формального описания следующих топологических отношений: 1) между частями пространственных объектов; 2) между пространственными объектами; 3) между слоями пространственных объектов. 1. Отношение, сохраняющееся между элементами x1∈ X и x2 ∈ X картографического объекта X при различных аффинных и топологических преобразованиях, назовем топологическим ϕэл . Топологическое отношение между элементами обозначается следующим образом: x1ϕэл x2 , т.е. элемент x1 имеет топологическое отношение ϕэл с элементом x2 . Следует указать, что противоположное отношение может и не иметь места. 2. Топологическим отношением ϕоб между картографическими объектами X1∈K и X 2 ∈K карты K будем называть отношение, которое сохраняется между данными объектами при различных аффинных и топологических преобразованиях. Топологическое отношение между объектами одного слоя обозначается следующим образом: X1ϕоб X2 (картографический объект X1 имеет топологическое отношение ϕоб с объектом X 2 ). Противоположное отношение может и не иметь места. 3. Топологическим отношением ϕсл между слоями s1∈S и s2 ∈S назовем отношение, которое сохраняется между данными слоями при различных аффинных и топологических преобразованиях между объектами, находящимися в слоях s1 и s2 соответственно: s1ϕсл s2 (слой s1 имеет топологическое отношение ϕсл со слоем s2 ). Обратная запись может и не иметь места. Рассмотрим следующие типы топологических отношений между картографическими объектами: соседство, изолированность, близость, вложенность и др. Эти топологические отношения наиболее полно отражают взаимодействие пространственных объектов. Отношение „Соседство“. Картографический объект X1∈K находится в соседстве с объектом X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Соседство“ α , т.е. X1αX2 тогда и только тогда, когда картографические объекты X1 и X 2 имеют общую граничную точку или линию, т.е. если есть совпадение координат точек обоих объектов. Отношение „Соседство“ выполняется ( X1αX2 ), если оно антирефлексивно, симметрично, транзитивно и пересечение картографических объектов X1 и X 2 есть непустое множество, т.е. X1 ∩ X 2 = A , A ≠ Ø и непустое множество А должно состоять только из граничных точек картографических объектов X1 и X 2 . Отношение „Изолированность“. Картографический объект X1∈K изолирован от объекта X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение изолированности δ , т.е. X1δX 2 тогда и только тогда, когда объекты X1 и X 2 не пересекаются друг с другом. Отношение „Изолированность“ выполняется ( X1δX 2 ), если оно антирефлексивно, симметрично, транзитивно и при этом выполняется условие X1 ∩ X 2 = Ø . Отношение „Близость“. Картографический объект X1∈K находится в близости к картографическому объекту X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Близость“ β , т.е. X1βX 2 тогда и только тогда, когда картографический объект X1 расположен на заданном расстоянии от картографического объекта X 2 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Формальное представление характеристик пространственно-распределенных объектов 27
Отношение „Близость“ выполняется ( X1βX 2 ), если оно антирефлексивно, симметрично,
транзитивно и при этом выполняется следующее условие: картографические объекты X1 и
X 2 не должны пересекаться между собой, т.е. X1 ∩ X 2 = Ø . Минимальное расстояние между
граничными точками объектов X1 и X 2 не превышает заданного расстояния ρз , т.е.
min ρ(a, b) ≤ ρз , где a, b — граничные точки картографических объектов X1 и X 2 соответственно; ρ(a, b) — расстояние между граничными точками а и b.
Отношение „Вложенность“. Картографический объект X1∈K вложен в картографи-
ческий объект X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Вложенность“ γ , т.е. X1γX 2 тогда и только тогда, когда все элементы объекта X1 находятся
внутри объекта X 2 .
Отношение „Вложенность“ выполняется ( X1γX 2 ), если оно рефлексивно, асимметрично,
нетранзитивно и при этом X2 ⊆ X1.
Отношение „Пересечение“. Картографический объект X1∈K пересекается с картогра-
фическим объектом X 2 ∈ K , или между X1 и X 2 установлено топологическое отношение „Пересечение“ χ , т.е. X1χX 2 .
Отношение „Пересечение“ выполняется ( X1χX 2 ), если оно рефлексивно, симметрично,
транзитивно и X1 ∩ X 2 = Ø . Для более полного описания положения объекта городской инфраструктуры введем от-
ношения, которые характеризуют геометрическое расположение пространственных объектов:
параллельность и перпендикулярность.
Картографический объект X1∈K параллелен объекту X 2 ∈ K , или между X1 и X 2 установлено геометрическое отношение „Параллельность“ η, т.е. X1ηX 2 тогда и только тогда,
когда в объектах X1 и X 2 можно найти по одному линейному сегменту, которые параллельны между собой, т.е.
(∃xk ∈ X1, ∃xl ∈ X 2 ): xk || xl ,
(7)
где xk , xl — линейные сегменты.
Объект X1∈K перпендикулярен картографическому объекту X 2 ∈ K , или между X1 и X 2 установлено геометрическое отношение „Перпендикулярность“ µ , т.е. X1µX 2 тогда и
только тогда, когда в объектах X1 и X 2 можно найти по одному линейному сегменту, которые перпендикулярны друг другу, т.е.
(∃xk ∈ X1, ∃xl ∈ X 2 ): xk ⊥ xl .
(8)
При анализе карты города было выявлено, что часть пространственных объектов по
различным признакам сгруппирована в отдельные структуры. Следует отметить, что в струк-
туру могут входить объекты не только из одного, но и из разных слоев. В результате если
формально описать такие структуры, то карта будет представлять собой совокупность струк-
тур с учетом взаимосвязей входящих в них объектов.
Топологическая структура — это совокупность картографических объектов, связанных
между собой топологическими и геометрическими отношениями, она задается следующим
образом:
T = (W , Π, Φ) ,
(9)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
28 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
где W ={X1, X2 , ..., Xn} — подсистема картографических объектов из разных слоев, n — ко-
личество объектов подсистемы; Π ={ρk } (k =1, 2, ..., h) — множество типов топологических
и
геометрических
отношений
в
подсистеме
W,
h
—
количество
отношений;
Φ
=
⎣⎡ϕi(jk
)
⎤ ⎦
(i, j =1, 2, ..., n) — матрица топологических отношений между объектами из подсистемы W .
Элемент ϕi(jk) = 0 , если не существует взаимодействия между объектами Xi и X j . Эле-
мент ϕi(jk) есть топологическое отношение k-го типа, если существует связь между слоями
Xi и X j .
Рассмотрим простейший пример расположения объектов в двумерном пространстве
(рис. 1). Здесь показаны отношения объектов A и В1, В2, В3, В4 (объекты A и В1 не вложены
друг в друга, A и В1 — соприкасаются, A и В3 — пе-
B4 B3
A—
B1 A°
ресекаются, A и В4 — один объект включает в себя другой).
Когда рассматривается отношение объектов трехмерном пространстве, необходимо анализировать и высотную составляющую объектов. На рис. 2
B2 ∂A
показаны возможные комбинации расположения объектов А и Вn по высоте, где n — один из воз-
Рис. 1
можных вариантов расположения объекта В (первый вариант — один объект включает в себя другой,
второй и седьмой — один объект находится на некотором удалении по высоте от другого,
третий и шестой — касание границы, четвертый и пятый — пересечение границы [2]).
A–3u В3
В4
В2 ∂uA
В1 A°3
В5
В6 A–3d
∂dA В7
Рис. 2
В основу метода описания трехмерных топологических отношений положим математическую модель „девяти пересечений“ Эгенгофера [3], которая использует пересечения различных составных элементов объектов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Формальное представление характеристик пространственно-распределенных объектов 29
Часть точек пространства в множестве A, расположенная во внутренней части объекта и
обозначенная А°, является объединением всех открытых множеств в A. Замкнутое выражение
A, обозначенное A⎯, является пересечением всех замкнутых множеств A. Внешняя часть A, относящаяся к вложенному пространству R2, обозначенному A⎯, является множеством всех точек R2, не содержащихся в A. Граница A, обозначенная ∂A, является пересечением замкнутого выражения А и замкнутого выражения внешней части A. Тем самым выполняется фор-
мальная характеристика расположения объектов на плоскости.
Для описания положения объекта в трехмерном пространстве введем дополнительные
обозначения. Часть точек трехмерного пространства, расположенную во внутренней части объекта, обозначим как А°3. Внешняя часть объекта будет представлять собой две непересекающиеся области A⎯3u (над объектом) и A⎯3d (под объектом). Верхняя граница A, обозна-
ченная ∂uA, является пересечением замкнутого выражения А и замкнутого выражения верх-
ней внешней части A. И соответственно нижняя граница A, обозначенная ∂dA, является пересечением замкнутого выражения А и замкнутого выражения нижней внешней части A.
Таким образом, пространственная область определена как трехмерное множество точек,
которое является гомеоморфным к пяти областям, т.е. каждая из восьми объектных частей
области в трехмерном пространстве (внутренняя часть, граница и внешняя часть) — непустая
и связанная.
Бинарное топологическое отношение между двумя областями А и B характеризуется как
сравнение границы (∂A), внутренней части (А°), внешней части (A⎯) на горизонтальной плоскости и верхней, нижней границ (∂uA, ∂dA), внутренней части (А°3), верхней и нижней внешних частей (A⎯3u, A⎯3d) в вертикальной плоскости объекта A с границей (∂В), внутренней частью (B°), и внешней частью (В⎯) на горизонтальной плоскости и верхней, нижней границ (∂uВ, ∂dВ) внутренней части (В°3), верхней и нижней внешних частей (В⎯3u, В⎯3d) в вертикальной плоскости объекта B. Эти четырнадцать объектных частей объединены так, что меж-
ду ними существует шестнадцать пересечений, которые представляют топологические отно-
шения между этими двумя объектами.
Естественно, это не все возможные комбинации топологических характеристик, но рас-
смотрев рис. 2, будем считать, что этими отношениями можно описать взаимодействие
объектов в дополнение к плоскости в трехмерном пространстве.
Топологическое отношение между областями А и B кратко может быть представлено
как матрица 4×4, назовем ее „16 пересечений“.
⎡ ∂A∩∂B
⎢
R16
(
A,
B)
=
⎢ ⎢
⎢
Ao ∩∂B A− ∩∂B
⎢⎣∂uA∩∂dB
∂A∩ Bo Ao ∩ Bo A− ∩Bo
∂dA∩∂uB
∂A∩ B− Ao ∩ B− A− ∩B− ∂dA∩ Bo3
A−3d ∩ Bo3 ⎤
A−3u ∩ Bo3 ∂uA∩ Bo3
⎥ ⎥ ⎥ ⎥
.
Ao3 ∩ Bo3
⎥ ⎦
Топологические отношения характеризуются топологическими инвариантами „16 пере-
сечений“, т.е. свойствами, которые сохраняются при топологических преобразованиях. Со-
держание этих шестнадцати пересечений было идентифицировано как самый простой и об-
щий топологический инвариант, хотя другие могут быть полезны как компоненты пересече-
ния и их измерения. Инвариант содержания характеризует каждое из этих шестнадцати пере-
сечений значением „пустое“ (∅) или „непустое“ (¬∅). С различением „пустое/непустое“ этих шестнадцати пересечений потенциально можно получить 216 различных топологических от-
ношений. Два из этих топологических отношений сохраняются между любыми двумя областя-
ми. Шестнадцать пересечений „пустое/непустое“ описывают набор отношений, которые обес-
печивают полный охват — три объектные части: граница, внутренняя часть и внешняя часть.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
30 Д. Е. Андрианов, С. С. Садыков, В. В. Фролов
Содержания их пересечений такие, что любое множество является или пустым, или непустым. Фактическое число возможных отношений зависит от измерения пространства относительно объектов и от топологических свойств объектов, вложенных в это пространство. Например, граница линии (нециклической), т.е. множество ее начальных и конечных точек, является разделенной, тогда как граница области без отверстий является соединенной, и различие в этих топологических свойствах влияет на то, какие топологические отношения могут быть реализованы.
Для хранения в памяти одного топологического отношения между картографическими объектами достаточно шестнадцати бит. Формализованная выше структура будет состоять из набора бинарных таблиц, достаточно простых в хранении и анализе.
СПИСОК ЛИТЕРАТУРЫ
1. Еремеев С. В., Садыков С. С. Автоматический контроль размещения пространственных объектов на цифровой карте с использованием топологических отношений // Информационные технологии. 2005. № 8. С. 6—9.
2. Андрианов Д. Е. Создание метода представления топологических отношений в трехмерном пространстве для задач городских ГИС // Геоинформатика. М.: ВНИИгеосистем, 2007. № 2. С. 1—3.
3. Egenhofer M. J. and Franzosa R. D. Point-set topological spatial relations // Int. J. of Geographical Inf. Systems. 1991. Vol. 5, N 2. Р. 161—176.
Дмитрий Евгеньевич Андрианов Султан Садыкович Садыков Владислав Валерьевич Фролов
Сведения об авторах — канд. техн. наук, доцент; Муромский институт (филиал) Владимир-
ского государственного университета, кафедра информационных систем; E-mail: AndrianovDE@inbox.ru — д-р техн. наук, профессор; Муромский институт (филиал) Владимирского государственного университета, кафедра информационных систем; E-mail: SadykovSS@yandex.ru — аспирант; Муромский институт (филиал) Владимирского государственного университета, кафедра информационных систем; E-mail: AndrianovDE@inbox.ru
Рекомендована кафедрой информационных систем
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2