J'ai un problème dans lequel je dois vérifier si l'union d'un ensemble de formes de rectangles donnés un rectangle ou non. Je n'ai pas beaucoup d'expérience en résolution de problèmes de géométrie informatique. Ce que mon approche du problème était que, puisque je connais les coordonnées de tous les rectangles, je peux facilement trier les points, puis déduire les points de coin du plus grand rectangle possible. Ensuite, je pourrais balayer une ligne et voir si tous les points de la ligne tombent à l'intérieur du rectangle. Mais cette approche est défectueuse et cela échouerait parce que le syndicat peut être sous la forme d'un «U». Je serais une bonne aide si vous pouviez me pousser dans la bonne direction.
10 Réponses :
Peut-être ...
Rassemblez toutes les coordonnées X dans une liste et triez-les. Dans cette liste, créez une séquence d'intervalles adjacents. Faites la même chose pour les coordonnées Y. Maintenant, vous avez deux listes d'intervalles. Pour chaque paire d'intervalles ( Si chaque rectangle de produit est contenu dans au moins un de vos rectangles initiaux, l'union doit être un rectangle.
Rendre cela efficace (je pense que j'ai offert à propos d'un algorithme O (N 4 ) est une question différente entièrement. a = [x1, x2] à partir de la liste X, b = [y1, y2] de la liste des y), faites leur produit. rectangle A x b = (x1, y1) - (x2, y2)
L'efficacité est préoccupante parce que j'ai 1 10000 points avec la valeur des coordonnées allongées entre -2 ^ 32 et 2 ^ 32
Vous pouvez déduire les points d'angle de la plus grand rectangle possible, puis passez tout le rectangle partageant la frontière avec le plus grand rectangle possible, par exemple le fond et assurez-vous que la ligne est entièrement contenue dans leurs frontières. . Cela échouera également si un espace vide au milieu du rectangle est cependant un problème. Je pense que la complexité sera O (N2).
Je pense que vous êtes dans la bonne direction. Après avoir obtenu les coordonnées du plus grand rectangle possible,
Si le plus grand rectangle possible est un rectangle valide, chaque côté doit être l'union des côtés des rectangles d'origine. Vous pouvez numériser l'ensemble rectangle d'origine, trouver ces rectangles qui font partie du plus grand côté que nous recherchons (cela peut être effectué dans O (n) en vérifiant si x == le plus grandRectangle.top.x Si vous regardez haut Côté, etc.), demandons-les S.
Pour chaque côté S dans S, nous pouvons créer un intervalle [de, à]. Tout ce que nous devons vérifier, c'est si l'union de tous les intervalles correspond à la partie du plus grand rectangle. Cela peut être fait dans O (Nlog (n)) par des algorithmes standard ou en moyenne O (n) par une astuce de hachage (voir http://www.careercup.com/question?id=12523672 , voir mon dernier commentaire (du dernier commentaire) là-bas pour l'algorithme O (n)).
Par exemple, dites que nous avons eu deux rectangles 1 * 1 dans le premier quadrant, il est laissé des coordonnées inférieures (0,0) et (1,0). Le plus grand rectangle est 2 * 1 avec une coordonnée inférieure gauche (0,0). Comme [0,1] Union [1,2] est [0,2], le côté supérieur et inférieur correspond au plus grand rectangle, similaire pour le côté gauche et droit.
Supposons maintenant que nous ayons une forme de U. 3 * 1 à (0,0), 1 * 1 à (0,1), 1 * 1 à (2,1), nous avons eu le plus grand rectangle 3 * 2 à (0,0). Puisque pour le côté supérieur, nous avons eu [0,1] Union [1,3] ne correspond pas à [0,3], l'algorithme émettra l'union des rectangles ci-dessus n'est pas un rectangle.
Vous pouvez donc faire cela dans O (n) en moyenne, ou O (Nlog (n)) au moins si vous ne voulez pas gâcher avec un algorithme de godets de hachage complexe. Beaucoup mieux que o (n ^ 4)!
Edit: Nous avons un petit problème s'il existe un espace vide quelque part au milieu de tous les rectangles. Laissez-moi y penser ....
Edit2: Un moyen facile de détecter l'espace vide est pour chaque coin d'un rectangle qui n'est pas un point sur le plus grand rectangle, nous allons sortir un peu pour les quatre directions (diagonale) et vérifier si nous sommes toujours dans n'importe quel rectangle. C'est O (n ^ 2). (Qui ruine ma belle o (Nlog (n))! Peut-on peut-être venir une meilleure idée?
Assumer que vos rectangles sont alignés sur l'axe de coordonnées:
donné deux rectangles Alors, étant donné un ensemble de rectangles Calculer un rectangle maximum rendre le jeu pour chaque rectangle pour evey rectangle si fin, Si les rectangles ne sont pas alignés sur l'axe de coordonnées, vous pouvez utiliser un algorithme similaire, mais qui utilise des triangles au lieu de rectangles. Les seuls problèmes sont que la soustraction de triangles n'est pas si simple à mettre en œuvre et que la gestion des erreurs numériques peut être difficile. a , b , vous pouvez créer une fonction qui soustrait b de a retourner Ensemble de sous-rectangles de a (qui peut être le jeu de vide): Set = Soustract_rectangle (A, B)
R pour lequel vous voulez savoir si leur union est un rectangle:
gros qui couvre tous les rectangles sous forme ((min_x, min_y) - (max_x, max_y))
S contient le rectangle de grande: S = (Big)
B dans r :
s1 = ()
A dans s :
S1 = S1 + Subtract_Rectangle (A, B)
S = S1
s est vide, l'union des rectangles est un rectangle.
s contient les parties de Big non couvertes par n'importe quel rectangle de R
Votre propre version ne prend pas en compte le fait que les bords des rectangles peuvent être non parallèles les uns aux autres. Par conséquent, il pourrait ne pas être « le plus grand rectangle possible ».
Je voudrais essayer cette approche générale:
1) Déterminer la coque convexe. Vous pouvez trouver des algorithmes de calcul de l'enveloppe convexe ici http://en.wikipedia.org/wiki/Convex_hull_algorithms .
2) Vérifier si l'enveloppe convexe est un rectangle. Vous pouvez le faire en boucle à travers tous les points sur la coque convexe et vérifier si elles toutes les formes 180 ou angles de 90 degrés. Si elles ne le font pas, l'union est pas un rectangle.
3) Allez dans tous les points sur la coque convexe. Pour chaque chèque point si le point milieu entre ThisPoint et NextPoint se trouve sur le bord d'un rectangle initialement donné. Si chaque point milieu fait, l'union est un rectangle. Si elle n'a pas, l'union est pas un rectangle.
complexité serait O (n log h) pour trouver la coque convexe, O (h) de la deuxième partie et O (h * n) pour la troisième partie, où h est le nombre de points sur l'enveloppe convexe.
Edit:
Si l'objectif est de vérifier si l'objet résultant est un rectangle rempli , pas uniquement les contours et les coins rectangle puis ajoutez l'étape (4).
4) Tous les segments de ligne qui sont formées par des rectangles se croisent ou se touchent. Note - par définition tous ces segments de ligne sont des segments d'arêtes des rectangles donnés. Si un rectangle ne touche pas / Intersection d'autres rectangles, les segments de ligne sont des bords de it.
Pour chaque contrôle de segment de ligne si elle est le point milieu est
Si au moins l'un d'entre eux est vrai pour tous les segments de ligne, objet qui en résulte est un rectangle rempli.
Vous pouvez faire l'étape 3) en moins dans O (h * n) si vous indexez chaque rectangle par les coordonnées Vertex. Il devient o (h) .
L'étape 3 ne garantit pas que la partie interne du rectangle est également couverte.
@salva par définition de la coque convexe, étape 1 le fait.
@Umnyobe: Non, calculer la coque convexe garantit que vous obtenez un rectangle A contenant tous les rectangles donnés, mais cela ne garantit pas qu'il est complètement couvert par ces rectangles. La forme de l'union des rectangles d'entrée peut être un rectangle avec des trous.
Je n'ai pas examiné un problème similaire dans le passé, alors il y a peut-être des moyens beaucoup plus efficaces de le faire. Le problème clé est que vous ne pouvez pas examiner le confinement d'un rectangle d'un autre isolément car ils pouvaient être adjacents mais de former toujours un rectangle, ou un rectangle pouvait être contenu dans plusieurs.
Vous ne pouvez pas simplement regarder la projection de chaque rectangle sur les bords du rectangle de liaison, à moins que le problème vous permet de laisser des trous au milieu du rectangle, bien que ce soit probablement un chèque initial rapide pouvant être effectué. Avant l'approche exhaustive suivante:
Une approche simple vient de viendoir à l'esprit: si deux rectangles Donc, si la liste des rectangles forme un rectangle plus grand, tout ce dont vous avez besoin à plusieurs reprises sur les rectangles et "Unifier «Les paires d'eux en un seul plus grand. Si dans une itération, vous pouvez unifier aucun, il n'est pas possible de créer un rectangle plus grand que vous n'avez déjà, avec ces pièces; Sinon, vous garderez des rectangles "unificer" jusqu'à ce qu'un seul soit laissé. p> [1] Partager, comme dans ils ont le même bord fort> pareil; il ne suffit pas que l'un d'entre eux ait un avantage inclus dans l'une des bords des autres. P> Étant donné que l'efficacité semble être un problème, vous pourriez probablement accélérer par Création de deux index de rectangles, l'un avec la taille de bord plus gros et l'autre avec la taille de bord plus petite. p> puis comparez les bords de même taille et si elles sont identiques aux deux rectangles, retirez-les de Les index et ajoutent le nouveau rectangle aux index. P> Vous pouvez probablement vous accélérer en ne faisant pas passer à la prochaine itération lorsque vous unifiez quelque chose, mais pour passer à la fin des index avant de réitérer. (S'arrêtant lorsqu'une itération ne fait pas d'unifications, il n'y a qu'un seul rectangle gauche.) P> En outre, les bords d'un rectangle résultant de l'unification sont toujours égaux ou supérieurs aux bords des rectangilles d'origine. de [] [] [] [] [] code> ou une contient l'autre [[]] code>. Efficacité h2>
Donc, si les index sont commandés par la taille de bord ascendant, le nouveau rectangle sera inséré dans la même position que vous vérifiez ou dans des positions à vérifier, de sorte que chaque unification ne nécessitera pas de cycle d'itération supplémentaire. (Lorsque le nouveau rectangle unifiable n'abandonnera assuréement aucun rectangle déjà enregistré dans cette itération, car ses bords sont plus grands que tous les bords vérifiés.)
Pour que cela tienne, à chaque étape d'une itération particulière, vous devez tenter l'unification sur le prochain bord inférieur de l'un des index: p>
Exemples H2>
A B C D
E F G H
I J K L
Les rectangles peuvent se chevaucher et couvrir le rectangle extérieur sans partager aucun bord
comme JVA a déclaré: "Votre propre version ne prend pas en compte que les bords des rectangles peuvent être non parallèles les uns aux autres." Cette réponse suppose également des rectangles "parallèles".
Si vous avez une grille par opposition à avoir besoin d'une précision infinie, en fonction du nombre et de la tailles des rectangles et de la granularité de la grille, il pourrait être réalisable de la force de brute.
Prenez simplement votre "plus gros rectangle possible" et testez tous ses points pour voir si chaque point est dans au moins l'un des plus petits rectangles.
J'ai enfin été capable de trouver le projet JavaScript impressionnant (grâce à la recherche Github :)!)
https://github.com/evanw/csg.js
Regardez également dans Ma réponse ici avec d'autres projets intéressants
cas général, pensant aux images:
Et s'il y a un espace vide au milieu du rectangle à la suite de l'Union? Est-il considéré comme un rectangle d'union valide?
Les rectangles sont-ils supposés être axes alignés ou partager la même orientation?
Oh, si je pouvais me souvenir du nom de ce projet JavaScript qui utilise une belle technique spéciale ... et cela pourrait même combiner des objets arbitraires. Quelques choses avec des triangles
N'a toujours pas trouvé le projet, mais cela pourrait aider: Stackoverflow.com/Questtions/2140070/...