Topological reasoning is important for speeding up spatial queries, e.g. in GIS or in AI (robotics). While topological relations between spatial objects in the vector model (
2) are investigated thoroughly, we run into inconsistencies in the raster model (
2). But instead of reducing our requirements in case of reasoning in raster images we change from simple raster to a cellular decomposition of
2 — what we call a hyper-raster — which is also discrete, but preserves the topology of
2. The discrete representation reduces the computational effort against the vector model.
We will introduce a data structure for the hyper-raster, which represents regions, curves and points. Then we will present algorithms for digitization (vector/hyper-raster conversion). With the hyper-raster the intersection sets, as needed for the determination of a topological relation between two objects, are calculated simply by logical joins of binary images. Without extending our model we can also compute further refinements of the relationships.
Supported by the Deutsche Forschungsgemeinschaft, Sonderforschungsbereich 350.