Vous cherchez une « force brute » non algorithme pour éliminer les zones d'intersection d'une collection de Rects

Question

J'ai une n-collection de taille Rects, dont la plupart se croisent. Je voudrais supprimer les intersections et réduire les Rects se coupent en petits rects de disjoints.

Je pourrais facilement la force brute une solution, mais je suis à la recherche d'un algorithme efficace.

Voici une visualisation:

Original:

traités:

Idéalement, la signature de la méthode ressemblerait à ceci:

public static List<RectF> resolveIntersection(List<RectF> rects);

la sortie serait supérieure ou égale à l'entrée, où la sortie résout le dessus représentation visuelle.

Answer 1

est un problème que je résolu dans le passé. La première chose à trier les rectangles en utilisant la valeur x ou y de l'un des bords. Disons que vous commandez dans la direction y et utilisez le bord supérieur. Le rectangle le plus élevé dans votre exemple est d'abord dans l'ordre. Pour chaque rectangle que vous connaissez sa taille dans la direction y.

Maintenant, pour chaque entrée (appeler l'entrée en cours, elle correspond à un rectangle) dans la liste triée vous effectuez une recherche en avant dans la liste jusqu'à ce que vous atteignez une plus grande entrée que l'entrée en cours + la taille rectangle correspondant. (Appeler l'entrée d'arrêt)

Toutes les entrées de la liste triée entre l'entrée actuelle et cette entrée d'arrêt seront les intersections potentielles. Il suffit de vérifier si les rectangles x-gammes se croisent.

Lors du choix de trier dans la direction x ou y, il sera préférable de choisir la dimension qui est plus grand que cela impliquera moins intersection en moyenne donc moins vérifier.

Voici un exemple. Les rectangles sont définis comme R (x1, x2, y1, y2) où x1 est le côté gauche, x2 est droite, y1 et y2 est haut en bas est

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)

trier selon y1 à donner

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

so, rectangle 1 a y1 + size = 0 + 4 = 4 ce qui implique qu'il sera rectangle potentiellement intersection 3 (y1 value = 3 <4) et le rectangle 4 (y1 value = 3 <4), mais pas rectangle 2 (valeur de y1 = 6> 4) ... pas besoin de vérifier les rectangels dans la liste après 2

Rectangle 3 a y2 + size = 2 + 3 = 5 ce qui implique qu'il sera rectangle potentiellement Intersection 4 (y1 valeur = 3 <5) mais pas recatngle 2 (y1 valeur = 6> 5) pas besoin de vérifier les rectangels dans la liste après 2

Rectangle 4 a y2 + size = 3 + 4 = 7 ce qui implique qu'il sera potentiellement rectangle se coupent deux (valeur de y1 = 6 <7), mais pas recatngle 5 (valeur de y1 = 9> 7)

Bien sûr, avec un grand nombre de rectangles, vous aurez en général seulement pour vérifier une fraction des paires possibles pour l'intersection.

Answer 2

algoithms Sweepline sont bonnes au traitement des intersections dans des univers 2D. Je veux dire considérer une ligne horizontale se déplaçant vers le bas d'un bord de rectangle à l'autre bord du rectangle. La ligne atteint un certain nombre de rectangles, formant les listes actives dites. La liste active est mis à jour à chaque maintenue mouvement.

En étudiant les plages de long de la ligne abscisses horizontale, vous pouvez détecter les chevauchements.

Une étude attentive de toutes les configurations devraient vous permettre de diviser les rectangles comme vous le souhaitez dans un seul balayage, avec une complexité plus faible que la force brute (plus proche de N ^ 1,5 que de N ^ 2).

Answer 3

ce que vous êtes descrbing est le problème d'emballage, jetez un oeil à wikipedia

il se réfère à cette article décrivant un algorithme pour les rectangles emballage rectangles

est de l'article:

Cet article décrit un algorithme rapide pour emballer une série de rectangles de différentes largeurs et hauteurs en un seul rectangle englobant, sans chevauchement et d'une manière qui minimise la quantité d'espace perdu dans le rectangle d'encadrement.