Comment vérifier efficacement si un point se trouve à l'intérieur d'un rectangle pivoté?

Une partie à des fins d'optimisation, une partie à des fins d'apprentissage, j'oserai demander: comment puis-je vérifier plus efficacement si un point 2D se Ptrouve à l'intérieur d'un rectangle tourné 2D XYZW, en utilisant C # ou C ++?

Actuellement, ce que je fais, c'est utiliser un algorithme "point dans le triangle" trouvé dans le livre Real Time Collision Detection , et l'exécuter deux fois (pour les deux triangles qui composent le rectangle, disons XYZ et XZW):

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2.Dot(v0, v0);
 float dot01 = Vector2.Dot(v0, v1);
 float dot02 = Vector2.Dot(v0, v2);
 float dot11 = Vector2.Dot(v1, v1);
 float dot12 = Vector2.Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

Cependant, j'ai le sentiment qu'il pourrait y avoir un moyen plus propre et plus rapide. Plus précisément, pour réduire le nombre d'opérations mathématiques.

Une optimisation simple et directe consisterait à modifier la condition finale dans PointInTriangle:

bool PointInRectangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P) {
  ...
  if(u >= 0 && v >= 0 && u <= 1 && v <= 1)
      { return true; } else { return false; }
  }
}

le code était à peu près PointInRectangledéjà, la condition (u + v) < 1était là pour vérifier s'il n'était pas dans le "deuxième" triangle de rectangle.

Alternativement, vous pouvez également faire un isLeft(premier exemple de code sur la page, également largement expliqué) tester quatre fois, et vérifier qu'ils renvoient tous des résultats avec le même signe (dont l'un dépend si les points ont été donnés dans le sens horaire ou antihoraire) pour le point d'être à l'intérieur. Cela fonctionne également pour tout autre polygone convexe.

float isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) );
}
bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
    return (isLeft(X, Y, P) > 0 && isLeft(Y, Z, P) > 0 && isLeft(Z, W, P) > 0 && isLeft(W, X, p) > 0);
}

Modifier: Le commentaire OP a été sceptique quant à l'efficacité de la vérification de la limite circulaire négative suggérée pour améliorer l'algorithme afin de vérifier si un point 2D arbitraire se trouve dans un rectangle tourné et / ou en mouvement. Je bidouille un peu sur mon moteur de jeu 2D (OpenGL / C ++), je complète ma réponse en fournissant une référence de performance de mon algorithme par rapport aux algorithmes (et variantes) de vérification de point dans le rectangle actuels des OP.

J'ai initialement suggéré de laisser l'algorithme en place (car il est presque optimal), mais de simplifier par une simple logique de jeu: (1) en utilisant un cercle prétraité autour du rectangle d'origine; (2) faire une vérification de distance et si le point se trouve dans le cercle donné; (3) utiliser les OP ou tout autre algorithme simple (je recommande l'algorithme isLeft comme indiqué dans une autre réponse). La logique derrière ma suggestion est que vérifier si un point se trouve dans un cercle est considérablement plus efficace qu'une vérification des limites d'un rectangle tourné ou de tout autre polygone.

Mon scénario initial pour un test de référence consiste à exécuter un grand nombre de points apparaissant et disparaissant (dont la position change dans chaque boucle de jeu) dans un espace contraint qui sera rempli d'environ 20 carrés rotatifs / mobiles. J'ai publié une vidéo ( lien youtube ) à des fins d'illustration. Remarquez les paramètres: nombre de points apparaissant au hasard, nombre ou rectangles. Je comparerai les paramètres suivants:

OFF : algorithme simple fourni par l'OP sans vérification négative des limites du cercle

ON : Utilisation de cercles (limites) par-traités autour des rectangles comme première vérification d'exclusion

ON + Stack : création de limites de cercle au moment de l'exécution dans la boucle de la pile

ON + Distance carrée : Utiliser les distances carrées comme une optimisation supplémentaire pour éviter de prendre l'algorithme de racine carrée plus cher (Pieter Geerkens).

Voici un résumé des différentes performances des différents algorithmes en montrant le temps qu'il faut pour parcourir la boucle.

L'axe des x montre une complexité accrue en ajoutant plus de points (et donc en ralentissant la boucle). (Par exemple, à 1000 points apparaissant au hasard dans un espace confié avec 20 rectangles, la boucle itère et appelle l'algorithme 20000 fois.) L'axe des y montre le temps qu'il faut (ms) pour terminer la boucle entière en utilisant une haute résolution minuterie de performance. Plus de 20 ms serait problématique pour un jeu décent car il ne profiterait pas des fps élevés pour interpoler une animation fluide et le jeu peut parfois apparaître comme "robuste".

Résultat 1 : un algorithme lié circulaire pré-traité avec un contrôle négatif rapide dans la boucle améliore les performances de 1900% par rapport à l'algorithme normal (5% du temps de boucle d'origine sans contrôle). Le résultat est approximativement proportionnel au nombre d'itérations dans une boucle, donc peu importe si nous vérifions 10 ou 10 000 points apparaissant au hasard. Ainsi, dans cette illustration, on peut augmenter le nombre d'objets en toute sécurité à 10k sans ressentir une perte de performances.

