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