TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: mailmaverick on October 13, 2014, 06:10:16 AM

Title: Minimum Bounding Box (Polygon)
Post by: mailmaverick on October 13, 2014, 06:10:16 AM

I have seen lot of LISPs for making bounding box (Rectangle) of given objects.

How to make bounding box with N sided polygon which is minimum fit bounding box ?

Title: Re: Minimum Bounding Box (Polygon)
Post by: Kerry on October 13, 2014, 06:31:16 AM

Very complex algorithm.
Will require lots of trial and optimise calculations.

The Polygon will be subscribed/inscribed in a circle, but not necessarily in a circle that encompases the objects you select.

Title: Re: Minimum Bounding Box (Polygon)
Post by: ribarm on October 13, 2014, 07:59:35 AM

Like Kerry said, it would be more complex than just smallest circumscribed circle... But if your sel. set is only from LWPOLYLINES, or if you previously converted 2D entities to corresponding LWPOLYLINES (LM has function for this...), the smallest circumscribed circle can be found...

Look here :
http://www.cadtutor.net/forum/showthread.php?63541-Smallest-Circumscribing-Circle/page5&p=#49

HTH, M.R.

Title: Re: Minimum Bounding Box (Polygon)
Post by: mailmaverick on October 14, 2014, 06:42:05 AM

Thanks.

Title: Re: Minimum Bounding Box (Polygon)
Post by: MickD on October 14, 2014, 04:16:41 PM

A bit of a quick hack but you could loop through the polygon edges, using the current edge as a direction vector and transform the polygon to say world X axis and grab the bbox and store it before transforming the object back?
Loop through stored bbox and calc distance between min/max points for comparison.

Title: Re: Minimum Bounding Box (Polygon)
Post by: Kerry on October 14, 2014, 06:00:45 PM

I imagined something like that Mick,

but some conditionals may ruin the game.

What determines the rotation of the polygon ?

Must admit I didn't consider it much more than that.

Title: Re: Minimum Bounding Box (Polygon)
Post by: Lee Mac on October 14, 2014, 06:09:43 PM

A brute-force approach might be to start with an n-sided polygon (regular, I assume) circumscribed around the minimum enclosing circle, and then proceed to incrementally rotate the polygon and decrease the radius until the polygon intersects the enclosed objects for each rotation step.

Of course, given the symmetry of the polygon, you would only need to perform a rotation through pi/n radians.

Title: Re: Minimum Bounding Box (Polygon)
Post by: Kerry on October 14, 2014, 06:19:28 PM

It would need to be a rotation, reduction/increase of size and a relocation of the centerpoint cycle.

Imagine fitting a triangle over a 'square' shape ( without knowing the shape is square.)

If the polygon isn't 'regular' the magnitude of complexity changes a bit :)

Title: Re: Minimum Bounding Box (Polygon)
Post by: MickD on October 14, 2014, 09:09:20 PM

Quote from: Kerry on October 14, 2014, 06:00:45 PM

I imagined something like that Mick,

but some conditionals may ruin the game.

What determines the rotation of the polygon ?

Must admit I didn't consider it much more than that.

Looping through the edge list gives you a new vector that you use as the rotation (i.e. the current edge may be pointing north east say which gives you the angle to X to rotate the whole polygon by).
I'm not sure about edge cases where a half rotation say might produce a smaller result. I guess it depends on how accurate you need to be.