determine the minimum box of an object

[Anonymous]

Hi
Anyone knows if there is a way to determine the minimum box that contains an
entity (eg: pline or 3dsolid)?

I tried the lisp function (vla-getboundingbox) but it returns only the
corners of a box that is parallel to WCS, and this is not the minimum box
necessary to enclose completely an object.


Thanks all

[devitg]

Please chek the value given by

draw a cube from 0 0 0, 100 units

then use it
(setq cube (vlax-ename->vla-object (car (entsel))))

(vla-GetBoundingBox cube 'mini 'maxi)


It give it

(setq down-min-corner (vlax-safearray->list mini))
(setq up-max-corner (vlax-safearray->list maxi))
(0.0 0.0 0.0)
(100.0 100.0 100.0)

As you can see it give two 3dpoints

[Anonymous]

But if you rotate the box 45 degs it'll give you the wrong bounding box
(-70.7107 0.0 0.0) (70.7107 141.421 100.0) . I think he is trying to find
the actual size of the box regardless of it's rotation. Wish I could help
but I'm looking for that answer also.

[devitg]

As I'm not a future teller , I do not make any guess.

Maybe if you can show a dwg , and a clear state of the task to do, some one here could give full help.

[Anonymous]

I find that 'boundingbox' yields 2 points, from which
you can determine a rectangle. However, depending on
(what) object, and (how) it is shaped, (how) it is rotated,
the 'box' derived doesn't completely surround that object.
I also find that one could generate a 'max' X and 'min' X,
'max' Y and 'min' Y.. from gathering a point list.. then
derive a 'box' that completely surrounds it.

Bob

[Anonymous]

Hi devitg, thanks for your response

As Jason said, I need to obtain the "required smallest box" to contain a
3DSolid regardless of its position or orientation.

If you draw a box with Length=10 Width=5 and Height=2 placed on point 0,0 in
WCS, the (vla-getboundingbox) function returns these coordinates:

Lower Left corner (0.0 0.0 0.0)
Upper Right corner (10.0 5.0 2.0)

But if you make a 45° rotation of your box around the 0,0 point the
(vla-getboundingbox) function returns these other coordinates:

Lower Left corner (-3.5355 0.0 0.0)
Upper Right corner (7.0711 10.6066 2.0)

These coordinates are not the corners of the required smallest box, because
the dimensions of this box are independent from the original object
orientation. In this case AutoCAD told me that to contain my solid I need a
box that have at least these dimensions 10.6066 x 10.6066 x 2.0 and we all
know that this is not absolutely true!!

Anyone can help me to find a solution to this problem?


ha scritto nel messaggio news:5997111@discussion.autodesk.com...
As I'm not a future teller , I do not make any guess.

Maybe if you can show a dwg , and a clear state of the task to do, some one
here could give full help.

[Anonymous]

I've been watching this thread casually, and some questions arise in my mind.

