Qu'est-ce qu'un algorithme efficace pour trouver une zone de rectangles superposés

Question

Ma situation

• Entrée: un ensemble de rectangles
• chaque rectangle est composé de 4 doubles comme ceci: (x0,y0,x1,y1)
• ils ne sont pas "tourné" à n'importe quel angle, tout ce qu'ils sont "normaux" de rectangles aller "up/down" et "gauche/droite" par rapport à l'écran
• ils sont placés au hasard: ils peuvent être sur de toucher sur les bords, qui se chevauchent , ou de n'avoir aucun contact
• Je vais avoir plusieurs centaines de rectangles
• ceci est implémenté en C#

J'ai besoin de trouver

• Le secteur qui est formé par leur chevauchement de la région dans la toile que plus d'un rectangle "couvre" (par exemple avec deux rectangles, il serait l'intersection)
• Je n'ai pas besoin de la géométrie de la part de chevauchement simplement la zone (exemple: 4 sq pouces)
• Les chevauchements ne devrait pas être compté plusieurs fois, de sorte par exemple, imaginez 3 rectangles qui ont la même taille et de la position qu'ils sont à droite sur le dessus les uns des autres -, cette zone ne doit être compté qu'une seule fois (trois fois)

Exemple

• L'image ci-dessous contient trois rectangles: A,B,C
• A et B se chevauchent (comme indiqué par un tiret)
• B et C se chevauchent (comme indiqué par un tiret)
• Ce que je cherche, c'est la zone où les tirets sont affichés

-

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC

Answer 1

Un moyen efficace de calcul de cette zone est d'utiliser un algorithme de balayage. Supposons que nous avons un balayage vertical de la ligne L(x) par le biais de l'union des rectangles U:

• tout d'abord, vous avez besoin pour construire une file d'attente d'événements Q, qui est, dans ce cas, la liste ordonnée de tous les coordonnées x (gauche et droite), de rectangles.
• pendant le balayage, vous devez maintenir un 1D discbased, qui devrait vous donner la longueur totale de l'intersection de L(x) et U. La chose importante est que cette longueur est constante entre deux événements successifs, q et q' de Q. Donc, si l(q) désigne la longueur totale de L(q+) (c'est à dire L juste sur la droite de q), entrecoupé de U, la surface balayée par L entre les événements de q et q' est exactement l(q)*(q' - q).
• vous avez juste à résumer tous ces secteurs balayés pour obtenir la totale.

Il nous reste à résoudre le problème 1D. Vous voulez un 1D structure, qui calcule dynamiquement une union de (vertical) des segments. Dynamique, je veux dire que vous avez parfois ajouter un nouveau segment, et parfois en supprimer une.

J'ai déjà détaillé dans ma réponse à cette réduction des plages question comment le faire de manière statique (qui est en fait un 1D de balayage). Donc, si vous voulez quelque chose de simple, vous pouvez appliquer directement que (en recalculant l'union pour chaque événement). Si vous voulez quelque chose de plus efficace, vous avez juste besoin d'adapter un peu:

• en supposant que vous connaissez l'union de segments de S₁...S_n se compose de segments disjoints D₁...D_k. L'ajout S_n+1 est très facile, il vous suffit de localiser les deux extrémités de la S_n+1 entre les extrémités de D₁...D_k.
• en supposant que vous connaissez l'union de segments de S₁...S_n se compose de segments disjoints D₁...D_k, la suppression du segment S_i (en supposant que S_i a été inclus dans D,_j) signifie recalculant l'union des segments D_j a consisté, à l'exception de S_i (à l'aide de l'algorithme statique).

C'est votre algorithme dynamique. En supposant que vous utiliserez ensembles classés avec le journal de localisation en temps requêtes pour représenter D₁...D_k, ce qui est probablement le plus efficace non spécialisés méthode que vous pouvez obtenir.

Answer 2

D'une façon-out de l'approche est de tracer une toile! Dessiner chaque rectangle à l'aide d'un semi-transparent couleur. L' .NET runtime faire le dessin dans optimisé, code natif - ou même à l'aide d'un accélérateur matériel.

Ensuite, vous devez lire la pixels. Est chaque pixel, la couleur d'arrière-plan, le rectangle de couleur, ou d'une autre couleur? La seule façon dont il peut être d'une autre couleur est si deux ou plus de deux rectangles se chevauchent...

Si c'est trop de la triche, je recommanderais le quad-arbre comme un autre répondeur n', ou le r-tree.

Answer 3

Ceci est un code rapide et sale que j'ai utilisé dans le TopCoder SRM 160 Div 2.

t = haut
b = botttom
l = gauche
r = droite

 public class Rect
{
    public int t, b, l, r;

    public Rect(int _l, int _b, int _r, int _t)
    {
    	t = _t;
    	b = _b;
    	l = _l;
    	r = _r;
    }	

    public bool Intersects(Rect R)
    {
    	return !(l > R.r || R.l > r || R.b > t || b > R.t);
    }

    public Rect Intersection(Rect R)
    {
    	if(!this.Intersects(R))
    		return new Rect(0,0,0,0);
    	int [] horiz = {l, r, R.l, R.r};
    	Array.Sort(horiz);
    	int [] vert = {b, t, R.b, R.t};
    	Array.Sort(vert);

    	return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
    } 

    public int Area()
    {
    	return (t - b)*(r-l);
    }

    public override string ToString()
    {
    	return l + " " + b + " " + r + " " + t;
    }
}
 

Answer 4

Voici quelque chose qui se trouve sur le dessus de ma tête sonne comme il pourrait le travail:

1. Créer un dictionnaire avec un double de la clé, et une liste de rectangle+valeurs booléennes, comme ceci:

   Dictionnaire< Double, Liste< KeyValuePair< Rectangle, Boolean>>> rectangles;

2. Pour chaque rectangle dans votre ensemble, trouver le correspondant de la liste de l'x0 et x1 valeurs, et ajouter le rectangle à cette liste, avec une valeur booléenne true pour x0, et false pour x1. De cette façon, vous avez maintenant une liste complète de toutes les coordonnées x de chaque rectangle, soit entre le (vrai) ou des feuilles (faux) dans la direction x

3. Saisir toutes les clés de ce dictionnaire (toutes les différentes coordonnées x), de les trier et de les parcourir en boucle dans l'ordre, assurez-vous que vous pouvez obtenir à l'état actuel de la valeur x, et le prochain comme bien (vous en avez besoin à la fois). Cela vous donne des bandes individuelles de rectangles

4. Maintenir un ensemble de rectangles, vous êtes actuellement à la recherche à, qui débute vide. Pour chaque valeur x vous parcourez au point 3, si le rectangle est inscrit avec une valeur true, l'ajouter à l'ensemble, sinon le supprimer.
5. Pour une bande de trier les rectangles par leur abscisse
6. Boucle à travers les rectangles dans la bande de gaza, le comptage de chevauchement des distances (pas clair pour moi encore comment le faire efficacement)
7. Calculer la largeur de bande de fois la hauteur de chevauchement des distances pour obtenir des zones

Exemple, 5 rectangles, dessiner sur le dessus les uns des autres, de a à e:

aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
        ddddddddddddddddddddddddddddd
        ddddddddddddddddddddddddddddd
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

Voici la liste des coordonnées x:

v       v  v   v      v   v         v  v  v   
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

La liste serait (où chaque v est simplement une coordonnée de départ à 0 et allant jusqu'à):

0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b

Chaque bande serait donc (rectangles classées de haut en bas):

0-1: a, c
1-2: a, d, c
2-3: a, d
3-4: d
4-5: d, e
5-6: b, d, e
6-7: b, e
7-8: b

pour chaque tranche, le chevauchement serait:

0-1: none
1-2: a/d, d/c
2-3: a/d
3-4: none
4-5: d/e
5-6: b/d, d/e
6-7: none
7-8: none

J'imagine qu'une variation de la tri + enter/leave algorithme pour le haut-en bas à vérifier serait faisable ainsi:

1. trier les rectangles nous sommes en train d'analyser dans la bande de gaza, du haut vers le bas, pour les rectangles avec le même haut-de coordonner, de les trier en bas de coordonnées ainsi
2. parcourir les coordonnées y, et quand vous entrez dans un rectangle, l'ajouter à l'ensemble, lorsque vous quittez un rectangle, le retirer de l'ensemble
3. chaque fois que le jeu a plus d'un rectangle, vous avez chevauchement (et si vous veillez à ajouter/supprimer tous les rectangles qui ont le même haut/bas de coordonnées que vous êtes en train de regarder, qui se chevauchent les rectangles ne serait pas un problème

Pour le 1-2 bande ci-dessus, vous itérer comme ceci:

0. empty set, zero sum
1. enter a, add a to set (1 rectangle in set)
2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate)
3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y
4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate)
5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y)
6. multiply sum with width of strip to get overlapping areas

Vous ne devez conserver une réelle définie ici non plus, juste le nombre de rectangles, vous êtes à l'intérieur, chaque fois que cela est de 1 à 2, stockez-le dans y, et chaque fois qu'il passe de 2 à 1, calculer le courant y stockée y, et la somme de cette différence.

Espérons que cela était compréhensible, et comme je l'ai dit, c'est hors de ma tête, pas encore testé en aucune façon.

Answer 5

Vous pouvez simplifier un peu ce problème si vous divisez chaque rectangle en petits rectangles. Collectez toutes les coordonnées X et Y de tous les rectangles, et ceux-ci deviennent vos points de partage - si un rectangle traverse la ligne, divisez-le en deux. Lorsque vous avez terminé, vous avez une liste de rectangles qui se chevauchent à 0% ou 100%, si vous les triez, il devrait être facile de trouver les mêmes.