Scatola rettangolare più piccola che circonda un poliedro

Question

Sto cercando un algoritmo che trovi la casella più piccola che racchiude un poliedro.

La mia idea è la seguente: trovare il lato più grande e spostare il solido in modo che il lato si allinea con l'asse x. Trova il lato più grande che incontra questo lato e allinea il più vicino possibile all'asse z, lasciando l'altro lato su x. Quindi, calcola le maggiori differenze in x, yez. Usa quelle dimensioni per creare la forma circostante e quindi sposta il riquadro nella posizione originale dell'oggetto.

Esiste una strategia più efficiente per questo? La mia idea trascura alcuni casi d'angolo?

Modifica: per ora assumere l'oggetto da limitare è convesso. Tuttavia, una risposta per il caso generale sarebbe anche il benvenuto.

Answer 1

Il problema di trovare scatole minime (volume) per poliedri convessi è stato studiato da O'Rourke, che propone un O(n^3) algoritmo:

J. O-Rourke. Trovare scatole di chiusura minime. International Journal of Computer & Scienze dell'informazione, 1985, 14 (3), p.183.

algoritmo di O'Rourke trova la scatola che contiene minimo per una serie di punti in R^3 - ma questo è chiaramente equivalente a trovare la scatola che contiene il poliedro formato come convesso del sottostante point-set.

Contrariamente a quanto ci si potrebbe aspettare (e l'approccio che hai descritto, se ti ho capito correttamente), la casella minima non è necessariamente orientata in modo tale che una faccia del poliedro sia complanare con una faccia della scatola ! Nota l'animazione mostrata here per un semplice tetraedro.

Se sei felice con l'idea di trovare una semplice scatola che contiene che è relativamente piccolo, piuttosto che la più piccola scatola racchiude, ci possono essere altre euristiche (più veloce) che possono essere applicati ...