Algorithme pour ajuster des polygones 2D dans une zone?

Question

Existe-t-il une norme pour cela? Nom de l'algorithme?

Dites: J'ai 10 polygones de tailles différentes. J'ai une zone de taille spécifique.

Je veux savoir comment remplir la plupart des polygones de cette zone et comment ils sont ajustés.

Remarque: Les polygones peuvent être pivotés en fonction du jeu de restrictions.

Answer 1

Un nom possible est un Problème d'emballage . Il est lié au problème de sac à dos . Ces problèmes ont tendance à être difficiles à résoudre et beaucoup nécessitent des heuristiques. Si vous pouvez limiter les formes de polygones et de zones autorisées, il peut exister un algorithme plus efficace pour votre cas particulier.

Answer 2

Vous pouvez consulter la rubrique "Liens de danse". sur Wikipedia pour la solution de Donald Knuth au problème de la couverture exacte - qui inclut la mosaïque - votre question peut être considérée comme un problème de mosaïque

Answer 3

SI (c'est un gros si) tous vos polygones étaient des rectangles, et la zone dans laquelle ils doivent être insérés est également un rectangle, alors cela s'appellera bin-packing, Google vous submergera d'informations à ce sujet. Si ce n’est pas le cas, alors je suppose que vous recherchez une variante de l’emballage à la poubelle, et je suppose qu’il ya un peu plus que vous êtes dans un problème de NP pour lequel "essayer et tester" est le meilleur algorithme du moment.