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

11

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.

Louis15
la source
Avez-vous de nombreux points ou avez-vous de nombreux rectangles? C'est la première question que vous devez vous poser avant d'essayer d'optimiser une si petite tâche.
sam hocevar
Bon point. J'aurai un très grand nombre de points, mais encore plus de rectangles à vérifier.
Louis15
Question connexe sur la recherche de la distance d'un point à un rectangle pivoté . C'est un cas dégénéré de cela (vérifier uniquement lorsque la distance est 0). Bien sûr, il y aura des optimisations qui s'appliquent ici qui ne sont pas là.
Anko
Avez-vous envisagé de faire pivoter le point dans le cadre de référence du rectangle?
Richard Tingle
@RichardTingle En fait, je ne l'ai pas fait au début. Plus tard, je l'ai fait, car je pense que cela se rapporte à l'une des réponses données ci-dessous. Mais juste pour clarifier: dans ce que vous proposez, après avoir tourné le point vers le cadre de référence des rectangles, alors il faut vérifier l'inclusion juste par des comparaisons logiques entre max.x, min.x, etc.?
Louis15

Réponses:

2

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);
}
Wondra
la source
Superbe. Je ne sais pas si j'aime plus votre suggestion, qui est vraiment plus rapide et beaucoup plus élégante que la mienne, ou si j'aime plus que vous avez remarqué que mon code PointInTri pourrait facilement devenir un PointInRec! Merci
Louis15
+1 pour la isLeftméthode. Il ne nécessite pas de fonctions trigonométriques (comme c'est le Vector2.Dotcas), ce qui accélère beaucoup les choses.
Anko
Au fait, le code n'a-t-il pas pu être modifié (n'a pas testé; ne sait pas comment dans cet ordinateur), en incluant isLeft directement dans la fonction principale, et en remplaçant les opérateurs "&&" par "||" à travers la logique inverse? public static bool PointInRectangle(Vector2 P, Vector2 X, Vector2 Y, Vector2 Z, Vector2 W) { return !(( (Y.x - X.x) * (P.y - X.y) - (P.x - X.x) * (Y.y - X.y) ) < 0 || ( (Z.x - Y.x) * (P.y - Y.y) - (P.x - Y.x) * (Z.y - Y.y) ) < 0 || ( (W.x - Z.x) * (P.y - Z.y) - (P.x - Z.x) * (W.y - Z.y) ) < 0 || ( (X.x - W.x) * (P.y - W.y) - (P.x - W.x) * (X.y - W.y) ) < 0 ); }
Louis15
1
@ Louis15 Je ne pense pas que vous en ayez besoin - à la fois && et || arrêtera d'exécuter d'autres déclarations si un négatif / positif a été trouvé (ou y avait-il une autre raison?). Déclarer isLeften ligne que le compilateur fera quelque chose de similaire pour vous (et probablement mieux que vous le pourriez, car les ingénieurs qui écrivent le compilateur connaissaient le mieux les CPU, en choisissant l'option la plus rapide) rendant votre code plus lisible avec un effet identique ou meilleur.
wondra
8

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.

entrez la description de l'image ici

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
Majte
la source
Bien que j'aimais l'approche inhabituelle et que j'aimais la référence Da Vinci, je ne pense pas que traiter les cercles, sans parler du rayon, serait aussi efficace. De plus, cette solution n'est raisonnable que si tous les rectangles sont fixes et connus à l'avance
Louis15
La position du rectangle n'a pas besoin d'être fixée. Utilisez des coordonnées relatives. Pensez-y aussi comme ça. Ce rayon reste le même, quelle que soit la rotation.
Majte
C'est une excellente réponse; mieux encore parce que je n'y avais pas pensé. Vous voudrez peut-être noter qu'il suffit d'utiliser les distances au carré à la place des distances réelles, ce qui évite d'avoir à calculer une racine carrée.
Pieter Geerkens
Algorithme intéressant pour des tests positifs / négatifs rapides! Le problème pourrait être de la mémoire supplémentaire pour enregistrer les cercles de délimitation prétraités (et les largeurs), cela pourrait être une bonne heuristique, mais notez également qu'il a une utilisation limitée - surtout pour les cas où la mémoire n'a pas beaucoup d'importance (rectangles de taille statique sur les objets plus gros = objets de jeu de sprites) et avoir le temps de prétraiter.
Wondra
Test de référence modifié et ajouté.
Majte du
2

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.

Peethor
la source
Hmm, merci pour la suggestion, mais tourner et obtenir la rotation inverse ne semble pas si efficace. En fait, ce ne sera pas aussi efficace que ma solution - sans parler des merveilles
Louis15
Vous pourriez noter que la rotation d'un point 3D avec une matrice équivaut à 6 multiplications et 3 additions, et un appel de fonction. La solution de @ wondra est au mieux équivalente, mais beaucoup moins claire dans son intention; et plus sensibles aux erreurs de maintenance en violant DRY
Pieter Geerkens
@Pieter Geerkens affirmation croisée, comment l'une de mes solutions viole-t-elle DRY (et est-ce que DRY est l'un des principes de programmation clés? Je n'en ai jamais entendu parler jusqu'à présent)? Et surtout, quelles erreurs ces solutions contiennent-elles? Toujours prêt à apprendre.
Wondra
@wondra: DRY = Ne vous répétez pas. Votre extrait de code suggère de coder les détails d'une matrice par multiplication vectorielle partout où cette fonctionnalité apparaît dans le code au lieu d'invoquer une méthode standard d'application de matrice à vecteur.
Pieter Geerkens du
@PieterGeerkens, bien sûr, il ne suggère qu'une partie de celui-ci - 1) vous n'avez pas de matrice explicitement (l'allocation d'une nouvelle matrice pour chaque requête affecterait les performances) 2) J'utilise uniquement un cas de multiplication spécifique, optimisé pour ce cas, laissant tomber le ballet du générique une. Il s'agit d'un fonctionnement de bas niveau et il doit rester encapsulé pour éviter tout comportement inattendu.
Wondra
1

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.

Lars Kokemohr
la source
Intéressant, mais n'oubliez pas que vous devez également appliquer la rotation de la matrice sur les points. J'ai une opération de pourriture matricielle dans mon moteur de jeu et je peux comparer votre algorithme plus tard. En ce qui concerne votre dernier commentaire. Ensuite, vous pouvez également définir un «cercle intérieur» et faire un double contrôle négatif si le point se trouve à l'extérieur du cercle intérieur et à l'intérieur du cercle extérieur, comme décrit ci-dessus.
Majte
Oui, cela aiderait si vous vous attendez à ce que la plupart des points soient proches du milieu du triangle. J'imaginais une situation comme une piste de course rectangulaire où vous définissez par exemple un chemin rectangulaire en utilisant un rectangle extérieur dans lequel le personnage doit rester à l'intérieur et un rectangle intérieur plus petit dans lequel il doit rester en dehors. Dans ce cas, chaque vérification serait proche de la bordure du rectangle et ces vérifications en cercle ne feraient probablement qu'empirer les performances. Certes, c'est un exemple construit, mais je dirais que c'est quelque chose qui pourrait réellement se produire.
Lars Kokemohr du
Des choses comme ça peuvent arriver, oui. Je me demande quel est le point idéal pour se retourner contre l'algorithme. À la fin, cela se résume à votre objectif. Si vous avez le temps, pouvez-vous publier votre code, en utilisant la publication OP et je peux comparer votre algorithme? Voyons voir si votre intuition est bonne. Je suis curieux de connaître les performances de votre idée par rapport à l'algorithme IsLeft.
Majte du