GeoToolKit is a C++ class library offering management of
persistent spatial data. It primarily is intended to
facilitate fast and easy development of scientific geo-applications.
It provides spatial data types in 3D Euclidean space:
0D-3D simplexes, 1D-3D complexes and compound
objects are supported as well as geometric operations, functions and
predicates. In coming releases also 4D (3D + time) types will be
available.
Evolved from experiences with
Geostore
(an information system for geologically defined geometries
developed in
SFB 350,
section
D4),
GeoToolKit has especially been designed to support geo-applications
that manage large amounts of spatial data in
connection with geometric functionality, such as fast spatial
queries. Following the object-oriented modelling technique, the
built-in general types, e.g. line segments, triangles and surfaces,
can be used to model more specific real world entities, for example
geological strata and faults. Applications of this kind simply
use or inherit as much spatial functionality from GeoToolKit
as needed.
Another principle design feature of GeoToolKit is its tight
coupling with the OODBMS ObjectStore®, since we consider
an OODBMS to be the most efficient way to handle spatial data types.
This introduction is divided into three chapters:
Sketches which needs GeoToolKit can satisfy and what the
user needs to work with it.
How is GeoToolKit organized, what exactly are its
capabilities? This second subsection tells you
everything about the data structure (classes and
associations), the functionality (geometric operations) and
the extensibility of GeoToolKit.
How does GeoToolKit serve to create a special geo-application?
Once understanding how GeoToolKit works, let the last section
introduce you in building geo-applications based on GeoToolKit.
1. Classification
Planning a geo-application, you generally will have
to solve at least three tasks:
Type resources
GeoToolKit's general data types are a complete set of 0D-3D
simplexes (point, segment, triangle, tetrahedron), 1D-3D complexes
(curve, surface, solid) and 1D-2D analytical objects (line and
plane). In addition, a compound object (group) can be used to
arrange an arbitrary amount of simplexes, complexes, analytical
objects and - again - groups into a new, standalone object. Thus,
new 3D data types can be modelled either directly by one of the
built-in types or by a specialization of a built-in type or by
a composition of these types. Object model
The main feature of GeoToolKit is its object model providing
its geometric types and operations: as you can see in
figure 2 (next
section) every concrete type is derived from an abstract spatial
object, called gtObj. gtObj defines an interface for
the spatial functions, predicates and operations as well as some
service functions that are to be common for all built-in and user-defined
spatial objects. Being abstract, every concrete spatial object must
redefine the underlying methods of this interface according to the
structure and the needs of
that object. For example, since every spatial object is bounded by
a bounding box, gtObj declares a function returning a
bounding box. This function must be redefined in every direct
derivation of gtObj and return the bounding box of the
corresponding type. Data management
As anticipated in the abstract, GeoToolKit uses the OODBMS
ObjectStore® to manage its spatial data. Like GeoToolKit,
ObjectStore®
is a C++ class library that must be linked to your application
(therefore you need access to the ObjectStore® software package).
This OODBMS offers some convincing advantages over relational DBMS:
First of all, simple geometric types as well as complex real world
objects are not splitted and distributed into relations but are
stored and retrieved as what they are - objects. This does not only
make the spatial data management easier to comprehend and to apply,
but it is the most essential requirement of efficient spatial data
access techniques. Furthermore, the object-oriented approach
facilitates the integration of own, user-defined types and methods.
The GeoToolKit library distinguishes four kinds of classes:
2.1 gtObj
Figure 3 shows a coarsely resoluted OMT diagram for this
class. The gtObj-interface can be divided into four
functional categories:
Easy functionality
Now, what is actually special about these predicates, functions and
operators? Data exchange - Import and Export Filters
Import: The class gtTriangleNet imports triangulated data of the following
formats:
2.2 Spatial Objects: The gtObj-hierarchy
As you already know from figures 1 and 2, there are currently 9
"standalone" spatial objects and one compound object
derived from gtObj.
Since it is more practical to sort the spatial objects by their
spatial classification, we will use these categories in the
following to order the classes.
One of the most important demands made on a geo-application is its
ability to perform fast spatial queries. The most important spatial
queries, in turn, are the following: gtRTree / gtObjRTree gtOcTree
This class serves as a distinct coordinate universe and container
class for spatial objects. While gtGroup is a compound object only
by technical aspects, gtSpace rather has an important conceptual
meaning: Inside GeoToolKit, it offers the highest abstraction level
of object grouping. Thus, gtSpace is also the main entry point
for spatial access paths.
In future versions of GeoToolKit, gtSpace is to be extended by the
following features:
Each spatial object is naturally enclosed by a minimal cuboid which
faces of
are parallel to the coordinate axes. This figure is called a
bounding box. In many cases it can save a lot of time to examine the
bounding box of an object instead of examining the object itself.
gtBoundBox is the GeoToolKit implementation of a bounding box. It
serves as the key structure of gtRTree as well as the query key for
the spatial access path interface gtAccessPath.
In the current stage of development, GeoToolKit solves at least the first
two problems.
Real world types (such as geological strata), easily are designed
by using GeoToolKit's types as base classes or aggregations to
manage the geometric part of the new type, completed with data
provided by the user.
In some cases, however, it may be neccessary to create a completely
new type. Then, apart from re-using GeoToolKit's types, you also can
create your own types as specializations of the most general
built-in type. The next section gives further information on this
topic.
With this basic approach the following is accomplished:
Therefore GeoToolKit cannot be used without ObjectStore®, but - in a
coming version - it can be used without knowledge about
ObjectStore®. This will be achieved by extending the capabilities of
the gtSpace class. Presently, gtSpace serves as a
container for sets of spatial objects and as the main entry point
for spatial access paths leading to the embedded objects. In future,
gtSpace will also be a service center for easy database and
transaction management.
All these types are specializations of the abstract masterclass
gtObj that declares the interface for all geometric
predicates, functions and operations that are common for all
the types above.
point
(gtPoint), segment
(gtSegment),
triangle (gtTriangle) and
tetrahedron (gtTetrahedron)
polyline (gtPolyLine),
triangle network (gtTriangleNet) and
tetrahedron network (gtTetraNet)
line (gtLine),
plane (gtPlane)
group (gtGroup)
gtPolyLineCursor, gtTriangleNetCursor,
gtTetraNetCursor and gtGroupCursor
Figure 2 shows an OMT-diagram of the most important GeoToolKit
types.
To understand the most important substructure of the GeoToolKit
architecture, lets first have a look at the interface class
gtObj, the most general spatial object defined in the
library. Note: In the following, the term "spatial
object" is used in equivalence to "class within the
gtObj-hierarchy".
Functions checking whether a particular unary or binary
spatial relation is fulfilled or not. They return
"false" (0) or "true" (not 0),
respectively.
Unary or binary functions computing new data on objects or
pairs of objects, returning a type which is not a member of
the gtObj-hierarchy.
Like spatial functions, but creating and returning new
spatial objects (i.e. types within the
gtObj-hierarchy).
Functions not belonging to the above categories, returning
non-geometric information or performing non-geometric
actions.
Spatial predicates:
intersects tests whether two spatial objects
intersect each other (touch is taken as intersection).
The binary predicate contains checks whether
a spatial
object contains another one, while equality of two objects is tested
by the predicate equal.
Spatial functions: The unary function
getBoundBox returns the bounding box of the
corresponding object and distance computes the shortest
distance between two objects.
Spatial operators: The operator intersection
determines the intersection of two spatial objects, with a new
spatial object as result. projection computes the
projection of a spatial object onto a given plane, and
clone returns a copy of the object itself.
division cuts a spatial object
into pieces: it separates everything lying on one side of
a given plane from everything lying on its other side (if an object
lies on both sides, it will be cut and the resulting "halfs" are
returned separately). Furthermore, cut
, erase and
paste methods are available.
They modify the part of an object lying insideof a given bounding
box.
The non-geometric service functions mainly are used internally and
therefore are described in the GT Library section.
Well, for instance, let us assume you have two sets of spatial objects
of arbitrary types and you need the geometric intersection of these two
sets. Note that you know nothing about the types of these objects,
since they are - again - results of another geometric operation.
How to compute their intersections then?
Since the intersection method is defined for
every
combination of two spatial objects, the virtual function table
mechanism of C++ automatically determines the correct intersection
method for an arbitrary pair of spatial objects. Therefore, also
objects that only are accessible via general spatial object
references or pointers, can easily be intersected.
Even better: this mechanism also works for new, user-provided
spatial objects.
During the import, the data can be run through various integrity
checks.
Export: Every spatial object can be exported to VRML 1.0 and the new
format VRML97.
Since derived from gtObj, they all share the basic functionality
of a spatial object. In addition, each class provides its own
type-specific predicates, functions and operators. The 9 standalone
spatial objects can be subdivided in two ways: according to their
dimensionality as well as according to their spatial
classification.
Currently, the first four dimensions (0-3D) are supported and the
spatial classifications are "simplex", "complex"
and "analytical".
Only the compound
object evades any classification, because it can hold any combination
of spatial objects.
gtPoint models a geometric point in 3D.
Class-specific functionality:
gtSegment models a geometric line segment defined
by two 3D points.
Class-specific functionality:
gtTriangle models a geometric triangle defined by three 3D
points.
Class-specific functionality:
gtTetrahedron models a geometric tetrahedron defined by four 3D
points.
Class-specific functionality:
gtPolyLine models a sequence of points in 3D space,
connected by line segments.
Class-specific functionality:
gtTriangleNet models a triangle network in 3D space.
Class-specific functionality:
At any stage of the object's lifetime, the user may
switch between optimations.
gtTetraNet models a tetrahedron network in 3D space.
Class-specific functionality:
These two types differ from the previous types in a fundamental
point: they have infinite expansion. However, since there is no
infinity in discrete geometry, GeoToolKit only allows
these objects to be "as infinitely expanded as the underlying
data structure permits it".
gtLine models a line in 3D space.
Class-specific functionality:
Note:
If the intersection of an object of any type with a line
is needed and the line need not be locally restricted
(like a line segment), then the faster gtLine intersection
method should be preferred to the gtSegment intersection
method.
A common example (from computer graphics) is the selection
of every object that is crossed by a ray.
gtPlane models a plane in 3D space.
Class-specific functionality:
Note:
If the intersection of an object of any type with a plane
is needed and the plane need not be locally restricted
(like a surface), then the gtPlane intersection method
should be used, since it is much faster than the
specialized intersection methods of gtTriangleNet.
For this case, the computation of elevation lines is
an important example from geo sciences.
Every spatial object derived from gtObj can be "inserted"
into a gtGroup. gtGroup does not copy the object itself, but it only
stores a pointer to it. Thus, any set of spatial objects can be
organized as a new spatial object of a higher abstraction level.
The main difference between a normal set structure storing spatial
objects and gtGroup lies in the fact, that gtGroup again serves as a
spatial object, with all the functionality derived from gtObj.
Given a set of spatial objects and a query box.
This fact is taken into account by the definition of the most
general spatial index class of GeoToolKit, gtAccessPath.
a) Retrieve all objects completely contained by the
query box.
b) Retrieve all objects intersecting the
query box.
c) Retrieve all objects containing a specified 3D point.
gtAccessPath is an abstract interface class for concrete spatial
index classes being used in connection with GeoToolKit. It gets by
on only four central methods:
Every concrete derivation of gtAccessPath must implement at least
these functions in order to serve as a spatial index class.
Currently, an R*Tree and an OctTree is implemented.
gtObjRTree is used as the standard model for
externally installed access paths (see gtSpace for more information
about this topic). As well, it is used internally to speed up some
complex geometric operations, such as intersections of complexes.
Additionally, the user can provide own access paths in order
to use them instead of gtObjRTree .
Generally spoken, an RTree establishes a spatial order on a set of
geometric objects. The objects are organized in a tree according to
their positions in space which, in turn, are measured by their
bounding boxes: each node in the tree contains the bounding boxes of
its sons. Thus, spatial queries like the ones above can be performed
in logarithmic time.
For more general information on RTrees please visit the
Links page.
Like the RTree, the OcTree is a spatial index based on a recursive
structure. It recursively partitions the 3D space into 8 subspaces
of equal size. Each inserted object is maintained corresponding to
the smallest subspace it completely fits in. The main difference to
the RTree: the subspaces are statically defined by the space
geometry and they do not overlap, while the RTree regions can grow
dynamically and are defined by the geometry of the objects they
contain.
The main difference between gtGroup and gtSpace: In order to organize
a logically closed environment of your geo-application, e.g. a closed
set of geological strata and faults which is not associated with
other data in your application, you would have one gtSpace to
contain all your objects in this environment. But "inside"
gtSpace, you may sub-organize your objects in as many gtGroups as
you like.
In the current version of GeoToolKit the programmer must be familiar
with the underlying OODBMS ObjectStore®. The overall structure, the
capabilities and the most important operations (e.g. database and
transaction handling) of this powerful system must be known to have
GeoToolKit store its data persistently.
In a future version, however, database and transaction handling
as well as persistent storage will be performed via gtSpace to
reduce or even eliminate the need for ObjectStore® knowledge.
A diploma candidate researches on a Spatial SQL interface for
gtSpace.
The intersection operation for two triangles is a good example:
Since two triangles can intersect each other only if their bounding
boxes share an intersection, an intersection test for the bounding
boxes is performed first, especially as this test is very fast.
Furthermore, if a bounding box can be computed for a spatial object,
it can be organized in an RTree to gain fast spatial access to
it.
Note: as well as the finite spatial objects, also gtLine and gtPlane
have a method returning their bounding boxes, although these boxes
are as virtually infinite as their corresponding analytical objects.
All further types of GeoToolKit as well as more detailed
descriptions of the discussed classes can be found in the
GT Library section.
Since GeoToolKit is a C++ class library, in the following we assume the reader to be familiar with object oriented C++ programming. This section intends to give a first insight into the creation of geo-applications using the facilities of GeoToolKit. More detailed information on code compilation and linkage with GeoToolKit (such as recommended compiler options, include paths, library choices etc.) is located in the GT Library section.
3.1 Requirements
First of all, let's have a look at the requirements for application development with the current version of GeoToolKit.
Required software:
- ObjectStore® 6
GeoToolKit's data management is based on the OODBMS ObjectStore®, version 6. Therefore the user at least must have access to the ObjectStore® header files and libraries needed by GeoToolKit. As well, an ObjectStore® server must be available.
- C++ compiler SUN CC 4.1 (or higher) or SGI MIPSPro C++
We guarantee ObjectStore® and GeoToolKit to compile with one of these two compilers (this limitation is due to ObjectStore, not GeoToolKit).
- Solaris / IRIX
Programs basing on GeoToolKit and ObjectStore® have been developed and tested in conjunction with the Unix derivatives Solaris (on SUN computers) and IRIX (on SGIs). The operating system, however, is not important by itself, since it only needs to be compatible to ObjectStore®.
Required hardware:
GeoToolKit has been tested on several machines of the SUN sparc
station family (including UltraSparc) and SGI computers.
A definite minimum of
installed memory is not known, since GeoToolKit has been tested on
computers with not less than 64 MB RAM. This is enough for
the ObjectStore® server, cache manager and a GeoToolKit application.
But certainly, the rule of thumb "the more the better"
concerning installed memory and processor speed, also applies for
GeoToolKit.
Required knowledge:
- Not to mention: Experiences in C++ programming
- Experiences in ObjectStore® usage
The current version of GeoToolKit cannot be used without knowledge on the ObjectStore® classes, if management of persistent data is intended. In a future version of GeoToolKit, however, the ObjectStore® functionality will be hidden from the user as far as possible.
3.2 Application development
In order to develop a geo-scientific application with GeoToolKit, at first an object model, that represents the data handled by the application, must be created. This task is described in section 3.2.1. When the object model is available, the application itself can be written. Section 3.2.2 gives information about this.
3.2.1 The object model
We recommend to carry out a particular sequence of
steps to create an object model.
After introducing these steps, we explain the following strategy by
means of a simple example.
- Work out the geometric part of your data and seperate it from the rest of the data. The geometric part mainly consists of the information that describes the size and position of an object in space.
- Look at the GeoToolKit types. Which are suitable to represent
the geometric data? Remember that you can easily create a new
spatial object that inherits from gtObj or its specializations. As
well, a new type can be created as aggregation of other spatial
objects.
Note:- Before making a decision, think about the geometric operations you want to perform on your objects.
- If you want to model two different real world objects that have different geometric features, for example geological strata and elevation lines, then create two different types. Never use a single class for more than one real-world type.
- After that you have created a representation for your geometric data, you can expand this type by member variables for the remaining non-geometric data. If you have created a new type for your geometric data, you only need to add these member variables to the rest of the new class. Else, if you intend to use an already defined class for your geometric data, you should create a new type as a specialization of this class. Then you can manage the remaining data by member variables of this new type.
A simple example
In the following an example reflecting a real world problem is
used to explain the introduced development strategy:
Given a set of geological strata. Now it is the task to compute a
set of elevation lines and to store them in a database along with
the according strata.
- Step 1:
- Which data must be handled? First of all, there are the strata. The geometric data of a stratum consists of its threedimensional structure and its position in space, while the non-geometric data, for example, could be the name of a landscape. Next, we want to store elevation lines. Elevation lines are open or closed curves. There is no non-geometric data to be stored: Because the altitude sketched by an elevation line is the same at every point on its course, there is no need to store extra altitude information.
- Step 2:
- Examining the GeoToolKit classes, we see that
gtTriangleNet is a type modeling a
3D surface and therefore is suitable to represent a geological
stratum. Being a curve, an elevation line can be represented by a
gtPolyLine.
Which geometric operations are needed to compute elevation lines from geological strata? Mathematically, an elevation line is the intersection of a threedimensional surface and a plane with a vertical normal vector. Looking at gtTriangleNet's repertoire of methods, we find an operation that intersects the triangle network with a gtPlane. The return type of this operation is gtObj (since more than one result type is possible), while, in most cases, the actually returned object will be a gtGroup containing gtSegments. These gtSegments, in turn, can be used to initialize a gtPolyLine representing the elevation line we wanted to compute. - Step 3:
- Since we want each stratum to be referred to by a name, we create
a new class myStratum as a specialization of
gtTriangleNet (i.e. we use gtTriangleNet as a public base class
for myStratum).
The name of the object is stored by a
member variable of myStratum.
Since there are no additional data to be stored along with the geometry of an elevation line, we do not need to create a new class to model this type. Therefore, we can use gtPolyLine as-is.
Because GeoToolKit comes as a regular shared library, its technical usage is not different from those of other class libraries known to the user. The application source only must include the header files of the types the application deals with.
First of all, the classes making up the object model should be written and tested. In our example, the class myStratum would have to be defined. This class could be completed by some useful methods like functions setting or returning the name of the stratum.
In order to store objects of the new type using ObjectStore®, myStratum must declare an additional function that informs ObjectStore® about the internal structure of the new class. Furthermore, an application that uses ObjectStore®'s facilities of persistent data management must provide a so-called "schema source file" containing the names of the classes to be stored persistently. The ObjectStore® documentation tells more about this.
The application itself starts with some statements initializing the ObjectStore® classes (remember, in the next version of GeoToolKit this will not be necessary any more). The built-in GeoToolKit types as well as user-defined types can be stored transiently as well as persistently. If persistent storage is needed, somewhere in the application a database must be opened. This database (or several databases) can then be used everywhere to store objects persistently.
The GT Library section offers a basic example of how to code a GeoToolKit application.