Minimum bounding rectangle

From Wikipedia, the free encyclopedia

A minimum bounding rectangle (MBR), also known as or bounding box, is an expression of the maximum extents of a 2-dimensional object (e.g. point, line, polygon) within its 2-D (x,y) coordinate system, in other words min(x), max(x), min(y), max(y). MBRs are frequently used as an indication of the general position of a geographic feature or dataset, for either display, first-approximation spatial query, or spatial indexing purposes. The minimum bounding rectangle may be considered a special (simple) case of a bounding volume, as described for n-dimensional objects, applied in a geographic (geospatial) context.

1 Introduction
2 Special cases
3 Applications
4 MBRs as spatial metadata
5 Syntax examples
6 Further reading
7 References
8 See also
9 External links

[edit] Introduction

The minimum bounding rectangle is an extremely useful concept in spatial information handling. According to Linda Hill in "Georeferencing"^[1], MBRs are:

relatively easy to obtain and they are better (more expressive) than points (i.e., centre location)
efficient to store and process for information retrieval (systems that are not capable of spatial matching operations based on polygons can process bounding-box data using ordinary mathematical operations).

On the negative side, they can overestimate the actual extent occupied by a particular spatial object (sometimes unacceptably so), and can present problems with representation of objects that extend past the boundaries of the coordinate system in use (in a geospatial context, this typically includes objects that cross a pole or the International Date Line, when represented in conventional latitude and longitude notation).

In the geographic coordinate system where x and y represent degrees of longitude and latitude, respectively, the MBR can be defined as the northernmost, southernmost, westernmost, and easternmost limits of the object, typically a geographic feature or dataset, expressed in the relevant units of choice (e.g. decimal degrees, or degrees/minutes/seconds). Note, these coordinates typically do not have any implied order, therefore in most systems that require them, either an order is specified, or they are supplied as parameter name/value pairs e.g. "north_bounding_coordinate, 42.0", etc. In some environments such as Geography Markup Language (GML) and the geographic information systems of ESRI, these are combined into a set of coordinate pairs (xmin,ymin and xmax,ymax) that define opposite corners of the MBR.

[edit] Special cases

[edit] Date line problem

A potential problem for MBRs is how to express the extent of an object that crosses the International Date Line or anti-prime meridian, at 180° longitude. If an MBR is permitted to cross the Date Line, then frequently the easternmost limit will be numerically lower in value than the westernmost limit, which may have to be handled as a special case by relevant software. Alternatively, if bounding boxes are not permitted to cross the date line in a particular software application, a workaround may be to permit two (or multiple) bounding boxes to be associated with a particular data extent, one on each side of the Date Line.

[edit] Polar data

Polar datasets (example: a guadrangular satellite image that includes the north or south pole within its field of view) are not well represented by MBRs expressed in conventional geographic coordinates. An alternative is to define such coverages using a polar projection (e.g. see discussion by Swick & Knowles, cited below), however then for any spatial search the search area must be expressed on a similar basis. Such MBRs are then difficult to integrate with those drawn on the more "standard" latitude-longitude system.

[edit] Global coverages

By convention, complete (global) coverages are expressed as western boundary = -180, eastern boundary = +180, northern boundary = +90, southern boundary = -90 (in signed decimal degrees), although of course these limits are notional.

[edit] Applications

The purpose of a MBR is usually to provide a proxy for a more complex spatial object, that can then be easily processed for simple spatial queries based on overlapping ranges in both the x and y dimensions. This produces a coarse "spatial filter" that can either be used alone, recognising its limitations, or as a pre-filter stage to a more computationally expensive "overlapping polygon" test^[2]. Applying the (computationally trivial) "overlapping rectangles" test as an initial step can frequently eliminate many spatial objects that cannot satisfy the designated spatial query conditions before passing to the more precise, but slow, second stage.

The degree to which an "overlapping rectangles" query based on MBRs will be satisfactory (in other words, produce a low number of "false positive" hits) will depend on the extent to which individual spatial objects occupy (fill) their associated MBR. If the MBR is full or nearly so (for example, a mapsheet aligned with axes of latitude and longitude will normally entirely fill its associated MBR in the same coordinate space), then the "overlapping rectangles" test will be entirely reliable for that and similar spatial objects. On the other hand, if the MBR describes a dataset consisting of a diagonal line, or a small number of disjunct points (patchy data), then most of the MBR will be empty and an "overlapping rectangles" test will produce a high number of false positives. One system that attempts to deal with this problem, particularly for patchy data, is c-squares.

MBRs are also an essential prerequisite for the R-tree method of spatial indexing.

[edit] MBRs as spatial metadata

Owing to their simplicity of expression and ease of use for searching, MBRs (frequently as "bounding box" or "bounding coordinates") are also commonly included in relevant standards for geospatial metadata, i.e. metadata that describes spatial (geographic) objects; examples include DCMI Box as an extension to the Dublin Core metadata scheme, "Bounding Coordinates" in the (U.S.) FGDC metadata standard, and "Geographic Bounding Box" in the (2003-current) ISO 19115 Metadata Standard for geographic information (ISO/TC 211). It is also (as "boundingBox") an element in Geography Markup Language (GML), that is utilised by a range of Web Service specifications from the Open Geospatial Consortium (OGC). In the ISO 19107 Spatial Schema (ISO/TC 211), MBR appears as the datatype GM_Envelope that is returned by the envelope() operation on the root class GM_Object.

[edit] Syntax examples

The following example in Geography Markup Language (GML) has been provided courtesy of Dr. Simon Cox:

<gml:boundedBy>

   <gml:Envelope srsName="urn:x-ogc:def:CRS:EPSG:27354"> 
       <gml:lowerCorner>-73.933217 40.78587</gml:lowerCorner>
       <gml:upperCorner>-73.768722 40.914404</gml:upperCorner>
   </gml:Envelope>

</gml:boundedBy>

The next example is provided from the ISO 19115 standard for geospatial metadata:

<EX_GeographicBoundingBox>

   <westBoundLongitude>...</westBoundLongitude>
   <eastBoundLongitude>...</eastBoundLongitude>
   <southBoundLatitude>...</southBoundLatitude>
   <northBoundLatitude>...</northBoundLatitude>

</EX_GeographicBoundingBox>

[edit] Further reading

Web-accessible articles that deal further with the concept of the MBR include "Unlocking the Mysteries of the Bounding Box" ^[3] by Douglas R. Caldwell, and "Geographic Database Search Interfaces and the Equatorial Cylindrical Equidistant Projection" ^[4] by Ross S. Swick and Kenneth W. Knowles. The section on "searching" on the Geospatial Methods site is also well worth investigating. See also documentation for specific spatially-enabled databases, e.g. ^[5], ^[6].