Quel est le moyen le plus rapide de calculer l'intersection de la boîte de sélection 2D?

62

Supposons que chaque objet Box ait les propriétés x, y, largeur, hauteur et qu’il ait son origine au centre, et que ni les objets ni les cadres ne tournent.

Iain
la source
S'agit-il de boîtes de contour d'axe ou d'objet?
mardi
3
Lorsque vous posez cette question, vous devrez sûrement tester d’autres types d’intersections à l’avenir;). C'est pourquoi je suggère LA LISTE concernant l'intersection Objet / Objet. Le tableau fournit des intersections entre tous les types d'objets courants (boîtes, sphères, triangles, cyclinders, cônes, ...) dans des situations statiques et dynamiques.
Dave O.
2
S'il vous plaît reformulez votre question à des liens contraignants. De mon point de vue boîte implique un objet 3d.
Dave O.

Réponses:

55

(Pseudocode C-ish - adapte les optimisations de langage selon les besoins)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

En anglais: Sur chaque axe, vérifiez si les centres des cases sont suffisamment proches pour qu’ils se croisent. S'ils se croisent sur les deux axes, les cases se croisent. S'ils ne le font pas, alors ils ne le font pas.

Vous pouvez remplacer les <par <= si vous voulez que les retombées sur les bords s'entrecroisent. Si vous souhaitez une formule spécifique au toucher uniquement sur les bords, vous ne pouvez pas utiliser == - cela vous dira si les coins se touchent, pas si les bords se touchent. Vous voudriez faire quelque chose logiquement équivalent à return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Il est à noter que vous pouvez obtenir une augmentation de vitesse faible mais significative en stockant la demi-largeur et la demi-hauteur en plus de (ou à la place de) la pleine largeur et la pleine hauteur. Par contre, il est rare que l’intersection du cadre de sélection 2D soit le goulot d’étranglement lié aux performances.

ZorbaTHut
la source
9
Cela suppose évidemment que les cases sont alignées sur les axes.
mardi
1
Les abdominaux ne devraient pas être particulièrement lents - pas plus lentement qu'un conditionnel, du moins, et le seul moyen de le faire sans abdominaux (dont je suis au courant) implique des conditionnels supplémentaires.
ZorbaTHut
4
Oui, cela suppose des cases alignées sur les axes. Les structures telles que décrites ne disposent d'aucun moyen d'indiquer la rotation, alors j'ai pensé que c'était sûr.
ZorbaTHut
3
Voici quelques conseils utiles pour accélérer les calculs dans Actionscript (principalement des calculs entiers): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math Je publie ce message, car il contient également une valeur plus rapide. remplacement de Math.abs (), ce qui a tendance à ralentir les choses dans Actionscript (en parlant de performances critiques bien sûr).
Bummzack
2
Vous manquez qu'ils ont l'origine au centre, pas au bord gauche. Une boîte qui va de 0 à 10 aura réellement "x = 5", alors qu'une boîte qui va de 8 à 12 aura "x = 10". Vous vous retrouvez avec abs(5 - 10) * 2 < (10 + 4)=> 10 < 14. Vous aurez besoin de faire quelques ajustements simples afin de le faire fonctionner avec topleft-corner-size-size.
ZorbaTHut
37

Cela fonctionne pour deux rectangles alignés avec les axes X et Y.
Chaque rectangle a les propriétés suivantes:
"gauche", la coordonnée x de son côté gauche,
"haut", la coordonnée y de son côté supérieur,
"droite", la coordonnée x de son côté droit,
"bas", la coordonnée y de sa face inférieure,

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

