Couvrir un polygone concave avec un nombre minimum de rectangles

11

J'essaie de couvrir un simple polygone concave avec un minimum de rectangles. Mes rectangles peuvent avoir n'importe quelle longueur, mais ils ont des largeurs maximales, et le polygone n'aura jamais d'angle aigu.

J'ai pensé à essayer de décomposer mon polygone concave en triangles qui produisent un ensemble de rectangles se chevauchant au minimum délimitant au minimum chaque triangle, puis à fusionner ces rectangles en plus grands. Cependant, je ne pense pas que cela fonctionnera pour les petites encoches dans les bords du polygone. Les triangles créés par les sommets réflexes sur ces encoches créeront les mauvais rectangles. Je recherche des rectangles qui s'étendent / ignorent les encoches.

Je ne sais vraiment rien de la géométrie informatique, donc je ne suis pas vraiment sûr de savoir comment commencer à poser la question.

J'ai trouvé d'autres articles similaires, mais pas ce dont j'ai besoin:

Quelques exemples: le noir est l'entrée. Le rouge est la sortie acceptable.

entrez la description de l'image ici

Un autre exemple: la deuxième sortie est préférable. Cependant, la génération des deux sorties et l'utilisation d'un autre facteur pour déterminer la préférence sont probablement nécessaires et ne relèvent pas de la responsabilité de cet algorithme.

entrez la description de l'image ici

entrez la description de l'image ici

Les polygones qui imitent les courbes sont extrêmement rares. Dans ce scénario, une grande partie de la surface des rectangles est gaspillée. Cependant, cela est acceptable car chaque rectangle obéit à la contrainte de largeur maximale.

entrez la description de l'image ici

Aussi, j'ai trouvé cet article proche de ce dont j'avais besoin:

Peut-être une meilleure question est "Comment puis-je identifier des parties de type rectangulaire d'un polygone concave?" entrez la description de l'image ici

Voici une image montrant l'implémentation souhaitée: entrez la description de l'image ici

Le vert est l'utilisation réelle du matériau. Les rectangles rouges sont les dispositions. Le bleu est le MBR de tout le polygone. Je pense que je devrais essayer d'obtenir de petits MBR et de les remplir. Les 2-3 rectangles verts dans le coin supérieur gauche qui se terminent au milieu du polygone sont chers. C'est ce que je veux minimiser. Les rectangles verts ont une largeur et une hauteur min et max, mais je peux utiliser autant de lignes et de colonnes nécessaires pour couvrir une région. Encore une fois, je dois minimiser le nombre de rectangles qui ne s'étendent pas sur l'entrée. Je peux également modifier la forme du rectangle vert pour l'adapter aux petits endroits, ce qui est également très cher. En d'autres termes, obtenir autant de rectangles que possible pour s'étendre autant que possible est idéal.

co.combinatorics cg.comp-geom Josh C.
la source
3
Votre titre dit polygones convexes, mais la question parle de polygones concaves. Vous avez peut-être besoin de faire quelques corrections?
Ankur
1
@JukkaSuomela, dans les deux premières images, le polygone est à peu près de la même taille, et dans la première image, j'aurais pu exécuter trois rectangles verticalement comme je l'ai fait dans la seconde. Cependant, cela est moins souhaitable. Je pense que l'astuce a à voir avec les périmètres des rectangles. Peut-être que ce que j'essaie de faire est de minimiser la quantité de limites du rectangle qui se trouve à l'intérieur du polygone et de maximiser la quantité de limites colinéaire avec les bords du polygone. Cependant, parfois les rectangles doivent déborder du polygone pour le couvrir entièrement.
Josh C.
1
@JohnMoeller, je comprends. Il s'agit d'un problème où un humain peut identifier la solution facilement, mais énoncer correctement le problème est assez difficile. Le problème est similaire à la pose de tapis ou de papier peint et le problème réel est structurel / architectural. J'essaie d'identifier des régions de dispositions rectangulaires qui seront plus tard remplies d'une autre forme de tesselation. Trouver ces rectangles et gérer les régions non rectangulaires est le problème. Faites-moi savoir si je peux vous expliquer davantage.
Josh C.
2
Je pense que nous devrions d'abord aborder cette question comme une question de modélisation: le but n'est pas de proposer un algorithme qui résout un problème d'optimisation bien défini, mais le but est de définir le problème d'optimisation.
Jukka Suomela
3
@JoshC .: Il serait peut-être également utile que vous essayiez de nous en dire plus sur l'application du monde réel. Je comprends de votre description que, par exemple, la coupe est assez coûteuse - idéalement, les pièces rectangulaires nécessiteraient le moins de coupe possible. Est-ce correct?
Jukka Suomela

Réponses:

3

Il s'agit d'une variante de la couverture d'ensemble géométrique. Selon les paramètres exacts, vous pourrez peut-être faire une bonne approximation. Le problème est bien sûr NP-Hard. Les huersitics naturels doivent utiliser un algorithme gourmand (choisissez toujours le rectangle / la bande qui couvre la plus grande partie non encore couverte. La technique alternative est d'utiliser la repesage. Il y a des résultats théoriques intéressants, mais franchement, rien qui ne devrait être trop utile en pratique Une hueristic intéressante que vous voudrez peut-être essayer, est d'abord de décomposer votre polygone en un nombre minimal de formes convexes (en utilisant l'algorithme de programmation dynamique Keil), puis de couvrir chaque polygone convexe séparément ...

Sariel Har-Peled
la source
Je ne connais pas l'algorithme de programmation dynamique Keil. Cependant, j'ai trouvé une méthode pour travailler en utilisant une combinaison des algorithmes Rectangle le plus grand et Rectangle à limite minimale avec quelques variantes basées sur l'heuristique.
Josh C.
2

Je pense que ce document peut être d'une certaine utilité. Évidemment, ce n'est pas le même problème - en fait c'est le problème inverse, couvrant un rectangle avec des polygones - mais certaines des idées pourraient être un point de départ. En particulier, ce problème inverse est NP-difficile et je soupçonne que le vôtre peut également l'être (bien qu'il n'y ait pas d'extension évidente de la réduction pour autant que je sache).

E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell et V. Polishchuk. Minceur scandinave sur le dessus du gâteau: sur la plus petite boîte à taille unique. Amusez-vous avec les algorithmes . pg.16-27. 2012

SamM
la source
1
Merci pour votre suggestion. J'ai travaillé avec les départements d'ingénierie et de fabrication de mon entreprise pour apporter plus de clarificaiton à ce problème. J'attends toujours de confirmer, mais je pense maintenant qu'un algorithme qui retournerait des ensembles de plus grands rectangles inscrits fonctionnerait. Bien qu'il ne couvre pas complètement la forme, il donnerait la préférence aux régions orthognales tout en laissant les régions non orthogonales à certaines heuristiques. La seule astuce consiste à maximiser ces régions orthogonales. Voir ma dernière image avec les 9 figures de type lamda.
Josh C.