Database Systems

Representation and Decomposition of Spatial Objects


Object approximations are used to reduce the number of exact geometry tests of polygons. Object decompositions are used to simplify such tests. Consider a point-in-polygon test. This test is rather time consuming for polygons with thousands of vertices. On the other hand, only a small local part of the object is actually relevant for the decision whether an object contains a point or not. This leads to the idea of object decompositions, where the objects are divided into a number of simple and local components, e.g. triangles, trapezoids, convex polygons, or even more complex components satisfying some quantitative constraint.


Using object decompositions, geometric tests are applied only to the object components, which is much more efficient than testing the whole polygon. To decide which components are relevant for a particular test, the components of one object are organized in a specific spatial structures. Important publications in this area are [Kri 91a], [KHS 91], [SK 91] und [SK 93].

An interesting research topic within the scope of this research area is the analysis and classification of spatial objects. First results are presented in [BKSB 95].

HOME Pages: DBS Institute LMU

Contact Institute: info@informatik.uni-muenchen.de
Contact WWW: wwwmaster@informatik.uni-muenchen.de