topic Re: Optimal Bounding Rectangle for given set of points. in VBA Forum

Optimal Bounding Rectangle for given set of points.

mdhutchinson — Fri, 26 Jan 2007 14:56:10 GMT

I am working on developing an algorithm to determine a bounding rectangle (rotated away from WCS) for a given set of points. In my search, I stumbled on a couple web sites that look to have the logic I need (links below). It is the optimal bounding rectangle having the least area that encloses the set of points.

http://cgm.cs.mcgill.ca/~orm/rotcal.html
http://www.geometrictools.com/LibFoundation/Containment/Containment.html

I think this (below) is in ‘html’ pseudo code…?
Could someone convert this into English for me? … I would be most appreciative!
… my apologies… for some reason the indentation using code blocks 'code' and '/code' didn’t work for this.

[code]
ordered vertices P(0) through P(N-1)
define P(N) = P(0)
minimumArea = infinity
for (i = 1 i <= N i++)
(
U0 = P(i) - P(i-1)
U0 /= U0.Length()
U1 = (-U0.y,U0.x)
s0 = t0 = s1 = t1 = 0
for (j = 1 j < N j++)
(
D = P(j) - P(0)
test = Dot(U0,D)
if ( test < s0 ) s0 = test else if ( test > s1 ) s1 = test
test = Dot(U1,D)
if ( test < t0 ) t0 = test else if ( test > t1 ) t1 = test
)
area = (s1-s0)*(t1-t0)
if ( area < minimumArea )
minimumArea = area
)
[/code]

Re: Optimal Bounding Rectangle for given set of points.

arcticad — Fri, 26 Jan 2007 18:09:41 GMT

This will get the Box that surrounds an object.

item.GetBoundingBox minPoint, maxPoint

Re: Optimal Bounding Rectangle for given set of points.

mdhutchinson — Fri, 26 Jan 2007 18:19:39 GMT

yup... you are correct... thank for pointing that out. 8-).

The problem though is that the bounding box you get with the method you suggest is Axis-Aligned to the WCS... what I want is the smallest bounding box... !! The smallest bounding box could be aligned with WCS then again it may not be aligned with any coordinate system defined in the drawing... however, once the smallest box is found, it could be used to create one.

Re: Optimal Bounding Rectangle for given set of points.

arcticad — Fri, 26 Jan 2007 23:41:55 GMT

Yup I see the limitation. Darn why is all their code in c++?

Re: Optimal Bounding Rectangle for given set of points.

Anonymous — Sat, 27 Jan 2007 17:38:31 GMT

> Could someone convert this into English for me?

Your algorithm will not work with any arbitrary set of points. First
you must find the minimum area bounding convex polygon (search
for a "convex hull" algorithm). The minimum area rectangle which
contains your points will then have an edge on at least one of the
edges of the bounding polygon. For each edge of the bounding
polygon, find the extent of its vertices in the direction of the edge
and in a direction perpendicular to the edge. Multiply these extents
to get the area of the bounding rectangle aligned with the edge.
Use the smallest area. If you want the minimum area bounding
rectangle instead of just its area you will have to save the extents
as well as the area.