minimum bounding box for a convex polygon

[Paul Henning]

It should be noted that Gottschalk's algorithm produces an _approximate_
minimum bounding box.   Unfortunately, it will bound a polygon like
[(1,0),(0,1),(-1,0),(0,-1)] by an axis-aligned box, which is not a great
bound.   All that being said, I haven't found a better approach for 3-D.
O'Rourke has an algorithm in:

@Article{orourke,
  author =       {O'Rourke, Joseph},
  title =        {Finding Minimal Enclosing Boxes},
  journal =      {International Journal of Computer and Information Sciences},
  year =         1985,
  volume =       14,
  number =       3,
  pages =        {183--199},
}

for true minimal boxes, but it is a bit tricky to implement.

Paul


"Dickinson, John" wrote:

> If you want an axis-orientated bounding box that will work and is very easy
> to do.  If not then search for orientated bounding box algorithms on the
> net.  S.  Gottschalk implemented a 3D orientated bounding box algorithm see
> the following paper. and his site: http://www.cs.unc.edu/~geom/OBB/OBBT.html
>
> OBB-Tree: A Hierarchical Structure for Rapid Interference Detection , S.
> Gottschalk, M. C. Lin and D. Manocha (27 pages PostScript, ) 493K, Technical
> report TR96-013, Department of Computer Science, University of N. Carolina,
> Chapel Hill. Proc. of ACM Siggraph'96.
>
> John


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.