Notez que ceci est conçu pour un système de coordonnées dans lequel l'axe + y pointe vers le bas et l'axe + x est dirigé vers la droite (c'est-à-dire les coordonnées écran / pixels typiques). Pour adapter cela à un système cartésien typique dans lequel + y est dirigé vers le haut, les comparaisons sur les axes verticaux seraient inversées, par exemple:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

L'idée est de capturer toutes les conditions possibles dans lesquelles les rectangles ne se chevauchent pas , puis d'annuler la réponse pour voir si elles se chevauchent. Quelle que soit la direction des axes, il est facile de voir que deux rectangles ne se chevauchent pas si:

  • le bord gauche de r2 est plus à droite que le bord droit de r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
    
  • ou le bord droit de r2 est plus à gauche que le bord gauche de r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
    
  • ou le bord supérieur de r2 est en dessous du bord inférieur de r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
    
  • ou le bord inférieur de r2 est au-dessus du bord supérieur de r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|
    

La fonction d'origine - et une description alternative de son fonctionnement - est disponible à l' adresse suivante : http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- chacun-autre-ou-pas /

Ponkadoodle
la source
1
Étonnamment intuitif, il montre une fois de plus que, lorsque trouver la réponse est trop difficile, essayer de trouver la réponse à une question opposée peut vous aider. Merci!
Lodewijk
1
Vous devez mentionner que l’axe des y pointe vers le bas (comme dans une image). Sinon, les inégalités r2.top> r1.bottom et r2.bottom <r1.top doivent être inversées.
user1443778
@ user1443778 bonne prise! Je suis allé de l'avant et j'ai vaguement expliqué la logique de cet algorithme d'une manière agnostique par rapport aux systèmes de coordonnées.
Ponkadoodle
11

Si vous souhaitez des boîtes englobantes alignées sur l’objet, essayez ce didacticiel sur le théorème de l’axe de séparation par Metanet: http://www.metanetsoftware.com/technique/tutorialA.html.

SAT n'est pas la solution la plus rapide, mais c'est relativement simple. Vous essayez de trouver une seule ligne (ou un plan si 3D) qui séparera vos objets. Si cette ligne existe, il est garanti d'être parallèle au bord de l'une de vos boîtes. Vous parcourez donc tous les bords en testant si elle sépare les boîtes.

Cela fonctionne également pour les boîtes alignées sur les axes en se limitant à l'axe x / y.

tenpn
la source
Je ne pensais pas à la rotation, mais merci c'est un lien intéressant.
Iain
5

La DoBoxesIntersect ci-dessus est une bonne solution par paire. Cependant, si vous avez beaucoup de boîtes, vous avez toujours un problème O (N ^ 2) et vous pouvez être amené à faire quelque chose de plus comme Kaj. (Dans la littérature sur la détection de collision en 3D, cela s'appelle avoir un algorithme à phase large et à phase étroite. Nous allons faire quelque chose de très rapide pour trouver toutes les paires de chevauchements possibles, puis quelque chose de plus coûteux pour voir si notre possible les paires sont des paires réelles.)

L'algorithme à phase large que j'ai utilisé auparavant est "balayage complet"; pour la 2D, vous devez conserver deux listes triées du début et de la fin de chaque zone. Tant que le mouvement de la boîte n'est pas >> échelle d'une boîte d'une image à l'autre, l'ordre de ces listes ne changera pas beaucoup et vous pouvez donc utiliser le tri par bulle ou par insertion pour le conserver. Le livre "Real-Time Rendering" propose une bonne rédaction sur les optimisations que vous pouvez faire, mais il se résume à un temps O (N + K) dans la phase large, pour N cases, dont K se chevauchent, et avec une excellente situation réelle Si vous avez les moyens de payer N ^ 2 booléens, gardez une trace des paires de boîtes qui se croisent d’une image à l’autre. Vous avez alors un temps global O (N + K ^ 2), qui est << O (N ^ 2) si vous avez beaucoup de cases mais seulement quelques chevauchements.

Tom Hudson
la source
5

Beaucoup de maths ici pour un problème très simple, supposons que nous avons 4 points déterminés pour un rect, en haut, à gauche, en bas, à droite ...

Pour déterminer si 2 phénomènes entrent en collision, il suffit de regarder tous les extrêmes possibles qui empêcheraient les collisions. Si aucun de ces éléments n'est respecté, les 2 phénomènes DOIVENT entrer en collision. Si vous souhaitez inclure les collisions de frontière, remplacez simplement les touches> et <. avec approprié> = et = <.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
utilisateur35189
la source
Honnêtement, je ne sais pas trop pourquoi cette réponse n’est pas la plus votée. C'est simple, correct et efficace.
3Dave
3

Autre version de la réponse de ZorbaTHut:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}
Iain
la source
En fait, cette arithmétique fonctionne très bien dans un cas Vous pouvez faire n'importe quelle opération arithmétique de part et d'autre du <et cela ne la change pas (la multiplication par un négatif signifie que vous devez changer le moins que, cependant). Dans cet exemple, les boîtes ne doivent pas entrer en collision. Si le centre de la case A est à 1, il s'étend de -4 à 6. La case b est centrée à 7,5 et de 7,5 à 12,5, il n'y a pas de collision là-bas ... La méthode affichée par Wallacoloo est non seulement correcte, mais fonctionnera plus vite sur les langues qui implémentent le court-circuit, puisque la plupart des vérifications retournent de toute façon fausse, le court-circuit peut se couper après
Deleter
Oui, je m'en suis rendu compte quand je me suis réveillé ce matin. Chris m'a accompagné de son <> confusion.
Iain
1
Deux problèmes: premièrement, la division a tendance à être beaucoup plus lente que la multiplication. Deuxièmement, si les valeurs impliquées sont des entiers, cela peut entraîner des problèmes de troncature d’entiers (ax = 0, bx = 9, a.width = 9, b.width = 10: abs (0-9) <(9 + 10) / 2, 9 <19/2, 9 <9, la fonction retourne la valeur false malgré le fait que les cases se croisent définitivement.)
ZorbaTHut le
2

En fonction du problème que vous essayez de résoudre, il peut être préférable de garder la trace de votre objet pendant que vous le déplacez, c'est-à-dire de garder une liste de x positions de début et de fin triées et d'une liste pour les positions de début et de fin y. Si vous devez faire BEAUCOUP de contrôles de chevauchement et que vous devez par conséquent optimiser, vous pouvez utiliser ceci à votre avantage, car vous pouvez immédiatement rechercher qui se termine près de votre gauche, toutes les personnes se terminant à gauche pouvant être élaguées immédiatement. Il en va de même pour le haut, le bas et la droite.
La comptabilité coûte du temps bien sûr, elle convient donc mieux à une situation avec peu d’objets en mouvement mais beaucoup de vérifications de chevauchement.
Une autre option est le hachage spatial, où vous répartissez les objets en fonction de leur position approximative (la taille peut les placer dans plusieurs compartiments), mais là encore, uniquement s’il existe un grand nombre d’objets, dont relativement peu se déplaçant par itération en raison du coût de la comptabilité.
Fondamentalement, tout ce qui évite (n * n) / 2 (si vous vérifiez l’objet a contre b, vous n’aurez pas à vérifier b contre a évidemment) est plus utile que l’optimisation des vérifications du cadre de sélection. Si les vérifications dans les cadres de sélection constituent un goulet d'étranglement, je conseillerais sérieusement de rechercher des solutions alternatives au problème.

Kaj
la source
2

La distance entre les centres n'est pas la même que la distance entre les coins (quand une case est dans une autre, par exemple), donc EN GÉNÉRAL, cette solution est la bonne (me semble-t-il).

distance entre les centres (par exemple x): abs(x1+1/2*w1 - x2+1/2*w2)ou1/2 * abs(2*(x1-x2)+(w1-w2)

La distance minimale est 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). les moitiés annulent donc ..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));
Vladimir Dizhoor
la source
1
Qu'y a-t-il dans la déclaration "return"?
doppelgreener
1

