Minimum bounding rectangle: Difference between revisions

Revision as of 14:56, 10 December 2012

Latest revision as of 22:41, 30 May 2025

(20 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Smallest rectangle which encloses some planar set of points}}

[[File:Minimum bounding rectangle.svg|thumb|A series of geometric shapes enclosed by its minimum bounding rectangle]]

TheIn [[computational geometry]], the '''minimum bounding rectangle''' ('''MBR'''), also known as '''bounding box''' ('''BBOX''') or '''envelope''', is an expression of the maximum extents of a 2two-dimensional object (e.g. [[Point (geometry)|point]], [[Line (geometry)|line]], [[polygon]]) or set of objects within its 2-D ({{mvar|x, -y)}} [[Cartesian coordinate system|coordinate system]],; in other words {{math|min(''x'')}}, {{math|max(''x'')}}, {{math|min(''y'')}}, {{math|max(''y'')}}. The MBR is a 2-dimensional case of the [[minimum bounding box]].

MBRs are frequently used as an indication of the general position of a [[geography|geographic]] feature or dataset, for either display, first-approximation spatial query, or [[Spatial database|spatial indexing]] purposes.

The degree to which an "overlapping [[rectangle]]s" 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]].

The degree to which an "overlapping [[rectangle]]s" 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]].

[[File:Detected-with-YOLO--Schreibtisch-mit-Objekten.jpg|thumb|Minimum bounding rectangles used in [[computer vision]] ]]

MBRs are also an essential prerequisite for the [[R-tree]] method of [[spatial index]]ing.

==MBRs asAs 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 [http://dublincore.org/documents/dcmi-box/index.shtml DCMI Box] as an extension to the [[Dublin Core]] metadata scheme, "Bounding Coordinates" in the [http://www.fgdc.gov/standards/projects/FGDC-standards-projects/metadata/base-metadata/v2_0698.pdf (U.S.) FGDC metadata standard], and "Geographic Bounding Box" in the (2003-current2003–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.

Web-accessible articles that deal further with the concept of the MBR include "Unlocking the Mysteries of the Bounding Box" <ref>[http://purl.oclc.org/coordinates/a2.htm Douglas R. Caldwell: Unlocking the Mysteries of the Bounding Box]</ref> by Douglas R. Caldwell, and "Geographic Database Search Interfaces and the Equatorial Cylindrical Equidistant Projection" <ref>[http://chukchi.colorado.edu/PAPER/ Ross S. Swick and Kenneth W. Knowles: Geographic Database Search Interfaces and the Equatorial Cylindrical Equidistant Projection]</ref> by Ross S. Swick and Kenneth W. Knowles. The section on "searching" on the [http://geospatialmethods.org/searching.html Geospatial Methods] site is also well worth investigating. See also documentation for specific spatially enabled databases, e.g.,.<ref>[http://publib.boulder.ibm.com/infocenter/db2luw/v9/index.jsp?topic=/com.ibm.db2.udb.spatial.doc/db2sb16.html IBM DB2 documentation]</ref><ref>ESRI, 1993. Understanding GIS: The Arc/Info method. John Wiley and Sons</ref>

==See also==

*[[Conjugate diameters#Of ellipse|Bounding parallelogram]]

*[[Minimum bounding box]]

*[[C-squares]]

*[[Darboux integral]]

*[[Elongatedness]]

*[[Geographic information system]]

*[[Geospatial metadata]]

*[[Largest empty rectangle]], also known as maximal empty rectangle

*[[Minimum bounding box]]

*[[R-tree]]

*[[Shapefile]]

*[[Spatial index]]

*[[ElongatednessConvex hull]]

==References==

Line 30 ⟶ 33:

*[http://geospatialmethods.org/ Geospatial Methods website]

[[Category:Geography]]

[[Category:Cartography]]

[[Category:Geometry]]

[[Category:Geometric algorithms]]

[[Category:Polygons]]

[[de:Minimal umgebendes Rechteck]]

[[fr:Rectangle à limite minimum]]

[[zh:最小外接矩形]]