So berechnen Sie die Kontaktfläche eines rechteckigen Quaders mit den benachbarten Quader

Question

Ich versuche, rechteckige Quader mit unterschiedlicher Größe so nebeneinander zu positionieren, dass die Kontaktfläche zwischen diesen Quader maximiert ist.

In einer brutalen Art von Weg suche ich nach einer möglichen Position für jeden im Raum positioniert werden, die nicht mit anderen Quader kreuzt. Ich erkannte dies mit Java 3D BoundingBox Klasse, wo es möglich ist, zu überprüfen, ob eine bestimmte Box mit einer bestimmten Sammlung von anderen Boxen schneidet. Jetzt habe ich viele mögliche Standorte, von denen ich diejenige mit der höchsten Kontaktfläche zu anderen Boxen auswählen muss.

Mein Problem ist, dass ich nicht weiß, wie man diesen Bereich effizient berechnet. Ein kleines Beispiel ...

Box 1: unterer linker Punkt x = 0, y = 0, z = 0; oberer rechter Punkt x = 10, y = 10, z = 10

Feld 2: unterer linker Punkt x = 10, y = 0, z = 0; obere rechte Punkt x = 15, y = 5, z = 5

Box 3 die gleichen Abmessungen wie Box 1 und sollte mit einer maximalen Kontaktfläche

In diesem Beispiel sind alle Positionen, an denen eine Seite der Box angeordnet sein, 3 passt zu allen, außer der rechten Seite von Box 1 (wo Box 2 ist) sind optimale Lösungen.

Ich wäre sehr froh, wenn jemand eine Idee oder sogar eine Lösung hat. Ich bin auch mit kostenlosen Bibliotheken zufrieden, wenn sie nicht zu groß sind.

Danke!

Answer 1

Betrachten Sie jedes mögliche Paar berührender Gesichter der Reihe nach.

Platzieren Sie Box 2 überall in Kontakt mit Box 1. Sie suchen dann rekursiv. Für jede Position identifizieren Sie alle sich kreuzenden Quader und finden dann minimale Bewegung nach oben, unten, links und rechts, die eine Kreuzung mit einem dieser sich kreuzenden Quader verhindern würde. Dies legt vier neue Orte fest, von denen aus gesucht werden kann. Sie trainieren dann auch von diesen.

Um zu verdeutlichen, wenn Sie sich nach links bewegen, finden Sie die rechte linke Seite eines sich kreuzenden Quaders und bewegen sich so, dass sich die Fläche nicht mehr schneidet. Andere Quader werden sich wahrscheinlich noch schneiden, aber wir werden uns rekursiv von ihnen entfernen.

Wenn es keine Kreuzungen gibt, haben Sie einen Halteort und Sie notieren den Bereich und fahren mit der Suche fort.

Wenn ein Umzug es unmöglich macht, die Originalverpackung zu berühren, werden Sie nicht weiter entlang dieser Route erkunden.

Für jedes Gesicht können Sie feststellen, dass entweder keine Orte möglich sind oder es mindestens einen mit maximalem Kontakt für dieses Gesicht gibt.

Anschließend wiederholen Sie den Vorgang für die anderen fünf Flächen.