donnée rectangle_a rectangle_b, qui a un syndicat défini de telle sorte qu'il s'agisse du rectangle contenant les deux rectangles, je souhaite déterminer les coordonnées des rectangles (non superposés) nécessaires à ajouter à rectangle_a pour créer l'union de rectangle_a et de rectangle_b:
Remarque: il ne s'agit que d'une configuration de la solution des rectangles. Les rectangles blancs ci-dessus pourraient être configurés différemment, tant qu'ils ne se chevauchent pas.
Y a-t-il un algorithme simple pour chaque cas d'intersection du rectangle? J'ai fait une première passe et des coins me manquent. Évidemment pas ma forté.
pourquoi? Lorsqu'il est panoramique dans une interface utilisateur, je veux seulement (i) mettre à jour les nouvelles parties de la toile (II) garder une trace de ce qui a été peint comme rectangle (l'union de rectangle_a et rectangle_b).
3 Réponses :
dire que nous représentons des rectangles par une paire de x, y paires de coordonnées Y: X1, Y1 pour le haut gauche et X2, Y2 pour le coin inférieur gauche. Supposons également que Y Coordonnées augmente vers le bas et x Les coordonnées X augmentent de gauche à droite.
Maintenant, supposons que le rectangle formé par l'Union d'A et B (selon votre définition de l'union) est le rectangle est u. P> SO, P>
Rt.x1=A.x2, Rt.y1=A.y1 Rt.x2=A.x2, Rt.y2=B.y2 Bot.x1=A.x1, Bot.y1=A.y2 Bot.x2=A.x2, Bot.y2=B.y2
Je suis tout à fait sûr que cela ne couvrira que le problème donné (dans les images), mais il y a de nombreux cas où vous avez besoin de plus de 2, ou juste 1 ajoutant un record. Le problème est toujours de trouver les CER dans tous les cas, le codage est sûrement pas une bonne approche ici.
@Insernickhere: Comme j'ai écrit dans ma réponse, je suppose que la mise en page est ce qui est montré dans les diagrammes pour la dernière moitié. Vous avez besoin de plus de 2 seulement si B est plus grand que A et couvre réellement A et s'étend de tous les côtés. Dans ce cas, U = B, déduisez simplement les rectors supplémentaires de cela. Si moins de 2 rectos supplémentaires sont nécessaires, ma méthode retourne des rect avec la zone = 0. Juste vérifier cela.
Je suis désolé je ne peux pas donner une solution de travail, mais ...
Au début, j'essaierais de dessiner de telles jolies images pour chaque cas que vous pouvez imaginer. Il y aura beaucoup de cas, où vous avez besoin de plus de 2 rectangles, ou juste un, non?
Je pense que le record contenant les autres est trivial - mais à ce moment-là, je ne peux pas penser à la procédure à suivre. :)
Edit: À ce stade, je pense à un algorith de remplissage d'inondation, remplissez simplement votre plus grand rect. Mais il y a 2 problèmes avec cela que je peux imaginer: comment utiliser la sortie de remplissage d'inondation pour générer des rects de celui-ci? Sera-ce la bonne façon, ou existe-t-il une solution d'algèbre linéaire ou quelque chose?
Si vous n'êtes pas préoccupé par la minimisation du nombre de rectangles retournés, vous pouvez simplifier le processus de pensée à celui qui ne renvoie pas plus de 8 rectangles: Si vous le souhaitez, vous pouviez Ensuite, vérifiez rapidement chaque rectangle pour voir si Par exemple, dans vos trois exemples, cette solution reviendrait 3, 1 et 5 rectangles et retournerait 0 dans le meilleur cas (lorsque B est contenu dans a) et 8 dans le pire des cas (lorsque A est contenu dans B). r.x1 == r.x2 || r.y1 == r.y2 (c'est-à-dire s'il a zéro zone) et jetez-le si oui. Dans la plupart des cas, plus de la moitié des rectangles peuvent être jetés de cette façon.
Exactement! La conversation sur la manière dont A et B Intersect semble sans importance. Vous pouvez toujours fusionner 1,2,3 en un et 6,7,8 dans un autre pour obtenir plus de 4 rectangles (et cela donnera une optimum si A est complètement dans le rectangle extérieur). Et si une touche une touche un des côtés, cela donnera l'optimum de 2 ou 3.
+1 Cette technique est relativement facile à mettre en œuvre et gère le rectangle de rectangle, peu importe où elle est par rapport à B. Compte tenu de la manière dont l'Union fonctionne, vous devriez toujours avoir à 3-5 de ces rectangles que vous pouvez ignorer (ils ont Zéro Zone). Parmi les rectangles restants, il devrait être relativement trivial pour combiner des rectangles adjacents et réduire le nombre de polygones que vous devez traiter.
Avez-vous toujours exactement deux rectangles à la fois?
Oui, toujours seulement deux rectangles originaux: A et B. Ces deux rectangles peuvent être des tailles complètement différentes.
Je trouve cela pas clair - dans la dernière image, que les règles déterminent comment les rectors résultants doivent être? Votre 3. Image, serait-il également valable pour punir les rectchices blancs? Ou "ne se chevauche pas" la seule restriction?
Et vont-ils toujours intersecter? Peut-on arriver que l'on se trouve dans l'autre? Peut-il arriver que la x-gamme de rectanche B soit entièrement contenue avec la x-gamme d'A (I.e B réside "ci-dessous" A, mais avec une plus grande largeur)? De même, peut-on couler à droite d'un (intersection, mais ne s'étendant pas au-dessus ou au-dessous) mais avec une hauteur inférieure?
@Insernickhere: bon point. Les rectangles de solution peuvent être dans n'importe quelle configuration tant qu'ils ne se chevauchent pas. Je vais clarifier dans l'OP.
@Shreeevatsar: Pour ce problème, le périmètre d'A va toujours intersecter le périmètre de B. Les deux exemples sont des configurations valides de A et B qui nécessitent des solutions.
Avez-vous besoin d'une solution qui présente le moins de rectangles possible? Sinon, une solution qui retourne toujours 8 rectangles (éventuellement de zone zéro) est triviale.
@Vearr: Un nombre minimum de rectangles serait préférable, mais je suis ouvert aux suggestions!