Comment trouver des rectangles de zone libre?

Question

Quelqu'un peut-il m'aider à dessiner des rectangles pour l'espace dans une zone de délimitation avec n obstacles rectangulaires? Il peut y avoir n'importe quel nombre d'obstacles rectangulaires parallèles à l'axe, ce n'est pas un cas unique, donc différents cas d'angle doivent être pris en considération. Est-il préférable d'utiliser l'algorithme de bande horizontale maximale? Et comment?

Description du problème:

1.SUB1 et SUB2 sont les obstacles et vous ne serez pas toucher la interne de SUB1 et SUB2, vous devez trouver toutes les zones libres à l'extérieur à tous les subs et créer des rectangles d'eux.

2. Vous devrez trouver tous les rectangles possibles sur les rectangles des zones libres en conséquence avec son balayage de gauche à droite sans couper les SUB;

Le nombre total des rectangles spatiaux horizontaux maximaux dans ce cas doit être de 7 ou en général, 3n + 2 (n étant le nombre d'obstacles): alt text http://img25.imageshack.us/img25/452/pic1gts.png

alt text http://img22.imageshack.us/img22/3417/pic2h.png

alt text http://img16.imageshack.us/img16/5818/pic3h.png

alt text http://img13.imageshack.us/img13/2151/pic4.png

Cliquez pour voir les images: http://img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16/5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png

Answer 1

Vous cherchez l'algorithme le plus simple, ou celui qui trouve les rectangles divisés de façon optimale plus petit nombre? Commencez par utiliser l'algorithme le plus facile à coder comme base de référence, ce qui est probablement suffisant pour de nombreuses applications en tant que telles. C'est facile à écrire et à comprendre.

Initialisez votre liste de rectangles pour n'en inclure qu'un seul, le rectangle de l'écran. Maintenant, pour chaque obstacle, parcourez la liste rectangle. Si le rectangle croise l'obstacle, supprimez le rectangle de la liste et insérez de nouveaux rectangles plus petits qui évitent l'obstacle. C'est un petit sous-problème, facile à résoudre en regardant simplement quelle partie de l'obstacle coupe le rectangle. Vous pouvez vous retrouver avec 0, 1, 2, 3 ou 4 nouvelles sous-bandes. (Considérez les six cas où l'obstacle croise un coin, deux coins, tous les coins, aucun coin et aucun bord, aucuns coins et 1 bord, aucuns coins et 2 bords.)

Répétez pour tous les obstacles, et vous êtes à gauche avec une liste de rectangles fendus qui couvrent votre zone sans heurter les obstacles. Ce n'est pas idéalement peu, mais c'est un bon endroit pour commencer et 10 minutes pour coder.

Answer 2

Oui, je cherche à trouver le plus petit nombre de rectangles.

Je voudrais obtenir un peu de clarification sur votre suggestion. "Initialisez votre liste de rectangles pour en inclure un seul, le rectangle de l'écran". Par rectangle d'écran, voulez-vous dire le canevas de délimitation externe? Ensuite, je n'aurais qu'un seul rectangle dans la liste Rectangle. "Maintenant, pour chaque obstacle, parcourez la liste rectangle.Si le rectangle croise l'obstacle, enlevez le rectangle de la liste et insérez de nouveaux rectangles plus petits qui évitent l'obstacle. "

Pour procéder ci-dessus, devrais-je effectuer une comparaison basée sur chaque bord colinéaire des obstacles (4 côtés -. gauche, droite, haut, bas) Signification chaque bords SUB1 et SUB2 à 4 points d'angle sont examiner pour voir si elle croise l'autre ou la zone de délimitation de toile est ce droit

Answer 3

la structure de données-couture coin? Je ne connais aucune implémentation open-source, mais le document original, ou du moins canonique, est Ousterhout (de Tcl Fame): http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html