Problème de hauteur d'empilement maximale

Le problème suivant a-t-il été étudié auparavant? Si oui, quelles approches / algorithmes ont été développés pour le résoudre?

Problème ("Problème de hauteur d'empilage maximale")

Étant donné polygones, trouvez leur disposition stable et sans chevauchement qui maximise leur hauteur d'empilement sur un sol fixe sous l'influence de la gravité.$n$

Exemple

Trois polygones:

et trois de leurs infiniment d'arrangements stables, sans chevauchement, avec différentes hauteurs d'empilement:

Clarifications

• Tous les polygones ont une masse uniforme et une densité égale
• La friction est nulle
• La gravité agit sur chaque point vers le bas (c'est-à-dire que les vecteurs de force sont tous parallèles)
• Une configuration n'est pas considérée comme stable si elle repose sur un point d'équilibre instable (par exemple, le triangle vert sur les images ne peut s'équilibrer sur aucun de ses sommets, même si la masse à gauche et à droite du point d'équilibre est égale)
• Pour clarifier davantage le point ci-dessus: Un polygone est considéré comme instable ("basculement") à moins qu'il ne repose sur au moins un point strictement à gauche et au moins un point strictement à droite de son centre de gravité (cette définition simplifie considérablement la simulation et en particulier, l'intégration de la position, etc. n'est pas nécessaire pour évaluer si un arrangement est stable ou non.
• Le problème sous sa forme "physique" est un problème continu qui ne peut être résolu que dans la plupart des cas. Pour obtenir un problème discret qui peut être résolu de manière algorithmique, contraignez les sommets des polygones et leur placement dans l'arrangement à des réseaux appropriés.

Remarques

• Les approches par force brute de toute nature sont clairement irréalisables. Même avec des contraintes strictes sur le placement des polygones à l'intérieur du réseau (comme fournir un espace de réseau limité), la complexité explose simplement pour plus de quelques polygones.
• Les algorithmes itératifs doivent apporter des heuristiques très intelligentes car il est facile de construire des arrangements où la suppression de tout polygone unique rend la configuration instable et de tels arrangements sont inaccessibles par des algorithmes reposant sur la stabilité de chaque étape intermédiaire.
• Puisque le problème sent au moins NP- mais plus probablement EXPTIME-complet dans le nombre total de sommets, même l'heuristique serait d'un intérêt considérable. Une chose qui donne de l'espoir est le fait que la plupart des humains reconnaîtront que le troisième arrangement dans l'exemple est optimal.

Bien que je ne connaisse aucun algorithme spécifique pour ce problème, vous pouvez aborder cela de manière assez efficace en le décomposant en parties distinctes.

Je commencerais par trouver la rotation pour chaque forme individuelle qui fournit une hauteur maximale tout en conservant une orientation d'équilibrage valide (n'est pas sur un point comme avec le triangle). Si une forme a plusieurs hauteurs égales, j'irais avec la configuration qui donne la plus grande surface au-dessus d'elle. Une fois que vous avez cela, vous pouvez alors trouver la meilleure façon d'empiler chaque objet dans un manoir qui peut être équilibré.