Can the 3DSolid be any shape at all, or is it always something "clean" like the rectangular prism
[I'm avoiding the potential confusion of using your word "box" for it] that you use as an example?
If it can be something very irregular, it's hard for me to imagine AutoCAD being able to answer the
question with very much precision.

What if you take your 10x5x2 rectangular prism and *tilt it up* at one end, out of the XY plane? Is
the "required smallest box" always meant to have horizontal top and bottom faces, and vertical
sides, but be rotatable around the Z axis? In that case, such a box needed to hold that prism would
be larger than the 10x5x2 size of the prism. Or would you also want to tilt that containing box as
necessary to achieve the smallest volume?

About the only thing I can think of, aside from eye-balling an orientation, would be to have a
routine repeatedly rotate the 3DSolid by however small an increment you like, and after each
rotation, get its bounding box. Then compare the volumes of the bounding boxes to calculate the
smallest one. You would probably need to do that in at least two series of rotations around
different axes.

A slightly less intensive way, but one which might not really get the very smallest required box,
would be to:
::: get the current bounding box, and calculate its volume;
::: rotate the 3DSolid by some small amount;
::: get its bounding box again, and calculate its volume;
::: if the volume has gotten larger, you're going the wrong way -- rotate it the other way instead;
::: if the volume has gotten smaller, keep rotating farther in that direction until you get a
bounding box that comes out larger than the previous one;
::: that previous one is likely [but not guaranteed, depending on the complexity of the shape] to
be at least close to the smallest required box.

--
Kent Cooper


"Francesco Pais" wrote...
....
As Jason said, I need to obtain the "required smallest box" to contain a
3DSolid regardless of its position or orientation.

If you draw a box with Length=10 Width=5 and Height=2 placed on point 0,0 in
WCS, the (vla-getboundingbox) function returns these coordinates:

Lower Left corner (0.0 0.0 0.0)
Upper Right corner (10.0 5.0 2.0)

But if you make a 45° rotation of your box around the 0,0 point the
(vla-getboundingbox) function returns these other coordinates:

Lower Left corner (-3.5355 0.0 0.0)
Upper Right corner (7.0711 10.6066 2.0)

These coordinates are not the corners of the required smallest box, because
the dimensions of this box are independent from the original object
orientation. In this case AutoCAD told me that to contain my solid I need a
box that have at least these dimensions 10.6066 x 10.6066 x 2.0 and we all
know that this is not absolutely true!!

Anyone can help me to find a solution to this problem?
....

[Anonymous]

You can rotate the UCS to the object (using UCS > Object) and then get the
bounding box using trans but not all solids define a coordinate system (as
in a cylindir) so you would hit a road block there. The only way I could
figure out how to get it with some consistancy was using acisout and
parceling the acis sat data. This will still fail on some objects so I'm
curous also if someone has another way.

[Anonymous]

Have a look here:

http://www.theswamp.org/index.php?topic=24045.0

For the work in progress...






This will still fail on some objects so I'm
curous also if someone has another way.

[Anonymous]

A very interesting project.
I need to learn more ObjectARX.

[Anonymous]

i think the first step would be to find code that can return the "convex
hull" that contains any given solid..... those surfaces that make up the
convex hull can then be examined to find your smallest box......

"Francesco Pais" wrote in message
news:5998693@discussion.autodesk.com...
Hi devitg, thanks for your response

As Jason said, I need to obtain the "required smallest box" to contain a
3DSolid regardless of its position or orientation.

If you draw a box with Length=10 Width=5 and Height=2 placed on point 0,0 in
WCS, the (vla-getboundingbox) function returns these coordinates:

Lower Left corner (0.0 0.0 0.0)
Upper Right corner (10.0 5.0 2.0)

But if you make a 45° rotation of your box around the 0,0 point the
(vla-getboundingbox) function returns these other coordinates:

Lower Left corner (-3.5355 0.0 0.0)
Upper Right corner (7.0711 10.6066 2.0)

These coordinates are not the corners of the required smallest box, because
the dimensions of this box are independent from the original object
orientation. In this case AutoCAD told me that to contain my solid I need a
box that have at least these dimensions 10.6066 x 10.6066 x 2.0 and we all
know that this is not absolutely true!!

Anyone can help me to find a solution to this problem?


ha scritto nel messaggio news:5997111@discussion.autodesk.com...
As I'm not a future teller , I do not make any guess.

Maybe if you can show a dwg , and a clear state of the task to do, some one
here could give full help.

[Anonymous]

mataeux wrote:
> i think the first step would be to find code that can return the "convex
> hull" that contains any given solid..... those surfaces that make up the
> convex hull can then be examined to find your smallest box......
>

Seems likely, but maybe not in 3D. Read on:

Search Wikipedia for "Minimum bounding box algorithms"

A brief quote:

===================
"Two dimensions

For the convex polygon, a linear time algorithm for the minimum-area
enclosing rectangle is known. It is based on the observation that a side
of a minimum-area enclosing box must be collinear with a side of the
convex polygon.[1] It is possible to enumerate of the boxes of this kind
in linear time with the approach called rotating calipers by Godfried
Toussaint in 1983 [2] The same approach is applicable for finding the
minimum-perimeter enclosing rectangle. [2]

Three dimensions

In 1985, Joseph O'Rourke published an cubic-time algorithm to find the
minimum-volume enclosing box of a 3-dimensional point set.[3] O'Rourke's
approach uses a 3-dimensional rotating calipers technique. This
algorithm has not been improved on as of August 2008, although heuristic
methods for tackling the same problem have been developed.

Preparatory theorems in O'Rourke's work were proved to the effect that:

* There must exist two neighbouring faces of smallest-volume
enclosing box which both contain an edge of the convex hull of the point
set. This criterion is satisfied by a single convex hull edge collinear
with an edge of the box, or by two distinct hull edges lying in adjacent
box faces.
* The other four faces need only contain a point of the convex
hull. Again, the points which they contain need not be distinct: a
single hull point lying in the corner of the box already satisfies three
of these four criteria.

It follows in the most general case where no convex hull vertices lie in
edges of the minimal enclosing box, that at least 8 convex hull points
must lie within faces of the box: two endpoints of each of the two
edges, and four more points, one for each of the remaining four box
faces. Conversely, if the convex hull consists of 7 or fewer vertices,
at least one of them must lie within an edge of the hull's minimal
enclosing box.

The minimal enclosing box of the regular tetrahedron is a cube, with the
tetrahedron's vertices lying at (0,0,0), (0,1,1), (1,0,1) and (0,1,1)."

==================

There didn't seem to be any AutoLISP code for this on Wikipedia, alas
(what *are* they thinking?), but at least the algorithm does exist.
O'Rourke is a professor of computer science at Smith. He has published
two books:

"Geometric Folding Algorithms: Linkages, Origami, and Polyhedra", with
Erik D. Demaine (2007) ISBN 978-0-521-85757-4

"Computational Geometry in C" (1998) ISBN 0521649765


Give him a call -- I don't think this is going to be a quick LISP hack...

[Anonymous]

Thanks Luis

I gave a look to the posts that you have suggested but I haven't found any
"sure" solution for my problem.

I am developing an application in AutoCAD for a customer and he need a
response to this simple question: what are the minimal dimensions of the a
box necessary to entirely enclose a generic 3dsolid?

Give an answer to this question..this is my issue!!

Anyone of you has never tackled this problem?

Thanks in advance

"Luis Esquivel" ha scritto nel messaggio
news:5998967@discussion.autodesk.com...
Have a look here:

http://www.theswamp.org/index.php?topic=24045.0

For the work in progress...



This will still fail on some objects so I'm
curous also if someone has another way.

[Anonymous]

sets of points are easy to study but i just hope the Original Poster doesn't
need to enclose curved surfaces!


"Bill Gilliss" wrote in message
news:5999248@discussion.autodesk.com...
mataeux wrote:
> i think the first step would be to find code that can return the "convex
> hull" that contains any given solid..... those surfaces that make up the
> convex hull can then be examined to find your smallest box......
>

Seems likely, but maybe not in 3D. Read on:

Search Wikipedia for "Minimum bounding box algorithms"

A brief quote:

===================
"Two dimensions

For the convex polygon, a linear time algorithm for the minimum-area
enclosing rectangle is known. It is based on the observation that a side
of a minimum-area enclosing box must be collinear with a side of the
convex polygon.[1] It is possible to enumerate of the boxes of this kind
in linear time with the approach called rotating calipers by Godfried
Toussaint in 1983 [2] The same approach is applicable for finding the
minimum-perimeter enclosing rectangle. [2]

Three dimensions

In 1985, Joseph O'Rourke published an cubic-time algorithm to find the
minimum-volume enclosing box of a 3-dimensional point set.[3] O'Rourke's
approach uses a 3-dimensional rotating calipers technique. This
algorithm has not been improved on as of August 2008, although heuristic
methods for tackling the same problem have been developed.

Preparatory theorems in O'Rourke's work were proved to the effect that:

* There must exist two neighbouring faces of smallest-volume
enclosing box which both contain an edge of the convex hull of the point
set. This criterion is satisfied by a single convex hull edge collinear
with an edge of the box, or by two distinct hull edges lying in adjacent
box faces.
* The other four faces need only contain a point of the convex
hull. Again, the points which they contain need not be distinct: a
single hull point lying in the corner of the box already satisfies three
of these four criteria.

It follows in the most general case where no convex hull vertices lie in
edges of the minimal enclosing box, that at least 8 convex hull points
must lie within faces of the box: two endpoints of each of the two
edges, and four more points, one for each of the remaining four box
faces. Conversely, if the convex hull consists of 7 or fewer vertices,
at least one of them must lie within an edge of the hull's minimal
enclosing box.

The minimal enclosing box of the regular tetrahedron is a cube, with the
tetrahedron's vertices lying at (0,0,0), (0,1,1), (1,0,1) and (0,1,1)."

==================

There didn't seem to be any AutoLISP code for this on Wikipedia, alas
(what *are* they thinking?), but at least the algorithm does exist.
O'Rourke is a professor of computer science at Smith. He has published
two books:

"Geometric Folding Algorithms: Linkages, Origami, and Polyhedra", with
Erik D. Demaine (2007) ISBN 978-0-521-85757-4

"Computational Geometry in C" (1998) ISBN 0521649765


Give him a call -- I don't think this is going to be a quick LISP hack...