by R. G. Newell and M. Doe
Abstract
Modern GIS systems go to great lengths to model a seamless world containing a
rich topological model. However, there is a requirement, particularly among utility
companies such as electricity and telecommunications companies to model their network
in both geometric and, possibly, multiple schematic coordinate systems. The schematics
may hold an alternative representation or a detail of par of the network. This
paper describes an elegant method of modelling such situations so that topology
is handled seamlessly and data common to the alternative
representations is not replicated. The technique, known as ‘multiple worlds ,
is a natural and straightforward extension of the spatial indexing techniques used
to handle a seamless database efficiently. One of the benefits of the approach
is that any network analysis application written to work in a single coordinate
world will work unchanged in a multiple world situation. Applications include the
integration of electricity substation schematics within a geographic database,
facilities management, multi-sheet schematic applications such as power systems
diagrams as well as P&ID diagrams in chemical plant applications.
Introduction
The work reported in this paper was carried out as a result of the requirement
to model complex network applications, particularly in the electricity supply and
telecommunications industries. The ideas presented have been developed within Smallworld
GIS. Smallworld GIS is one of a number of systems whose origins lay more in database
management foundations than in file and CAD foundations (Chance et al. 1990, Easterfield
et al.1990). In such systems, the underlying principle is that the GIS manages
a single logical database that manages both spatial and aspatial data together.
The principle extends to cases where the data is held in multiple existing (legacy)
databases.
One of the benefits of this approach is that the spatial data can be modelled
as it really is – a seamless carpet of topologically structured geometry. Such
an architecture requires different solutions to those implemented in tile-based
systems. In particular, spatial organisation is very important so the system gives
a good response time for spatial queries on very large seamless databases. There
are many successful spatial indexing schemes (Abel 1983, Abel 1984, Batty 1990,
Bundock 1987, Guttman 1984, Kriegel 1990, Libera 1986, Newell 1991, Samet 1989,
Seeger 1988, Smith 1990). In this paper we briefly describe the method employed
in Smallworld GIS. For a fuller explanation see Newell et al. 1991.
Although much has been written about managing spatial data within one coordinate
system, less has been written on managing data in multiple coordinate systems,
including cases where there is a topological structure, but possibly no corresponding
spatial coordinate data: for example, a complex junction where a large number of
inputs are connected to corresponding outputs using a connection’matrix’.
A common example of multiple coordinate systems in the electricity supply and
telecommunications industries is schematic diagrams of parts of a network where
there is too much detail to represent the structure in the ‘geographic’ coordinate
system. Such a case arises with substation schematics. Figure 1 shows such an example,
where a substation at Barnes Road has 3 separate representations, one geographic
and 2 schematic, as well as a duct containing cables represented geographically
and as a cross-section.
[Figure not yet available]
Figure 1: Geographic, schematic and cross-section representations
On the face of it, one might think that a tile-based architecture is more suited
to handling such situations, since presumably such systems have ways of handling
connections across tile boundaries. We hope to go on to show in this paper an elegant
approach that maintains connections across multiple coordinate systems without
incorporating any other compromises into the system.
Handling Topology
Smallworld GIS models the world as a collection of objects that have relationships
and attributes. Complex object relationships are modelled by one-to-one, one-to-many
or many-to-many relations that are defined in a CASE tool. Object attributes are
aspatial (represented as numbers or characters for example) and spatial (represented
as points, chains and areas). An aspatial attribute may be defined as a ‘logical’
attribute; such an attribute is not defined in the database, it is always derived
by a method on the object when needed.
[Figure not yet available]
Figure 2: Smallworld Object Structure
Topological relationships are modelled by points, chains and areas sharing nodes,
links or polygons. A chain consists of a linear sequence of links (xy or xyz coordinate
strings) and an area consists of a contiguous set of polygons. The two level structure
allows for a much richer modelling of topology than a layer based approach. Figure
2 shows an idealised representation of the structure underpinning the Smallworld
topology model. One object may have multiple geometries and many objects may share
one geometry.
Spatial Organisation
The Smallworld GIS Version Managed Datastore holds all of its spatial and aspatial
data seamlessly; there are no tiles or layers. The basic storage structure is tabular,
but unlike a conventional relational database, the access language is the object-oriented
language, Smallworld Magik. Fast spatial retrievals are achieved by means of an
improved quadtree indexing technique, which neither complicates nor compromises
the logical data structure described above. The primary key of all spatial data
contains an automatically generated ‘spatial key’. The method both clusters data
spatially on disk and provides an efficient index; Figure 3a illustrates how a
simple quadtree index can sometimes produce an inefficient index. Figure 3b illustrates
the overlapping quadtree index in which a small overlap produces additional digits
in the key.
[Figure not yet available]
Figure 3a: Traditional Quadtree Index
[Figure not yet available]
Figure 3b: Smallworld Overlapping Quadtree Index
Because the spatial key is not necessarily unique for two objects in proximity,
it is extended by an automatically generated unique identifier (see figure 3c).
Quadtree key Unique id
Figure 3c: Unique spatial key
Multiple Worlds
Although it is essential in many cases to model a seamless real world with a seamless
geographic database, there are also cases where some information needs to be handled
in a different coordinate system – a different world. Examples include applications
where part of the model is represented as a drawing schematic, either as an alternative
representation or as an expanded detail of part of the geographic world. An example
of the latter is a schematic that represents the internal structure of an electricity
substation. In such cases, although the geometry may be spread across different
coordinate systems, it is important to handle the topology seamlessly, so that
applications such as network analysis can work across multiple worlds unhindered
by modelling artifacts.
Implementation
Smallworld GIS handles multiple worlds as an extension to the quadtree indexing
scheme described above. The spatial index can be extended to include extra high
order bits. In this way topological tracing operations work in an identical manner
regardless of whether the geometry is in a single coordinate system or multiple
coordinate systems. Figure 4 shows how the spatial key is extended to handle multiple
worlds,
World Id Quadtree Key Unique id
Figure 4: Structure of Smallworld spatial
index.
A further extension of this idea allows the data to be partitioned according to
various non-spatial criteria. In Smallworld GIS, this technique is used to control
both drawing priority and to implement the idea of multiple worlds. A number of
high order bits are reserved to store a world ID. The next block of bits is reserved
to store drawing priority (see figure 5).
The clustering properties of the spatially indexed database will ensure that all
geometry in a particular world will be clustered on disc and it is therefore very
efficient to scan for geometry within one world.
The spatial scanners, used by the GIS in hit-searching and in screen refresh,
can be constrained to find data which has a particular world ID. Hence, viewing
and interaction with the spatial database is made world-specific.
Types of World
There may be many types of world in a GIS. Each world type typically has a different
meaning for the geometry it contains.
Geographic worlds represent the location of objects in the real world. This geometry
may or may not have associated topology.
Schematic worlds have geometry which represents the existence of objects and possibly
their topology, but does not carry any real-world positional information.
Cross Section worlds are essentially geographic, i.e. geometry represents real
world locations of objects, but use a coordinate system in which the x axis represents
distance along some arbitrary direction and the y axis represents vertical position.
Worlds and Universes
There are a fixed number of bits available to be shared between the spatial index,
drawing priority and world ID.
The number of bits used for the spatial index (together with the overall extents
of the scanned area) determines the size of the smallest quad-tree box and hence
the resolution of the quad-tree. This, in turn, affects the efficiency of hit-searching
and graphics re-draws. In a world which is densely populated and which has many
geographically small objects, a relatively fine resolution would be required. Conversely,
a world with very little geometry, or with very sparse geometry, can be scanned
with coarser resolution.
The number of bits used for the world ID and for drawing priority determines the
total number of worlds and priorities that can exist in the database. Hence, there
are competing requirements which have to be juggled to achieve a compromise allocation
of bits.
Using the topmost few bits of the spatial index to store a ‘universe id’, each
‘universe’ uses a different allocation of the rest of the bits. This allows each
universe to contain worlds with certain characteristics. A geographic universe
may contain just one world and hence uses its remaining bits to obtain maximum
spatial resolution. A substation internals universe or cross-section universe would
need to contain a large number of worlds, but each world is small and has little
geometry in it. We can therefore use up a large number of bits to store the world
ID, leaving relatively few for the spatial index without performance loss. A universe
for network schematics lies somewhere between the previous two examples: there
may be a relatively small number of schematic diagrams and the diagrams will be
relatively sparsely populated compared with the geographic world. Figure 5 shows
the full structure of the spatial key.
Universe World Drawing Quadtree Unique Id Id priority Key id
Figure 5: Complete structure of spatial key
Alternative Representations of Objects and Networks
An object may be represented in several worlds and it may take a different form
in each. For example, an electricity substation is represented in the geographic
network by an area which is its boundary. In a schematic diagram, however, the
substation is represented as a collection of transformers, busbars and switches.
A cable or pipe may be represented by its centre line (chain) geometry in the
geographic world, but by a point in the world owned by a cross section object.
The cable may appear in many cross sections.
A network may also have more than one representation. An electricity network,
for example, may be represented in the geographic world by a connected network
of cables, overhead lines and joints, and in a schematic world as a connected network
of load sections. Both collections of geometry describe the same network.
Connections Between Worlds
Topological connections from one world to another may be made with a special object
called a hypernode. This object has two point geometries, one in each world. This
allows network traces to jump from world to world. For example, a network trace
in an electricity network may arrive at a substation, jump into its internals world
follow the geometry related topology inside it, then jump back out into the network
again.
Hypernodes are a simple example of a multi-pin device and can be given special
behaviour to change the trace state, or to prevent certain types of trace from
jumping.
Complex Objects
An object may have a very simple representation in the network but may have considerable
internal topological complexity which is hidden from the outside world. This internal
topology may be implemented in a number of ways:
Objects with Internals worlds
Each object owns its own internals world. The internal topology of the object
is associated with geometry in that world.
For example, an electricity substation has components: busbars, transformers and
switches, which have their geometry in the owning substation’s internals world.
These components form an internal topological network for the substation.
Multi-pin-devices
These are objects with several connection pins (point geometries). The number
of pins may be fixed, as in a simple switch or junction box, or dynamically variable
– pins may be added or removed as required by the user.
External connections to the network are made to these pins, but the internal topology
of the object is encapsulated as behaviour on the object itself. This topology
may be implemented as a hard coded set of rules, which may refer to attributes
of the object itself or to other conditions, or as a connectivity table which may
be updated by the user.
For example, the following pseudo-code describes a method on a simple switch object
which responds to the message ‘connectivity_trace’ from the network tracer.
method simple_switch.connectivity_trace(pin)
if self.closed
then if pin = input_pin
then return output pin
else return input_pin
endif
else
return unset
endif
A multi-input/output junction box may have an associated connectivity table. When
asked for output pins connected to a particular input pin, the junction box will
perform a lookup of this table and return a number of pins. Records may be added
to or removed from this table as connections are made or broken in the junction
box.
Objects with trace behavior
These are objects with simple, geometry related topology but which have behaviour
which modifies that simple topology in some way.
For example, a road_junction may have a single node in the road network, which
may be connected to several roads. However, when asked for exit roads given a particular
approach road, the junction object overrides the simple topology (in which all
roads which join that junction are connected) and may take into account such things
as one way streets or restricted access. The road junction may also assign various
costs to these transitions; turning right (in the UK) may be a more costly move
than going straight on or turning left.
As with the multi-pin device, this internal topological complexity may be defined
algorithmically or by table lookup, or some combination of the two. There may be
a dependence on various internal external parameters such as the day of the week,
or the angle between approach road and exit road at a roundabout.
Encapsulating topology inside objects in this way allows us to simplify the geometry
of topologically complex networks. In a fibre-optic cable network, for instance,
each cable may contain 256 fibres and at each junction, the connections between
individual fibres must be modelled. However, the cable can be modelled by a single
chain and when network traces are carried out, the current fibre number is carried
as an attribute of the trace. The junction objects can use this attribute to determine
connectivity and will modify it when passing back output cables. Hence, the network
tracer will ask the junction “I have arrived along this cable on fibre number
125. Give me connected output cables and corresponding fibre numbers”.
Conclusion
The approach described in this paper to handling topologically structured data
in multiple coordinate systems is a simple and natural extension to the spatial
indexing techniques employed to organise a single large seamless geographic database.
The method is elegant in that it adds no complexity to the topological capabilities
of the system implemented for a single coordinate world. Even though geometry is
stored seamlessly, the spatial key implemented organises the data physically so
that data belonging to each coordinate system is stored contiguously in different
parts of the base datastore tables. The approach has been highly effective for
implementing complex models for a range of network applications.
References
Abel, D.J. & Smith, J.L. (1983): A Data Structure and Query Algorithm Based
on a Linear Key for a Rectangle Retrieval Problem, Computer Vision, Graphics, and
Image Processing 24,1, October 1983.
Abel,D.J. & Smith, J.L. (1984): A Data Structure and Query Algorithm for a
Database of Areal Entities, The Australian Computer Journal, Vol 16, No 4.
Batty, P. (1990): Exploiting Relational Database Technology in GIS, Mapping Awareness
magazine, Volume 4 No 6, July/August 1990.
Bundock, M. (1987): An Integrated DBMS Approach to Geographical Information Systems,
Autocarto 8 Conference Proceedings, Baltimore, March/April 1987.
Chance, A., Newell, R.G. & Theriault, D.G. (1990). An Object-Oriented GIS
– Issues and Solutions, EGIS ’90 Conference Proceedings, Amsterdam,, April 1990.
Easterfield, M.E., Newell, R.G. & Theriault, D.G. (1990): Version Management
in GIS Applications and Techniques, EGIS ’90 Conference Proceedings, Amsterdam,
April 1990.
Guttman, A. (1984): R-trees: A Dynamic Index Structure for Spatial Searching,
Proceedings of ACM SIGMOD Conference on Management of Data, Boston, June 1984.
Kriegel, H., Schiwietz, M., Schneider, R., Seeger, B. (1990): Performance Comparison
of Point and Spatial Access Methods, in Design and Implementation of Large Spatial
Databases: Proceedings of the First Symposium SSD ’89, Santa Barbara, July 1989.
Libera, F.D. & Gosen, F. (1986): Using B-trees to Solve Geographic Range Queries,
The Computer Journal, Vol 29, No 2.
Newell, R.G., Easterfield, M. and Theriault, D.G. (1991): Integration of Spatial
Objects in a GIS, Proceedings of Auto-carto 10, Baltimore March 1991, Volume 7,
pp 408-415.
Samet, H. (1989): The Design and Analysis of Spatial Data Structures, Addison
Wesley, 1990, ISBN 0-201-50255-0.
Seeger, B. & Kriegel,H. (1988): Techniques for Design and Implementation of
Efficient Spatial Access Methods, Proceedings of the 14th VLDB Conference, Los
Angeles, California, 1988.
Smith, T. R. and Gao, P. (1990): Experimental Performance Evaluations on Spatial
Access Methods Proceedings of the 4th Spatial Data Handling Symposium, Zurich 1990,
Vol 2, p991.