155:
followed by a linear-time computation. A three-dimensional rotating calipers algorithm can find the minimum-volume arbitrarily-oriented bounding box of a three-dimensional point set in cubic time. Matlab implementations of the latter as well as the optimal compromise between accuracy and CPU time are
133:
and its applications when it is required to find intersections in the set of objects, the initial check is the intersections between their MBBs. Since it is usually a much less expensive operation than the check of the actual intersection (because it only requires comparisons of coordinates), it
20:
150:
method can be used to find the minimum-area or minimum-perimeter bounding box of a two-dimensional convex polygon in linear time, and of a three-dimensional point set in the time it takes to construct its
78:
in higher dimensions) within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".
114:) for a given point set is its minimum bounding box subject to the constraint that the edges of the box are parallel to the (Cartesian) coordinate axes. It is the
129:
Axis-aligned minimal bounding boxes are used as an approximate location of an object in question and as a very simple descriptor of its shape. For example, in
142:
The arbitrarily oriented minimum bounding box is the minimum bounding box, calculated subject to no constraints as to the orientation of the result.
168:, it can be useful to store a bounding box relative to these axes, which requires no transformation as the object's own transformation changes.
122:
intervals each of which is defined by the minimal and maximal value of the corresponding coordinate for the points in
143:
304:
207:
94:
177:
236:
165:
130:
188:
when it is placed over a page, a canvas, a screen or other similar bidimensional background.
63:
258:
8:
81:
The minimum bounding box of a point set is the same as the minimum bounding box of its
299:
147:
115:
212:
202:
197:
59:
293:
185:
23:
A sphere enclosed by its axis-aligned minimum bounding box (in 3 dimensions)
107:
272:
184:
is merely the coordinates of the rectangular border that fully encloses a
273:"Matlab implementation of several minimum-volume bounding box algorithms"
152:
82:
75:
86:
55:
28:
134:
allows quickly excluding checks of the pairs that are far apart.
277:
71:
19:
271:
Chang, Chia-Tche; Gorissen, Bastien; Melchior, Samuel (2018).
137:
253:
Joseph O'Rourke (1985), "Finding minimal enclosing boxes",
67:
237:"Solving geometric problems with the rotating calipers"
159:
270:
101:
252:
291:
234:
16:Smallest box which encloses some set of points
92:In the two-dimensional case it is called the
171:
138:Arbitrarily oriented minimum bounding box
230:
228:
164:In the case where an object has its own
18:
292:
225:
160:Object-oriented minimum bounding box
13:
14:
316:
102:Axis-aligned minimum bounding box
144:Minimum bounding box algorithms
264:
246:
1:
218:
242:. Proc. MELECON '83, Athens.
7:
191:
85:, a fact which may be used
10:
321:
208:Minimum bounding rectangle
95:minimum bounding rectangle
235:Toussaint, G. T. (1983).
110:minimum bounding box (or
89:to speed up computation.
178:digital image processing
172:Digital image processing
166:local coordinate system
131:computational geometry
45:smallest enclosing box
24:
41:minimum enclosing box
37:smallest bounding box
22:
305:Geometric algorithms
259:Springer Netherlands
255:Parallel Programming
33:minimum bounding box
39:(also known as the
62:with the smallest
47:) for a point set
25:
148:rotating calipers
116:Cartesian product
312:
284:
282:
268:
262:
261:
250:
244:
243:
241:
232:
213:Darboux integral
54:
50:
320:
319:
315:
314:
313:
311:
310:
309:
290:
289:
288:
287:
269:
265:
251:
247:
239:
233:
226:
221:
203:Bounding volume
198:Bounding sphere
194:
174:
162:
140:
104:
52:
48:
17:
12:
11:
5:
318:
308:
307:
302:
286:
285:
263:
245:
223:
222:
220:
217:
216:
215:
210:
205:
200:
193:
190:
173:
170:
161:
158:
139:
136:
103:
100:
15:
9:
6:
4:
3:
2:
317:
306:
303:
301:
298:
297:
295:
280:
279:
274:
267:
260:
256:
249:
238:
231:
229:
224:
214:
211:
209:
206:
204:
201:
199:
196:
195:
189:
187:
186:digital image
183:
179:
169:
167:
157:
154:
149:
146:based on the
145:
135:
132:
127:
125:
121:
117:
113:
109:
99:
97:
96:
90:
88:
87:heuristically
84:
79:
77:
73:
69:
65:
61:
57:
46:
42:
38:
34:
30:
21:
276:
266:
254:
248:
182:bounding box
181:
175:
163:
141:
128:
123:
119:
111:
108:axis-aligned
105:
93:
91:
80:
44:
40:
36:
32:
26:
156:available.
153:convex hull
83:convex hull
76:hypervolume
294:Categories
219:References
56:dimensions
300:Geometry
192:See also
29:geometry
64:measure
58:is the
278:GitHub
180:, the
72:volume
31:, the
240:(PDF)
74:, or
112:AABB
106:The
68:area
176:In
118:of
60:box
51:in
43:or
35:or
27:In
296::
275:.
257:,
227:^
126:.
98:.
70:,
283:.
281:.
124:S
120:N
66:(
53:N
49:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
