Comment emballer des polygones à l'intérieur d'un autre polygone?

J'ai commandé quelques feuilles de cuir à partir desquelles j'aimerais construire des balles de jonglage en cousant des bords ensemble. J'utilise les solides platoniciens pour la forme des boules.

Je peux numériser les feuilles de cuir et générer un polygone qui se rapproche de la forme de la feuille de cuir (comme vous le savez, c'est de la peau d'animal et il ne vient pas en rectangles).

Alors maintenant, je voudrais maximiser la taille de ma balle de jonglage.

Dans mon exemple, les polygones sont réguliers, mais je cherche une solution avec des polygones simples.

Quel est le plus grand facteur d'échelle que je peux appliquer à mes polygones pour qu'ils tiennent tous à l'intérieur de la feuille?

J'essaie de minimiser les déchets en utilisant autant de matière que possible.

Évidemment, couper le filet de polyèdre en polygone individuel augmentera l'espace de combinaison possible, mais diminuera également la qualité de la géométrie finale, car il y a plus de couture impliquée et d'erreurs accumulées. Mais cette question ne concerne pas l'énumération des différentes manières de déplier un polyèdre. Ils peuvent être considérés indépendamment. Les polygones sont donc de simples polygones.

Officiellement:

Contribution:

• $P$ : un simple polygone (la cible)
• $S$ : l'ensemble des polygones que je veux placer
• n $G$ : un graphique de polygones simples - chaque nœud représente un polygone simple en , et il y a un bord de bord entre chaque paire de polygones qui partagent un bord commun $n$$S$
• $\alpha >= 0, \beta >= 0$ (utilisation du matériel et connectivité)

Production:

• un facteur d'échelle$f$
• $H$ , un sous-graphe de$G$
• V ( G $Loc$ : un emplacement et un angle pour chaque polygone en$V(G)$
• une mesure de la qualité de la solution:m = α . f + β . | E ( H ) $m$$m = \alpha.f + \beta. {|E(H)|\over|E(G)|}$

Maximisez sous ces conditions:$m$

• $| V(H) | = |V(G)|$ (1)
• $| E(H) | <= |E(G)|$ (2)
• pour chaque polygone dans , mis à l'échelle par un facteur à l'emplacement est à l'intérieur de (3) S S i f L o c ( S i ) $S_i$$S$$S_i$$f$$Loc(S_i)$$P$
• les polygones en ne se chevauchent pas (4)$V(H)$

(V (G) sont les sommets du graphique et S est l'ensemble des polygones, mais ils décrivent le même ensemble d'objets. Peut-être existe-t-il une manière plus compacte de procéder.)

Explication des conditions:

• (1) Je veux que tous les polygones soient dans la disposition finale
• (2) Certaines connexions peuvent être rompues si nécessaire
• (3) (4) la balle est en cuir

Voici le polygone cible

Voici l'ensemble des polygones que je veux emballer:

Cela appartient à une classe d'optimisation de problèmes appelée Problèmes d'emballage . Dans votre cas, au lieu d'un polygone régulier comme conteneur, vous en avez un irrégulier, mais l'idée reste la même.
Ces problèmes d'optimisation sont généralement difficiles à NP, donc je ne pense pas qu'il existe un moyen facile d'obtenir la solution exacte et essayer toutes les combinaisons serait trop trop cher.
Il y a des gens intéressés par ce genre de problèmes; J'ai trouvé ce lien de quelques problèmes d'emballage spécifiques résolus: http://www2.stetson.edu/~efriedma/packing.html

La façon la plus simple que je vois est de définir un centre approximatif de la feuille de cuir, de déplacer l'ensemble de polygones là-bas et, en augmentant et en diminuant et en vérifiant si l'ensemble de polygones se trouve ou non à l'intérieur du polygone cible, d'obtenir un facteur d'échelle de plus en plus proche «f» pour votre ensemble de polygones souhaité.

Mais, à moins que vous n'utilisiez ce facteur pour une production de balles de jonglage à grande échelle, le faire à la main serait probablement assez.