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-