Résultat 2 : Il a été suggéré par un commentaire précédent que l'algorithme peut être plus rapide mais gourmand en mémoire. Cependant, notez que le stockage d'un flottant pour la taille du cercle prétraité ne prend que 4 octets. Cela ne devrait poser aucun problème réel, sauf si l'OP prévoit d'exécuter simultanément plus de 100 000 objets. Une approche alternative et efficace en mémoire consiste à calculer la taille maximale du cercle sur la pile dans la boucle et à la laisser hors de portée à chaque itération et donc à n'avoir pratiquement aucune utilisation de la mémoire pour un prix de vitesse inconnu. En effet, le résultat montre que cette approche est en effet plus lente que l'utilisation d'une taille de cercle prétraitée, mais elle montre tout de même une amélioration considérable des performances de l'ordre de 1150% (soit 8% du temps de traitement d'origine).

Résultat 3 : J'améliore encore l'algorithme du résultat 1 en utilisant des distances au carré au lieu des distances réelles et en prenant ainsi une opération de racine carrée coûteuse en calcul. Cela n'augmente que légèrement les performances (2400%). (Remarque: j'essaie également des tables de hachage pour des tableaux prétraités pour des approximations de racines carrées avec un résultat similaire mais légèrement pire)

Résultat 4 : Je vérifie en outre le déplacement / collision des rectangles autour; cependant, cela ne change pas les résultats de base (comme prévu) car la vérification logique reste essentiellement la même.

Résultat 5 : je fais varier le nombre de rectangles et je trouve que l'algorithme devient encore plus efficace moins l'espace est rempli (non montré dans la démo). Le résultat est également quelque peu attendu, car la probabilité qu'un point apparaisse dans un espace minuscule entre un cercle et les limites de l'objet diminue. À l'autre extrême, j'essaie d'augmenter le nombre de rectangles trop 100 dans le même petit espace confiné ET de les faire varier dynamiquement en taille au moment de l'exécution à l'intérieur de la boucle (sin (itérateur)). Cela fonctionne toujours très bien avec une augmentation des performances de 570% (ou 15% du temps de boucle d'origine).

Résultat 6 : Je teste des algorithmes alternatifs suggérés ici et découvre une différence de performance très légère mais non significative (2%). L'algorithme IsLeft intéressant et plus simple fonctionne très bien avec une augmentation des performances de 17% (85% du temps de calcul d'origine) mais loin de l'efficacité d'un algorithme de contrôle négatif rapide.

Mon point est de considérer d'abord la conception allégée et la logique de jeu, en particulier lorsqu'il s'agit de frontières et d'événements de collision. L'algorithme actuel des OP est déjà assez efficace et une nouvelle optimisation n'est pas aussi critique que l'optimisation du concept sous-jacent lui-même. De plus, il est bon de communiquer la portée et le but du jeu, car l'efficacité d'un algorithme en dépend de manière critique.

