ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001
3.2 Searching connector of a specified line
The connector of a line object is found by searching the connector
object corresponding with the center of the MBR of line object on
GBD-tree, because the connector is located at the center of the
MBR. In the following sentence, we describe the procedure to find
the connector of link L on GBD-tree, when link L is specified.
(Step.1) Let T be the root node.
(Step.2) If T is not leaf node, each offspring node E is checked
whether the MBR of E includes the center of the MBR of L. If
so, for all including nodes, search the connector of L on
sub-tree whose root node is E.
(Step.3) If T is a leaf node, check all connectors under the node
whether its location accords to the center of the MBR of L.
3.3 Searching connector of a specified region
To find the connector of the region that includes the specified
point, it is necessary to restore the region, and to find the
connector located in the region.
In the implicit topology model, a region consists of a boundary and
a connector (the representative point). The boundary consists of a
collection of line segments (links). The connector is placed inside
the region, and is used to connect the attribute information of the
region.
Region restoration is a procedure to restore the shape of a region.
This procedure is necessary in several operations including to
restore the shape to display and to know the attribute of the region.
This procedure is written as follows.
(Step 1) Find one of the boundary line segments of the
specified region. This can be done by retrieving the rightmost
boundary line segment on the horizontal line stretched from
the specified point P, as shown in Figure 5. Let the found line
segment S. This operation can be executed efficiently on
GBD-tree.
(Step 2) Follow the line segments forming the specified region
counter-clockwise from S to return back to S. At the end of S,
the next segment can be found as follows. In Figure 6, let link L
be a boundary line segment of which either end is N. Expand
the node to find all line segment meeting at N. Then, determine
the line segment located counter-clockwise neighboring to line
L. Repeat the same operation at the end of the opposite side
end of the segment until return back to link L. After the
operation, all line segments consisting of the region are found.
Figure 5 summarizes the operations.
Then to find the connector of the region R that includes the
specified point, it is necessary to find the connector located in the
region R on GBD-tree. This procedure is written as follows.
(Step.1) Let T be the root node.
(Step.2) If T is not leaf node, each offspring node E is checked
whether its MBR overlapped with the MBR of R. If so, for all
overlapping nodes, search the connector of R on sub-tree
whose root node is E.
(Step.3) If T is a leaf node, each connector under T is checked
whether it is located in R.
3.4 Searching line entity corresponding to a specified
connector
When some attributes are specified to display the line segments
meeting the conditions, the connector that satisfies the condition
are retrieved. The shape of the line is searched by spatial retrieval
in the way the center of the line locally corresponds to the
connector.
This retrieval can be performed on GBD-tree as follows.
(Step.1) Let T be the root node.
(Step.2) If T is not leaf node, each offspring node E is checked
whether its MBR include the location of the connector. If so,
for all including nodes, search the line on sub tree whose
root node is E.
(Step.3) If T is a leaf, each entity under the node is checked
whether the center of its MBR according to the location of
the specified connector. If so, it is the line object according
to the specified connector.
3.5. Searching region corresponding to a specified
connector
The connector of a region is located in the region, so when a
connector is specified to restore the region, the procedure can be
done by the same procedure described in 3.3.