Voici mon implémentation en Java en supposant une architecture à deux-complément . Si vous n'êtes pas sur deux-complément, utilisez plutôt un appel de fonction Math.abs standard :

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

En supposant qu'un compilateur / LLVM en ligne semi-décent développe ces fonctions pour éviter les jongleries de pile et les comparaisons coûteuses de la pile. Cela échouera pour les valeurs d'entrée proches des extrêmes 32 bits (c'est Integer.MAX_VALUE-à- dire et Integer.MIN_VALUE).

MadMartian
la source
0

Le moyen le plus rapide est de combiner les 4 valeurs dans un seul registre vectoriel.

Stockez les cases dans un vecteur avec les valeurs suivantes [ min.x, min.y, -max.x, -max.y ]. Si vous stockez des boîtes de ce type, le test d'intersection ne prend que 3 instructions de la CPU:

_mm_shuffle_ps pour réorganiser la deuxième boîte en retournant les moitiés min et max.

_mm_xor_psavec nombre magique _mm_set1_ps(-0.0f)pour retourner les signes de toutes les 4 valeurs dans la deuxième case.

_mm_cmple_ps pour comparer les 4 valeurs entre elles, en comparant les deux registres suivants:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Enfin, si nécessaire, _mm_movemask_psobtenir le résultat de l’unité vectorielle dans un registre scalaire. La valeur 0 signifie les cases intersectées. Ou, si vous avez plus de 2 boîtes, cela n'est pas nécessaire, laissez les valeurs dans les registres de vecteurs et utilisez des opérations au niveau des bits pour combiner les résultats de plusieurs boîtes.

Vous n'avez pas spécifié de langue ni de plate-forme, mais le support de SIMD comme celui-ci, ou très similaire, est disponible dans toutes les plates-formes et langues. Sur mobile, ARM utilise NEON SIMD avec des éléments très similaires. .NET a Vector128 dans l'espace de noms System.Runtime.Intrinsics, et ainsi de suite.

Soonts
la source