Je suggère de toujours essayer de comparer n'importe quel algorithme complexe pendant la phase de conception du jeu car le simple fait de regarder le code simple peut ne pas révéler la vérité sur les performances d'exécution réelles. L'algorithme proposé peut ne pas être ici même nécessaire, si, par exemple, on souhaite simplement tester si le curseur de la souris se trouve dans un rectangle ou non, ou, lorsque la majorité des objets se touchent déjà. Si la majorité des vérifications de points se trouvent dans le rectangle, l'algorithme sera moins efficace. (Cependant, il serait alors possible d'établir une limite de `` cercle intérieur '' comme contrôle négatif secondaire.) Les contrôles de limite de cercle / sphère sont très utiles pour toute détection de collision décente d'un grand nombre d'objets qui ont naturellement un espace entre eux. .

Rec Points  Iter    OFF     ON     ON_Stack     ON_SqrDist  Ileft Algorithm (Wondra)
            (ms)    (ms)    (ms)    (ms)        (ms)        (ms)
20  10      200     0.29    0.02    0.04        0.02        0.17
20  100     2000    2.23    0.10    0.20        0.09        1.69
20  1000    20000   24.48   1.25    1.99        1.05        16.95
20  10000   200000  243.85  12.54   19.61       10.85       160.58

La définition d'un rectangle à 4 points permet de réaliser un trapèze. Si toutefois, vous le définissiez par x, y, largeur, hauteur et une rotation autour de son milieu, vous pourriez simplement faire pivoter le point que vous vérifiez par la rotation inverse de votre rectangle (autour de la même origine), puis vérifier s'il est dans le rectangle d'origine.

Je n'ai pas eu le temps de comparer cela, mais ma suggestion serait de stocker la matrice de transformation qui transforme le rectangle en carré aligné sur l'axe dans la plage x et y de 0 à 1. En d'autres termes, stocker la matrice qui transforme un coin du rectangle en (0,0) et l'autre en (1,1).

Cela serait bien sûr plus cher si le rectangle est déplacé beaucoup et que la collision est vérifiée assez rarement, mais s'il y a beaucoup plus de vérifications que de mises à jour du rectangle, ce serait au moins plus rapide que l'approche initiale de test contre deux triangles, car les six produits scalaires seraient remplacés par une multiplication matricielle.

Mais comme toujours, la vitesse de cet algorithme dépend beaucoup du type de contrôles que vous prévoyez d'effectuer. Si la plupart des points ne sont même pas proches du rectangle, une simple vérification de distance (par exemple (point.x - firstCorner.x)> aLargeDistance) peut entraîner une grande accélération, alors qu'elle peut même ralentir les choses si presque tout les points sont à l'intérieur du rectangle.

EDIT: Voici à quoi ressemblerait ma classe Rectangle:

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

Voici la liste complète de mon benchmark:

#include <cstdlib>
#include <math.h>
#include <iostream>

#include <sys/time.h>

using namespace std;

class Vector2
{
public:
    float _x;
    float _y;

    Vector2()
    :_x(0)
    ,_y(0)
    {}

    Vector2(float p_x, float p_y)
        : _x (p_x)
        , _y (p_y)
        {}

    Vector2 operator-(const Vector2& p_other) const
    {
        return Vector2(_x-p_other._x, _y-p_other._y);
    }

    Vector2 operator+(const Vector2& p_other) const
    {
        return Vector2(_x+p_other._x, _y+p_other._y);
    }

    Vector2 operator*(float p_factor) const
    {
        return Vector2(_x*p_factor, _y*p_factor);
    }

    static float Dot(Vector2 p_a, Vector2 p_b)
    {
        return (p_a._x*p_b._x + p_a._y*p_b._y);
    }
};

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2::Dot(v0, v0);
 float dot01 = Vector2::Dot(v0, v1);
 float dot02 = Vector2::Dot(v0, v2);
 float dot11 = Vector2::Dot(v1, v1);
 float dot12 = Vector2::Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

class Matrix3x3
{
public:
    Vector2 _columns[3];

    Vector2 transform(Vector2 p_in)
    {
        return _columns[0] * p_in._x + _columns[1] * p_in._y + _columns[2];
    }
};

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

void runTest(float& outA, float& outB)
{
    Rectangle r;
    r.setCorners(Vector2(0,0.5), Vector2(0.5,1), Vector2(0.5,0));

    int numTests = 10000;

    Vector2 points[numTests];

    Vector2 cornerA[numTests];
    Vector2 cornerB[numTests];
    Vector2 cornerC[numTests];
    Vector2 cornerD[numTests];

    bool results[numTests];
    bool resultsB[numTests];

    for (int i=0; i<numTests; ++i)
    {
        points[i]._x = rand() / ((float)RAND_MAX);
        points[i]._y = rand() / ((float)RAND_MAX);

        cornerA[i]._x = rand() / ((float)RAND_MAX);
        cornerA[i]._y = rand() / ((float)RAND_MAX);

        Vector2 edgeA;
        edgeA._x = rand() / ((float)RAND_MAX);
        edgeA._y = rand() / ((float)RAND_MAX);

        Vector2 edgeB;
        edgeB._x = rand() / ((float)RAND_MAX);
        edgeB._y = rand() / ((float)RAND_MAX);

        cornerB[i] = cornerA[i] + edgeA;
        cornerC[i] = cornerA[i] + edgeB;
        cornerD[i] = cornerA[i] + edgeA + edgeB;
    }

    struct timeval start, end;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        r.setCorners(cornerA[i], cornerB[i], cornerC[i]);
        results[i] = r.isInside(points[i]);
    }
    gettimeofday(&end, NULL);
    float elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outA += elapsed;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        resultsB[i] = PointInRectangle(cornerA[i], cornerB[i], cornerC[i], cornerD[i], points[i]);
    }
    gettimeofday(&end, NULL);
    elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outB += elapsed;
}

/*
 * 
 */
int main(int argc, char** argv) 
{
    float a = 0;
    float b = 0;

    for (int i=0; i<5000; i++)
    {
        runTest(a, b);
    }

    std::cout << "Result: " << a << " / " << b << std::endl;

    return 0;
}

Le code n'est certainement pas beau, mais je ne vois pas immédiatement de bugs majeurs. Avec ce code, j'obtiens des résultats qui indiquent que ma solution est environ deux fois plus rapide si le rectangle est déplacé entre chaque vérification. S'il ne bouge pas, mon code semble être plus de cinq fois plus rapide.

Si vous savez comment le code va être utilisé, vous pouvez même l'accélérer un peu plus en séparant la transformation et les contrôles dans les deux dimensions. Par exemple, dans un jeu de course, il serait probablement plus rapide de vérifier d'abord les coordonnées qui pointent dans la direction de la conduite, car de nombreux obstacles seront devant ou derrière la voiture, mais presque aucun ne sera à droite ou à gauche.