Je recherche un algorithme d'emballage qui réduira un polygone régulier dans des rectangles et des triangles droits. L'algorithme devrait tenter d'utiliser aussi peu de formes que possible et devrait être relativement facile à mettre en œuvre (compte tenu de la difficulté du défi).
Si possible, la réponse à cette question devrait expliquer les heuristiques générales utilisées dans l'algorithme suggéré.
3 Réponses :
Ce n'est pas spécifiquement des rectangles + des triangles droits, mais un bon point de recherche pour rechercher des polygones tesselants est Voronoi Diagrams et des triangulations de Delaunay et ici et ici .
En fait, si "juste des triangles droits" est suffisamment bon, celles-ci sont garanties de triangulés pour vous et vous pouvez toujours diviser n'importe quel triangle en deux triangles droits, si vous avez vraiment besoin de ceux-ci. Ou vous pouvez couper des "conseils" de triangles pour faire plus de triangles droits et certains rectangles hors des triangles de droite.
Vous pouvez aussi essayer Coupage d'oreille , soit en balayant radialement, si vous Sachez que vous avez des polygones assez réguliers ou en «coupant le plus grand morceau convexe». Ensuite, divisez chaque triangle restant en deux pour créer des triangles droits.
Vous pouvez essayer de faire moins de pauses en balayant d'une manière et d'une autre pour faire un trapèze et le scinder différemment, mais vous devez alors faire un chèque pour vous assurer que votre balayage n'a pas traversé une autre ligne . Vous pouvez toujours clipser, même avec quelque chose de pratiquement fractal.
Cependant, cela crée parfois des triangles très minces. Vous pouvez effectuer des heuristiques, comme «Prendre le plus grand», au lieu de couper continuellement le long du bord, mais cela prend plus de temps, approchant de O (n ^ 2). Delaunay / Vornoi le fera plus rapidement dans la plupart des cas, avec des triangles moins minces. 
(Source: eruciforme.com )
Absolument doit être des rectangles et des triangles droits. Je sais que cela semble étrange, mais c'est une exigence d'utilisateur.
mis à jour. Vous pouvez transformer n'importe quel triangle en triangles droits et rectangles assez facilement.
Les triangulations de Delaunay ne sont pas idéales ici car elles introduisent des points supplémentaires et inutiles au milieu. Chacun de ces points internes peut être "traîné" sur un sommet polygone adjacent et vous êtes laissé avec un ensemble de triangles plus petits.
Vous pouvez essayer "couper" Le plus grand rectangle Peut tenir dans le polygone , laissant derrière quelques restes. Continuez à répéter la découpe des rectangles sur les restes, jusqu'à ce que vous vous retrouviez avec des pièces triangulaires. Ensuite, vous pouvez les diviser en deux triangles droits si nécessaire. Je ne sais pas si cela produira toujours des solutions qui vous donneront le moins de rectangles et de triangles droits.
Je pense que ce n'est pas une bonne idée non plus: manger plus de la zone que possible avec le premier rectangle ne vous laissera pas avec la forme "plus facile" par la suite.
Ce n'était pas clair quelles étaient ses exigences. Les formes les moins totales ou la plupart des superficies de la moindre forme ...
Pour des polygones réguliers cependant, cela vous donnerait toujours des formes "belles". Encore une fois, je ne sais pas si cela vous donnera les solutions "les plus optimales".
Je pense que la réponse est assez simple pour régulier polygones.
Trouvez un axe de symétrie et dessinez une ligne entre chaque sommet et son miroir. Cela divise le polygone en trapèze. Chaque trapèze peut être transformé en un rectangle et deux triangles droits.
Vous pouvez obtenir un crédit supplémentaire en prouvant que cela produit le nombre minimum de tuiles. :)
Je crois maintenant que c'est en fait optimal :-)
Non, ce n'est pas toujours optimal. Prenons par exemple un hexagone régulier avec deux côtés parallèles à l'axe X = 0. Ensuite, cet algorithme génère 2 rectangles et 4 triangles droits, mais 1 rectangle et 4 triangles suffiraient. Néanmoins, la solution est probablement assez bonne et facile à mettre en œuvre.
Cela génère 1 rectangle + 2 triangles si vous êtes assez prudent pour "diviser" le polygone (générer un rectangle) le long de la dernière corde d'abord.
Agréable! Va attendre un peu pour voir si quelqu'un d'autre pèse, mais cela a l'air génial! PS Je prévois de poser la même question mais pour des polygones irréguliers avec une prime de 200 points.
Soyez prudent avec des polygones réguliers mais impairs-Vertex, l'algorithme change légèrement. Cependant, cela fournira généralement les plus grands rectangles avec une grande surface. Cela créera également de petits triangles sur les bords, si cela compte pour vous. Faites-moi savoir si vous avez nonné une pour irrégularités - mon message était plus dirigé contre ça ...
@Mau L'OP spécifie que les triangles doivent avoir un angle droit (c'est-à-dire 90 degrés). Par conséquent, vous ne pouvez pas diviser un hexagone régulier en un rectangle et 2 triangles à droite. Il y a d'autres cas où l'algorithme apparaît avec un rectangle supplémentaire, par ex. Un octogone rectangulaire aligné de manière à ce que les coins soient à un angle 0, 45, 90 etc. loin du centre. Encore une fois, cela peut avoir d'importance si la simplicité de la solution est importante.
@ABC: Correct, je voulais dire 4 triangles.
Une belle propriété est que cet algo renvoie des formes d'axe alignées. Je ne suis pas sûr que ce soit une exigence, mais c'est souvent une propriété utile.
Un cas simple où cet algorithme n'est pas optimal est pour un triangle droit menant sur son hypoténuse. Mais j'aime sa simplicité, +1.
Est-ce pour une classe d'algorithmes ou une classe graphique de l'ordinateur?
Ce n'est pas pour une classe. Je ne suis pas à l'école.
En fait, je pourrais être disposé à donner à quelqu'un qui peut répondre à la question bien une offre d'emploi s'ils peuvent programmer pour l'iPhone, Mac Desktop et .NET. ;)
Merci, je travaille pour moi en ce moment, mais je te garderai à l'esprit. :-)