The Approximation of Two-Dimensional Spatial Objects by Two Bounding Rectangles
Jörg Roth · Spatial Cognition and Computation · 2011
Minimal bounding rectangles are a simple and efficient tool for approximating geometries, particularly for accelerating spatial queries. If a spatial object fills a rectangular shape to a certain extent, then the minimal bounding rectangle is a reasonable approximation. Unfortunately some geo objects, such as streets or rivers, have a small area but large bounding rectangles. In this paper we suggest an approximation with two bounding rectangles instead of a single one. Since the corresponding shape provides a better approximation, we get a greater average benefit. We present an efficient algorithm that computes the two rectangles with the theoretically smallest combined area that encloses a given geometry in O(n · log n) steps. Following a detailed description of the algorithm, we present an analysis with approximately 4 million real geo objects.