Regular Decomposition

Introduction

Applying the regular decomposition methods, the data space is divided in a regular or semi-regular way. The subdivision of space should be specified and afterwards the object will be addressed in the new structure. The geometry of the object is hence distributed between several adjacent cells (or regions). The objects descriptions are generally kept intact, while the spatial index cells store references to the database locations of the complete objects that intersect them. The data associated with each cell will normally be stored in one or more records, the address of which is given in terms of the coordinates of the lower corner of the cell.

For the regular decomposition of space, cells mainly have three different shapes:

Triangle: convenient for representing approximately spherical surfaces. Triangles have the advantage that they can be regularly subdivided any number of times.
Rectangle: most suitable because its edges can be aligned with the axis of a coordinate system. Rectangles simplify inclusion analysis within rectangular search window.
Hexagon: useful for mapping statistical properties since their neighboring centers are equidistant in all six directions.