Author Topic: Minimum Bounding Box (Polygon)  (Read 3495 times)

0 Members and 1 Guest are viewing this topic.

mailmaverick

  • Bull Frog
  • Posts: 494
Minimum Bounding Box (Polygon)
« 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 ?

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Minimum Bounding Box (Polygon)
« Reply #1 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.

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

ribarm

  • Gator
  • Posts: 3225
  • Marko Ribar, architect
Re: Minimum Bounding Box (Polygon)
« Reply #2 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.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

mailmaverick

  • Bull Frog
  • Posts: 494
Re: Minimum Bounding Box (Polygon)
« Reply #3 on: October 14, 2014, 06:42:05 AM »
Thanks.


MickD

  • King Gator
  • Posts: 3619
  • (x-in)->[process]->(y-out) ... simples!
Re: Minimum Bounding Box (Polygon)
« Reply #4 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.
"Short cuts make long delays,' argued Pippin.”
J.R.R. Tolkien

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Minimum Bounding Box (Polygon)
« Reply #5 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.

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: Minimum Bounding Box (Polygon)
« Reply #6 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.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Minimum Bounding Box (Polygon)
« Reply #7 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 :)

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

MickD

  • King Gator
  • Posts: 3619
  • (x-in)->[process]->(y-out) ... simples!
Re: Minimum Bounding Box (Polygon)
« Reply #8 on: October 14, 2014, 09:09:20 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.
"Short cuts make long delays,' argued Pippin.”
J.R.R. Tolkien