Full text: The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics

ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
219 
. The most 
ithod. This 
it implicitly, 
il retrieval 
s are now 
at and an 
nventional 
hnique[11] 
s restored 
used them 
•educed to 
l section 3, 
jrmation is 
lod and its 
t, including 
litions and 
I section 5. 
limited in 
sographical 
jorized into 
ig on their 
jildings can 
;an be dealt 
s. Here we 
;it topology 
work. In this 
iach other at 
iks and the 
logy model, 
iology of the 
id, describe 
nctions. This 
ugh spatial 
cified link are 
found by a spatial retrieval specifying the end point of the link. The 
spatial retrieval returns the links of which one endpoint meets at 
the same position with the specified end point. In this paper, this 
operation is called as 'node expansion’. 
To perform such an operation at high speed, a special data 
structure, so called spatial data structure, is necessary. Several 
kinds of spatial structures, including R-tree[6], R*-tree[7] and 
GBD-tree[8], have been proposed. In this paper, GBD-tree, which 
is developed one of the authors, is used to manage spatial data. 
The algorithms described in this paper can be widely applicable to 
other types of spatial data structures. 
In the implicit topology model, the attributes and the geometrical 
shape of the entities are managed separately. When 
correspondence among them is necessary, they are combined by 
spatial retrieval. Figure 2 shows a line object (e g. road), and the 
object has attributes (e.g. name of the road, width of the road, 
number of traffic lanes). Usually, when a GIS displays the entities 
on CRT, all attributes data are not always necessary. Thus, it is 
sufficient that the attributes can be retrieved when they are 
requested. Then, if the shape and the attributes are separated, 
the time required to read the entities from a hard disk can be 
shortened. For the reason mentioned above, it is preferable that 
the shape and the attributes are managed separately even on 
explicit topology based GIS. 
In the implicit topology model described in this paper, the 
attributes and geometrical shape are also managed separately. 
The shape and the attributes are related to each other by their 
position. Lines and regions have extent in two-dimensional space. 
Then, to determine their positions, a unique point, or 
representative point of the object is necessary. We determine the 
point as the center of the minimum-bounding rectangle (MBR) of 
the object, as shown in Figure 2. The attributes are located at the 
representative point. Hereafter, we call the representative point 
the ‘connecter’, in the sense that it connects the shape and the 
attributes. 
To generate the relationship between the shape and the attributes, 
two inverse directional operations are necessary: (1) find the 
attributes (connector) from the shape, and (2) find the shape from 
the connector. The details of these operations are described in 
section 3. 
Regions are expressed by a set of borderlines, as shown in 
Figure 3. Each closed area divided by the borderlines is a region. 
In the implicit topology model, all borderlines are also not mutually 
explicitly related. Hence, the shape of a region must be also 
restored by using node expansion. 
The attributes of a region are related to the geometrical shape by 
the connector. In the case of region, the connector is placed 
somewhere inside the region. Because the shape of region is 
varied, it is not easy to determine a rule for placing the connector. 
For this reason, the position of the connector is restricted only to 
somewhere inside the region, as shown in Figure 3. To determine 
the attributes of a region, the following steps of operations are 
necessary: (1) restore the shape of the region, (2) find the position 
of the connector by searching inside the region, then (3) read the 
attributes related to the connector. 
Summarizing the operations used in the implicit topology GIS, the 
followings basic generations are necessary: 
(1) node expansion 
(2) generation of correspondence between the shape and 
the connector of line objects 
(3) generation of correspondence between the shape and 
the connector of region objects 
By combining these basic operations, more complicated 
geographical operations, such as the shortest path finding, are 
realized. 
3. OPERATIONS TO RESTORE TOPOLOGY 
3.1 Spatial operation for restoring topology 
Figure 1 showed a simple example of topology. In explicit 
topology description, relation tables or pointers describe the 
connective relationships among L-1, L-2, L-3 and N, allowing us to 
easily recognize the links that are connected to each other by 
referring to them. On the other hand, a GIS based on implicit 
topology description must restore the relation by spatial retrieval. 
In STIMS, GBD-tree is used for this purpose. The GBD-tree is a 
multi-dimensional data indexing structure Figure 4 shows the 
structure. As shown in this figure, each node has M slots. Each 
slot in non-leaf nodes has a pointer to the child node, its 
minimum-bounding rectangle (MBR) and the center point of the 
MBR for indexing. The MBR is the tightest rectangle bounding all 
entities contained in offspring nodes. A slot in the leaf nodes has 
pointer to the entity, MBR of the entity, and the layer of the entity. 
Spatial retrieval can be done efficiently by referring to the MBR. 
As mentioned in Section 2, node expansion is a basic operation 
for restoring topology. This operation can be performed by 
searching the links of which an endpoint meets the position of the 
node. Following shows the procedure of searching the links 
connected to node N on GBD-tree. 
(Step.1) Let T be the root node. 
(Step.2) If T is not a leaf node, each offspring node E is checked 
whether the MBR of E includes the location of node N. For all 
including nodes, search the links connected to node N on the sub 
tree whose root node is E. 
(Step.3) If T is leaf node, all entities under the root node are 
checked whether an end point of it meets the position of 
node N. If so, the entity is connected with node N. 
Fig.4 Hierarchical structure ofGBD-
	        
Waiting...

Note to user

Dear user,

In response to current developments in the web technology used by the Goobi viewer, the software no longer supports your browser.

Please use one of the following browsers to display this page correctly.

Thank you.