Je cherche un algorithme pour détecter si deux rectangles se croisent (l'un à un angle arbitraire, l'autre avec seulement des lignes verticales / horizontales).
Test si un coin de l'un est dans l'autre ALMOST fonctionne. Il échoue si les rectangles forment une forme en croix.
Il semble judicieux d’éviter d’utiliser les pentes des lignes, ce qui nécessiterait des cas particuliers pour les lignes verticales.
La méthode standard serait de faire la séparation de test de l'axe (faire une recherche google sur que).
En bref:
La chose amusante est, qu'il est suffisant de simplement vérifier tous les bords des deux rectangles. Si les rectangles ne se chevauchent pas l'un des bords seront à la séparation de l'axe.
En 2D, vous pouvez le faire sans l'aide de pentes. Un bord est simplement défini comme la différence entre les deux sommets, par exemple
edge = v(n) - v(n-1)
Vous pouvez obtenir une perpendiculaire à cette par la rotation de 90°. En 2D, c'est facile:
rotated.x = -unrotated.y
rotated.y = unrotated.x
Donc pas de trigonométrie ou des pentes impliqués. Normaliser le vecteur unité de longueur n'est pas nécessaire non plus.
Si vous voulez tester si un point est sur l'un ou l'autre côté de la ligne, vous pouvez simplement utiliser le produit scalaire. le panneau vous indiquera de quel côté vous êtes sur:
// rotated: your rotated edge
// v(n-1) any point from the edge.
// testpoint: the point you want to find out which side it's on.
side = sign (rotated.x * (testpoint.x - v(n-1).x) +
rotated.y * (testpoint.y - v(n-1).y);
Maintenant tester tous les points d'Un rectangle contre les bords du rectangle B et vice versa. Si vous trouvez une séparation de bord, les objets ne coupe pas (en fournissant tous les autres points de B sont de l'autre côté de l'arête en cours d'essai pour voir dessin ci-dessous). Si vous ne trouvez pas de séparation de bord, soit les rectangles sont sécantes ou un rectangle est contenue dans l'autre.
Le test fonctionne avec tous les polygones convexes btw..
Modification: Pour identifier une séparation de bord, il ne suffit pas de tester tous les points d'un rectangle à l'encontre de chaque bord de l'autre. Les candidat-E (ci-dessous), en tant que telle être identifié comme une séparation de bord, car tous les points sont dans le même demi-plan de E. Cependant, il n'est pas une séparation de bord, car les sommets Vb1 et Vb2 de B sont aussi dans ce demi-plan. Il aurait seulement été une séparation de bord si ce n'avait pas été le cas
Fondamentalement, regardez l'image suivante:
Si les deux zones de collision, les lignes A et B se chevauchent.
Notez que cela devra être fait sur les deux axes X et Y, et tous les deux besoin de chevauchement pour les rectangles à entrer en collision.
Il y a un bon article dans gamasutra.com qui répond à la question (la photo de l'article). Je n'ai algorithme similaire il y a 5 ans et je dois trouver mon extrait de code pour poster ici plus tard
Modification: La Séparation de l'Axe Théorème dit que deux formes convexes ne pas se chevauchent si une séparation de l'axe existe (c'est à dire celui où les projections comme indiqué ne pas se chevauchent). Donc, "la séparation de l'axe existe" => "Aucun chevauchement". Ce n'est pas un bi-implication de sorte que vous ne peut pas conclure l'inverse.
Dans le Cacao, vous pouvez facilement détecter si le selectedArea rect croise votre rotation de NSView du cadre rect. Vous n'avez même pas besoin de calculer les polygones, les normales d'un tel. Ajoutez simplement ces méthodes à votre NSView sous-classe. Par exemple, l'utilisateur sélectionne une zone sur la NSView de superview, puis vous appelez la méthode DoesThisRectSelectMe passage de la selectedArea rect. L'API convertRect: va faire ce travail. La même astuce fonctionne lorsque vous cliquez sur le NSView pour le sélectionner. Dans ce cas, tout simplement remplacer la méthode hitTest comme ci-dessous. L'API convertPoint: va le faire ;-)
- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
NSRect localArea = [self convertRect:selectedArea fromView:self.superview];
return NSIntersectsRect(localArea, self.bounds);
}
- (NSView *)hitTest:(NSPoint)aPoint
{
NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
Vérifiez si l'une des lignes d'un rectangle intersecte l'une des lignes de l'autre. L'intersection des segments de ligne naïfs est facile à coder.
Si vous avez besoin de plus de vitesse, il existe des algorithmes avancés pour l'intersection des segments de ligne (ligne de balayage). Voir http://en.wikipedia.org/wiki/Line_segment_intersection
Une solution est d'utiliser quelque chose qui s'appelle un Pas d'Ajustement Polygone. Ce polygone est calculée à partir des deux polygones (sur le plan conceptuel en faisant glisser l'un autour de l'autre) et il définit la zone pour laquelle les polygones se chevauchent en raison de leur relative offset. Une fois que vous avez cette BNL puis il vous suffit de faire un test d'inclusion avec un point donné par le rapport du décalage des deux polygones. Cette inclusion de test est rapide et facile, mais vous n'avez pas à créer de la BNL en premier.
Avoir une recherche pour Aucun Ajustement d'un Polygone sur le web et voir si vous pouvez trouver un algorithme pour les polygones convexes (il devient BEAUCOUP plus complexe si vous avez des polygones concaves). Si vous ne pouvez pas trouver quelque chose, alors écrivez-moi à howard point J dot peut gmail dot com
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
