Déterminer si deux rectangles se chevauchent les uns les autres?
Je suis en train d'écrire un programme en C++ qui prend la suite des entrées de l'utilisateur de construire des rectangles (entre 2 et 5): la hauteur, la largeur, x-pos, y-pos. Tous ces rectangles existera en parallèle aux axes x et y, c'est l'ensemble de leurs bords doivent pentes de 0 ou l'infini.
J'ai essayé de mettre en œuvre ce qui est mentionné dans cette question, mais je suis de ne pas avoir beaucoup de chance.
Mon actuel de la mise en œuvre est le suivant:
//Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
//point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
//Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
//rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
//point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
//test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
Cependant, je ne suis pas tout à fait sûr si (un), j'ai implémenté l'algorithme de je lien correctement, ou si je n'ai exactement comment l'interpréter?
Des suggestions?
- je pense que la solution à votre problème ne concerne pas toute multiplication.
Vous devez vous connecter pour publier un commentaire.
ou, à l'aide de coordonnées Cartésiennes
(Avec X1 être de gauche coord, X2 droit d'être coord, l'augmentation de gauche à droite et Y1 être coord, et Y2 étant Bas coord, croissant du bas vers le haut) ...
REMARQUE: POUR TOUS LES POSSESSEURS DE MODIFIER AUTORITÉ. ARRÊTEZ DE JOUER AVEC CE.
Dire que vous avez Rect Un, et Rect B.
Preuve par contradiction. L'un des quatre conditions de garanties que pas de chevauchement peut exister:
- alors A est Totalement à droite De B
- alors A est Totalement à gauche De B
- alors A est Totalement en dessous de B
- alors A est Totalement au-dessus de B
Donc la condition de Non-recouvrement est
Par conséquent, une condition suffisante pour que le Chevauchement est à l'opposé.
De Morgan, la loi dit
Not (A or B or C or D)
est le même queNot A And Not B And Not C And Not D
donc, à l'aide De Morgan, nous avons
Ceci est équivalent à:
RectA.Left < RectB.Right
], etRectA.Right > RectB.Left
], etRectA.Top > RectB.Bottom
], etRectA.Bottom < RectB.Top
]Note 1: Il est assez évident ce même principe peut être étendu à un nombre quelconque de dimensions.
Note 2: Il devrait aussi être assez évident de compter les chevauchements de un pixel, changer la
<
et/ou la>
sur cette limite à un<=
ou un>=
.Note 3: Cette réponse, lors de l'utilisation de coordonnées Cartésiennes (X, Y) est basé sur le standard algébrique des coordonnées Cartésiennes (x augmente de gauche à droite, et Y augmente de bas en haut). Évidemment, où un système informatique peut mécaniser l'écran des coordonnées différemment (par exemple, l'augmentation de Y de haut en bas, ou X De la droite vers la gauche), la syntaxe doit être ajusté en conséquence/
left
,right
,top
,bottom
au lieu de X1, X2, etc.B.height
devrait êtreA.height
#undef min
et#undef max
, ou par l'utilisation de différents noms de paramètre.#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
xOverlap
est dans une dimension;rectOverlap
est en deux dimensions. Il est possible d'étendre à N dimensions à l'aide d'une boucle.Il est plus facile de vérifier si un rectangle est complètement en dehors de l'autre, de sorte que si elle est
sur la gauche...
ou sur la droite...
ou sur le dessus...
ou sur le fond...
de la deuxième rectangle, il ne peut pas entrer en collision avec elle. Afin d'avoir une fonction qui retourne un Booléen disant météo rectangles entrent en collision, il nous suffit de combiner les conditions logiques Rup et réduire à néant le résultat:
Déjà recevoir un résultat positif lors de la toucher seulement, nous pouvons changer le "<" et ">" par "<=" et ">=".
Posez-vous la face de la question: Comment puis-je déterminer si deux rectangles ne se croisent pas à tous? De toute évidence, un rectangle complètement à gauche du rectangle B ne se croisent pas. Aussi, si Un est complètement à droite. Et de même, si Un est complètement au-dessus de B ou complètement en dessous de B. Dans les autres cas A et B se croisent.
Ce qui suit peut avoir des bugs, mais je suis assez confiant sur l'algorithme:
Supposons que vous ayez défini les positions et les dimensions des rectangles comme ceci:
Mon implémentation C++ est comme ceci:
Un exemple d'appel de fonction selon la figure donnée ci-dessus:
Les comparaisons à l'intérieur de la
if
bloc de ressembler à ci-dessous:Voici comment c'est fait dans l'API Java:
Dans la question, vous un lien vers les maths quand les rectangles sont à l'arbitraire des angles de rotation. Si je comprends le peu sur les angles de la question cependant, j'interprète que tous les rectangles sont perpendiculaires l'un à l'autre.
Général sachant que la zone de chevauchement de la formule est:
À l'aide de l'exemple:
1) collecter toutes les coordonnées x (gauche et droite) dans une liste, puis de les trier et supprimer les doublons
2) collecter toutes les coordonnées y (à la fois en haut et en bas) dans une liste, puis de les trier et supprimer les doublons
3) créer un tableau 2D par un certain nombre de lacunes entre la unique les coordonnées x * nombre de lacunes entre la unique y de coordonnées.
4) de la peinture sur tous les rectangles dans cette grille, en augmentant le nombre de chaque cellule, il se produit sur:
5) Que vous peignez les rectangles, son facile à intercepter le chevauche.
Ne pense pas que des coordonnées indiquant où les pixels sont. Pensez à eux comme étant entre les pixels. De cette façon, le domaine de la 2x2 rectangle doit être de 4, pas 9.
Plus simple est
tout d'abord le placez dans votre esprit que dans les ordinateurs, le système de coordonnées est à l'envers. l'axe des x est la même qu'en mathématiques, mais y-axe augmente vers le bas et de la diminution de allez vers le haut..
si rectangle sont établis à partir du centre.
si x1 coordonnées est supérieure à x2 en plus de sa de sa de la moitié de la largeur. ensuite, il faut aller demi-ils toucher les uns les autres. et de la même manière en allant à la baisse + la moitié de sa hauteur. il va entrer en collision..
Permet de dire que les deux rectangles sont Un rectangle et rectangle en B. que les centres A1 et B1 (coordonnées de A1 et B1 peut être facilement trouvé), laissez les hauteurs être Ha et Hb, la largeur sera Wa et Wb, laissez dx être de la largeur(x) la distance entre A1 et B1 et dy être à la hauteur(y) la distance entre A1 et B1.
Nous pouvons dire que maintenant on peut dire que A et B se chevauchent: quand
J'ai implémenté une version C#, il est facilement converti en C++.
J'ai une solution très simple
x1,y1, x2,y2 ,l1,b1,l2,être cordinates et de longueurs et largeurs de respectivement
considérer l'état ((x2
maintenant, la seule manière que ces rectangle de chevauchement est si le point en diagonale par rapport à x1,y1 va se coucher à l'intérieur de l'autre rectangle ou même le point en diagonale par rapport à x2,y2 va se coucher à l'intérieur de l'autre rectangle. ce qui est exactement la condition ci-dessus implique.
A et B deux rectangle. C leur couvrant rectangle.
Il prend soin de tous les cas possibles.
C'est à partir de l'exercice 3.28 du livre Introduction à Java, la Programmation Complète de l'Édition. Le code vérifie si les deux rectangles sont indenticle, si l'on est à l'intérieur de l'autre et que l'on est en dehors de l'autre. Si aucune de ces conditions sont réunies, les deux se superposent.
**3.28 (Géométrie: deux rectangles) Écrire un programme qui demande à l'utilisateur d'entrer le
centre x, y les coordonnées, la largeur et la hauteur de deux rectangles et détermine
si le deuxième rectangle est à l'intérieur de la première ou des chevauchements avec la première, comme le montre
dans la Figure 3.9. Tester votre programme afin de couvrir tous les cas.
Voici l'exemple d'exécution:
Entrer r1 de centre x, y les coordonnées, la largeur et la hauteur: 2.5 4 2.5 43
Entrez r2 de centre x, y les coordonnées, la largeur et la hauteur: 1.5 0.5 3 5
r2 est à l'intérieur r1
Entrer r1 du centre-x-, y-coordonnées, largeur et hauteur: 1 2 3 5.5
Entrez r2 de centre x, y les coordonnées, la largeur et la hauteur: 3 4 4.5 5
r2 chevauche r1
Entrer r1 du centre-x-, y-coordonnées, largeur et hauteur: 1 2 3 3
Entrez r2 de centre x, y les coordonnées, la largeur et la hauteur: 40 45 3 2
r2 ne se chevauchent pas, r1
Pour ceux d'entre vous qui sont à l'aide de points de centre et des demi-tailles pour leurs rectangle de données, au lieu de x,y,w,h, ou x0,y0,x1,x1, voici comment vous pouvez le faire:
Un coup d'oeil à la question à partir d'un autre site.
Le cas avère pour être assez simple si l'on regarde le problème (algorithme) de l'autre côté.
Cela signifie qu'au lieu de répondre à la question: "les rectangles se chevauchent-elles?", nous allons répondre à la question: "Sont les rectangles ne pas se chevauchent?".
En fin de compte, les deux questions à résoudre le même problème, mais la réponse à la deuxième question est plus simple à mettre en œuvre parce que rectangles ne se chevauchent pas seulement lorsque l'on est sous l'autre, ou lorsque l'on est plus à la gauche de l'autre (il suffit que l'un de ces cas, mais bien sûr, il peut arriver que les deux vont se produire simultanément - une bonne compréhension de la logique d'état "ou" est important). Cela réduit le nombre de cas qui doivent être considérées comme agissant de la première question.
Toute la question est aussi simplifiée par l'utilisation de noms de variables:
Même si nous avons une représentation différente d'un rectangle, il est facile d'adapter la fonction ci-dessus pour en modifiant uniquement la section où les changements de variables sont définies. L'autre partie de la fonction reste la même (bien sûr, les commentaires ne sont pas vraiment nécessaire ici, mais j'ai ajouté de sorte que tout le monde puisse comprendre rapidement cet algorithme simple).
Un équivalent mais peut-être un peu moins lisible forme de la fonction ci-dessus peut ressembler à ceci:
"Si vous effectuer la soustraction des coordonnées x ou y correspondant aux sommets des deux en face de chaque rectangle, si les résultats sont du même signe, les deux rectangle ne se chevauchent pas des axes" (je suis désolé, je ne suis pas sûr de ma traduction est correcte)
Source: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Cette réponse doit être la première réponse:
Si les rectangles se chevauchent alors la zone de chevauchement sera plus grand que zéro. Maintenant, laissez-nous trouver la zone de chevauchement:
Si elles se chevauchent, puis le bord gauche de chevauchement-rect sera le
max(r1.x1, r2.x1)
et de droite serontmin(r1.x2, r2.x2)
. De sorte que la longueur du chevauchement seramin(r1.x2, r2.x2) - max(r1.x1, r2.x1)
De sorte que la zone sera:
Si
area = 0
alors qu'ils ne se chevauchent pas.Simple n'est-ce pas?
Code Java pour déterminer si les Rectangles sont communiquant avec ou se chevauchent les uns les autres
...
...