Wie überprüfe ich effizient, ob sich ein Punkt innerhalb eines gedrehten Rechtecks ​​befindet?

11

Zum Teil zur Optimierung, zum Teil zu Lernzwecken möchte ich fragen: Wie kann ich mit C # oder C ++ am effizientesten überprüfen, ob sich ein 2D-Punkt Pinnerhalb eines gedrehten 2D-Rechtecks XYZWbefindet?

Derzeit verwende ich einen "Punkt im Dreieck" -Algorithmus aus dem Buch " Echtzeit-Kollisionserkennung" und führe ihn zweimal aus (für die beiden Dreiecke, aus denen das Rechteck besteht, z. B. XYZ und 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;
}

Ich habe jedoch das Gefühl, dass es einen saubereren und schnelleren Weg geben könnte. Insbesondere, um die Anzahl der mathematischen Operationen zu reduzieren.

Louis15
quelle
Haben Sie viele Punkte oder haben Sie viele Rechtecke? Das ist die erste Frage, die Sie sich stellen sollten, bevor Sie versuchen, eine so kleine Aufgabe zu optimieren.
Sam Hocevar
Guter Punkt. Ich werde eine sehr hohe Anzahl von Punkten haben, aber noch mehr Rechtecke zu überprüfen.
Louis15
Verwandte Frage zum Ermitteln des Abstands eines Punkts zu einem gedrehten Rechteck . Dies ist ein entarteter Fall davon (nur prüfen, ob der Abstand 0 ist). Natürlich wird es hier Optimierungen geben, die dort nicht zutreffen.
Anko
Haben Sie darüber nachgedacht, den Punkt in den Referenzrahmen des Rechtecks ​​zu drehen?
Richard Tingle
@ RichardTingle Eigentlich habe ich am Anfang nicht. Später habe ich das getan, weil ich denke, dass dies mit einer der unten angegebenen Antworten zusammenhängt. Aber nur um zu verdeutlichen: In dem, was Sie vorschlagen, sollte man nach dem Drehen des Punkts zum Referenzrahmen des Rechtecks ​​die Aufnahme nur durch logische Vergleiche zwischen max.x, min.x usw. überprüfen.
Louis15

Antworten:

2

Eine einfache und unkomplizierte Optimierung wäre, die Endbedingung zu ändern in 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; }
  }
}

Der Code war so ziemlich PointInRectangleschon da, die Bedingung (u + v) < 1war da, um zu überprüfen, ob er nicht im "zweiten" Dreieck des Rechtecks ​​ist.

Alternativ können Sie auch isLeftviermal einen Test (erstes Codebeispiel auf Seite, ebenfalls ausführlich erklärt) durchführen und überprüfen, ob alle Ergebnisse mit demselben Vorzeichen (das davon abhängt, ob die Punkte im oder gegen den Uhrzeigersinn angegeben wurden) für zurückgegeben werden der Punkt, drinnen zu sein. Dies funktioniert auch für jedes andere konvexe Polygon.

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
quelle
Hervorragend. Ich weiß nicht, ob ich Ihren Vorschlag mehr mag, der wirklich schneller und viel eleganter ist als meiner, oder ob ich mehr mag, dass Sie bemerkt haben, dass mein PointInTri-Code leicht zu einem PointInRec werden könnte! Vielen Dank
Louis15
+1 für die isLeftMethode. Es erfordert keine Triggerfunktionen (wie Vector2.Dotauch), was die Dinge sehr beschleunigt.
Anko
Übrigens, konnte der Code nicht optimiert werden (nicht getestet; nicht wie in diesem Computer), indem isLeft direkt in die Hauptfunktion aufgenommen und die Operatoren "&&" durch "||" ersetzt wurden. durch die umgekehrte Logik? 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 Ich glaube nicht, dass du das musst - sowohl && als auch || stoppt die Ausführung weiterer Anweisungen, wenn ein Negativ / Positiv gefunden wurde (oder gab es einen anderen Grund?). Wenn Sie isLeftden Compiler als Inline deklarieren, wird dies etwas Ähnliches für Sie tun (und wahrscheinlich besser als Sie es könnten, da die Ingenieure, die den Compiler geschrieben haben, die CPUs am besten kannten und die am schnellsten verfügbare Option auswählten), wodurch Ihr Code mit gleichem oder besserem Effekt besser lesbar wird.
Wondra
8

Bearbeiten: Der Kommentar des OP war skeptisch hinsichtlich der Effizienz der vorgeschlagenen Prüfung der negativen Kreisgrenze zur Verbesserung des Algorithmus, um zu prüfen, ob ein beliebiger 2D-Punkt innerhalb eines gedrehten und / oder sich bewegenden Rechtecks ​​liegt. Ich fummele ein bisschen an meiner 2D-Game-Engine (OpenGL / C ++) herum und ergänze meine Antwort, indem ich einen Leistungsbenchmark meines Algorithmus gegen die aktuellen Point-in-Rectangle-Check-Algorithmen (und Variationen) des OP gebe.

Ich habe ursprünglich vorgeschlagen, den Algorithmus beizubehalten (da er nahezu optimal ist), aber durch bloße Spielelogik zu vereinfachen: (1) Verwenden eines vorverarbeiteten Kreises um das ursprüngliche Rechteck; (2) eine Entfernungsprüfung durchführen und ob der Punkt innerhalb des gegebenen Kreises liegt; (3) Verwenden Sie die OPs oder einen anderen einfachen Algorithmus (ich empfehle den isLeft-Algorithmus, wie in einer anderen Antwort angegeben). Die Logik hinter meinem Vorschlag ist, dass die Überprüfung, ob sich ein Punkt innerhalb eines Kreises befindet, erheblich effizienter ist als die Grenzprüfung eines gedrehten Rechtecks ​​oder eines anderen Polygons.

Mein erstes Szenario für einen Benchmark-Test besteht darin, eine große Anzahl von erscheinenden und verschwindenden Punkten (deren Position sich in jeder Spielschleife ändert) in einem begrenzten Raum auszuführen, der mit etwa 20 rotierenden / sich bewegenden Quadraten gefüllt wird. Ich habe ein Video ( Youtube-Link ) zur Veranschaulichung veröffentlicht. Beachten Sie die Parameter: Anzahl der zufällig erscheinenden Punkte, Anzahl oder Rechtecke. Ich werde mit den folgenden Parametern vergleichen:

AUS : Einfacher Algorithmus, wie er vom OP ohne negative Prüfung der Kreisgrenze bereitgestellt wird

EIN : Verwenden von pro-verarbeiteten (Grenz-) Kreisen um die Rechtecke als erste Ausschlussprüfung

EIN + Stapel : Erstellen von Kreisgrenzen zur Laufzeit innerhalb der Schleife auf dem Stapel

ON + Quadratabstand : Verwenden Sie Quadratabstände als weitere Optimierung, um den teureren Quadratwurzelalgorithmus (Pieter Geerkens) zu vermeiden.

Hier finden Sie eine Zusammenfassung der verschiedenen Leistungen verschiedener Algorithmen, indem die Zeit angezeigt wird, die zum Durchlaufen der Schleife erforderlich ist.

Geben Sie hier die Bildbeschreibung ein

Die x-Achse zeigt eine erhöhte Komplexität, indem mehr Punkte hinzugefügt werden (und somit die Schleife verlangsamt wird). (Bei 1000 zufällig erscheinenden Punktprüfungen in einem vertrauten Raum mit 20 Rechtecken iteriert die Schleife und ruft den Algorithmus 20000 Mal auf.) Die y-Achse zeigt die Zeit (ms), die benötigt wird, um die gesamte Schleife mit einer hohen Auflösung abzuschließen Leistungs-Timer. Mehr als 20 ms wären für ein anständiges Spiel problematisch, da es die hohen fps nicht nutzen würde, um eine reibungslose Animation zu interpolieren, und das Spiel manchmal so "robust" erscheinen könnte.

Ergebnis 1 : Ein vorverarbeiteter zirkular gebundener Algorithmus mit einer schnellen negativen Prüfung innerhalb der Schleife verbessert die Leistung um 1900% im Vergleich zum regulären Algorithmus (5% der ursprünglichen Schleifenzeit ohne Prüfung). Das Ergebnis ist ungefähr proportional zur Anzahl der Iterationen innerhalb einer Schleife. Daher spielt es keine Rolle, ob wir 10 oder 10000 zufällig erscheinende Punkte überprüfen. Somit kann man in dieser Abbildung die Anzahl der Objekte sicher auf 10.000 erhöhen, ohne einen Leistungsverlust zu spüren.

Ergebnis 2 : In einem früheren Kommentar wurde vorgeschlagen, dass der Algorithmus möglicherweise schneller, aber speicherintensiv ist. Beachten Sie jedoch, dass das Speichern eines Floats für die vorverarbeitete Kreisgröße nur 4 Byte dauert. Dies sollte kein wirkliches Problem darstellen, es sei denn, das OP plant, mehr als 100000 Objekte gleichzeitig auszuführen. Ein alternativer und speichereffizienter Ansatz besteht darin, die maximale Größe des Kreises auf dem Stapel innerhalb der Schleife zu berechnen und ihn bei jeder Iteration aus dem Gültigkeitsbereich zu entfernen, sodass für einen unbekannten Geschwindigkeitspreis praktisch kein Speicher belegt wird. Das Ergebnis zeigt zwar, dass dieser Ansatz zwar langsamer ist als die Verwendung einer vorverarbeiteten Kreisgröße, zeigt jedoch immer noch eine erhebliche Leistungsverbesserung von etwa 1150% (dh 8% der ursprünglichen Verarbeitungszeit).

Ergebnis 3 : Ich verbessere den Algorithmus für Ergebnis 1 weiter, indem ich quadratische Abstände anstelle tatsächlicher Abstände verwende und somit eine rechenintensive Quadratwurzeloperation durchführe. Dies steigert die Leistung nur geringfügig (2400%). (Hinweis: Ich versuche auch Hash-Tabellen für vorverarbeitete Arrays für Quadratwurzel-Näherungen mit einem ähnlichen, aber etwas schlechteren Ergebnis.)

Ergebnis 4 : Ich überprüfe weiter, ob die Rechtecke bewegt / kollidiert werden. Dies ändert jedoch nicht die grundlegenden Ergebnisse (wie erwartet), da die logische Prüfung im Wesentlichen gleich bleibt.

Ergebnis 5 : Ich verändere die Anzahl der Rechtecke und stelle fest, dass der Algorithmus umso effizienter wird, je weniger Platz der Raum belegt ist (in der Demo nicht gezeigt). Das Ergebnis wird auch etwas erwartet, da die Wahrscheinlichkeit abnimmt, dass ein Punkt innerhalb eines winzigen Raums zwischen einem Kreis und den Objektgrenzen erscheint. Auf der anderen Seite versuche ich, die Anzahl der Rechtecke innerhalb desselben begrenzten Raums auf 100 zu erhöhen UND sie zur Laufzeit innerhalb der Schleife (sin (Iterator)) dynamisch zu variieren. Dies funktioniert immer noch sehr gut mit einer Leistungssteigerung um 570% (oder 15% der ursprünglichen Schleifenzeit).

Ergebnis 6 : Ich teste die hier vorgeschlagenen alternativen Algorithmen und finde einen sehr geringen, aber nicht signifikanten Leistungsunterschied (2%). Der interessante und einfachere IsLeft-Algorithmus bietet eine sehr gute Leistung mit einer Leistungssteigerung von 17% (85% der ursprünglichen Berechnungszeit), aber bei weitem nicht die Effizienz eines schnellen Negativprüfungsalgorithmus.

Mein Punkt ist, zuerst Lean Design und Spielelogik zu betrachten, insbesondere wenn es um Grenzen und Kollisionsereignisse geht. Der aktuelle Algorithmus des OP ist bereits ziemlich effizient und eine weitere Optimierung ist nicht so kritisch wie die Optimierung des zugrunde liegenden Konzepts. Darüber hinaus ist es gut, den Umfang und den Zweck des Spiels zu kommunizieren, da die Effizienz eines Algorithmus entscheidend von ihnen abhängt.

Ich schlage vor, immer zu versuchen, einen komplexen Algorithmus während der Spieldesignphase zu bewerten, da ein bloßer Blick auf den einfachen Code möglicherweise nicht die Wahrheit über die tatsächliche Laufzeitleistung preisgibt. Der vorgeschlagene Algorithmus ist hier möglicherweise nicht einmal erforderlich, wenn beispielsweise lediglich getestet werden soll, ob der Mauszeiger innerhalb eines Rechtecks ​​liegt oder nicht, oder wenn sich die meisten Objekte bereits berühren. Wenn sich die meisten Punkteprüfungen innerhalb des Rechtecks ​​befinden, ist der Algorithmus weniger effizient. (Dann wäre es jedoch möglich, eine 'innere Kreis'-Grenze als sekundäre negative Prüfung festzulegen.) Kreis- / Kugelgrenzprüfungen sind sehr nützlich für jede anständige Kollisionserkennung einer großen Anzahl von Objekten, zwischen denen natürlich etwas Platz ist .

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
quelle
Obwohl ich den ungewöhnlichen Ansatz mochte und die Da Vinci-Referenz liebte, denke ich nicht, dass der Umgang mit Kreisen, geschweige denn mit dem Radius, so effizient wäre.
Diese
Die Position des Rechtecks ​​muss nicht festgelegt werden. Verwenden Sie relative Koordinaten. Denken Sie auch so darüber nach. Dieser Radius bleibt unabhängig von der Drehung gleich.
Majte
Dies ist eine großartige Antwort. Besser noch, weil ich nicht daran gedacht hatte. Möglicherweise möchten Sie beachten, dass es ausreicht, die quadratischen Abstände anstelle der tatsächlichen Abstände zu verwenden, um zu vermeiden, dass jemals eine Quadratwurzel berechnet werden muss.
Pieter Geerkens
Interessanter Algorithmus für schnelle positive / negative Tests! Das Problem könnte zusätzlicher Speicher sein, um vorverarbeitete Begrenzungskreise (und Breiten) zu speichern. Es könnte eine gute Heuristik sein, aber auch eine begrenzte Verwendung haben - meistens in Fällen, in denen der Speicher keine große Rolle spielt (Rechtecke mit statischer Größe bei größeren Objekten = Sprite-Spielobjekte). und Zeit zum Vorverarbeiten haben.
Wondra
Bearbeitet + Benchmark-Test hinzugefügt.
Majte
2

Das Definieren eines Rechtecks ​​mit 4 Punkten ermöglicht das Erstellen eines Trapezes. Wenn Sie es jedoch durch x, y, Breite, Höhe und eine Drehung um seine Mitte definieren würden, könnten Sie den zu überprüfenden Punkt einfach durch die umgekehrte Drehung Ihres Rechtecks ​​(um denselben Ursprung) drehen und dann prüfen, ob dies der Fall ist im ursprünglichen Rechteck.

Peethor
quelle
Hmm, danke für den Vorschlag, aber das Drehen und Erhalten der umgekehrten Drehung scheint nicht so effizient zu sein. In der Tat wird es kaum so effizient sein wie meine Lösung - ganz zu schweigen von Wondra
Louis15
Sie können feststellen, dass das Drehen eines 3D-Punkts mit einer Matrix 6 Multiplikationen und 3 Additionen sowie einen Funktionsaufruf umfasst. Die Lösung von @ wondra ist bestenfalls gleichwertig, aber in ihrer Absicht viel weniger klar. und anfälliger für Wartungsfehler durch Verletzung von DRY
Pieter Geerkens
@Pieter Geerkens übergreifende Behauptung, wie verstößt eine meiner Lösungen gegen DRY (und ist DRY eines der wichtigsten Programmierprinzipien? Bis jetzt noch nie davon gehört)? Und vor allem, welche Fehler haben diese Lösungen? Immer bereit zu lernen.
Wondra
@wondra: DRY = Wiederhole dich nicht. Ihr Code-Snippet schlägt vor, die Details einer Matrix durch Vektormultiplikation überall dort zu codieren, wo die Funktionalität im Code erscheint, anstatt eine Standardmethode für die Anwendung von Matrix auf Vektor aufzurufen.
Pieter Geerkens
@PieterGeerkens schlägt natürlich nur einen Teil davon vor - 1) Sie haben keine explizite Matrix (das Zuweisen einer neuen Matrix für jede Abfrage würde die Leistung stark beeinträchtigen) 2) Ich verwende nur einen bestimmten Multiplikationsfall, der für diesen Fall optimiert ist und das Aufblähen von Generika beseitigt eins. Es handelt sich um einen Betrieb auf niedriger Ebene, der eingekapselt bleiben sollte, um unerwartetes Verhalten zu verhindern.
Wondra
1

Ich hatte keine Zeit, dies zu bewerten, aber mein Vorschlag wäre, die Transformationsmatrix, die das Rechteck in das achsenausgerichtete Quadrat transformiert, im x- und y-Bereich von 0 bis 1 zu speichern. Mit anderen Worten, speichern Sie die Matrix, die das Rechteck ausrichtet transformiert eine Ecke des Rechtecks ​​in (0,0) und die gegenüberliegende in (1,1).

Dies wäre natürlich teurer, wenn das Rechteck viel bewegt und die Kollision eher selten überprüft wird. Wenn jedoch viel mehr Überprüfungen als Aktualisierungen des Rechtecks ​​vorgenommen werden, wäre dies zumindest schneller als der ursprüngliche Ansatz zum Testen gegen zwei Dreiecke. da die sechs Punktprodukte durch eine Matrixmultiplikation ersetzt würden.

Aber wie immer hängt die Geschwindigkeit dieses Algorithmus stark von der Art der Überprüfungen ab, die Sie erwarten. Wenn sich die meisten Punkte nicht einmal in der Nähe des Rechtecks ​​befinden und eine einfache Abstandsprüfung durchführen (z. B. (point.x - firstCorner.x)> aLargeDistance), kann dies zu einer starken Beschleunigung führen, während die Geschwindigkeit sogar verlangsamt wird, wenn fast alle Die Punkte befinden sich innerhalb des Rechtecks.

EDIT: So würde meine Rectangle-Klasse aussehen:

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);
    }
};

Dies ist die vollständige Auflistung meiner 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;
}

Der Code ist sicherlich nicht schön, aber ich sehe nicht sofort größere Fehler. Mit diesem Code erhalte ich Ergebnisse, die darauf hinweisen, dass meine Lösung etwa doppelt so schnell ist, wenn das Rechteck zwischen den einzelnen Prüfungen verschoben wird. Wenn es sich nicht bewegt, scheint mein Code mehr als fünfmal schneller zu sein.

Wenn Sie wissen, wie der Code verwendet wird, können Sie ihn sogar noch etwas beschleunigen, indem Sie die Transformation und die Prüfungen in zwei Dimensionen aufteilen. Zum Beispiel wäre es in einem Rennspiel wahrscheinlich schneller, zuerst die Koordinate zu überprüfen, die in Fahrtrichtung zeigt, da sich viele Hindernisse vor oder hinter dem Auto befinden, aber kaum eines rechts oder links davon.

Lars Kokemohr
quelle
Interessant, aber vergessen Sie nicht, dass Sie die Matrixrotation auch auf die Punkte anwenden müssen. Ich habe eine Matrix-Rot-Operation in meiner Gameengine und kann Ihren Algorithmus später bewerten. In Bezug auf Ihren letzten Kommentar. Dann können Sie auch einen 'inneren Kreis' definieren lassen und doppelt negativ prüfen, ob der Punkt außerhalb des inneren Kreises und innerhalb des Außenkreises liegt, wie oben beschrieben.
Majte
Ja, das wäre hilfreich, wenn Sie erwarten, dass sich die meisten Punkte nahe der Mitte des Dreiecks befinden. Ich stellte mir eine Situation wie eine rechteckige Rennstrecke vor, in der Sie beispielsweise einen rechteckigen Pfad definieren, indem Sie ein äußeres Rechteck verwenden, in dem der Charakter bleiben muss, und ein kleineres inneres Rechteck, aus dem er herausbleiben muss. In diesem Fall würde sich jede Prüfung nahe am Rand des Rechtecks ​​befinden, und diese Kreisprüfungen würden wahrscheinlich nur die Leistung verschlechtern. Zugegeben, das ist ein konstruiertes Beispiel, aber ich würde sagen, es ist etwas, das tatsächlich passieren könnte.
Lars Kokemohr
Solche Dinge können passieren, ja. Ich frage mich, was der Sweet Spot ist, um sich gegen den Algorithmus zu wenden. Am Ende läuft es auf Ihren Zweck hinaus. Wenn Sie Zeit haben, können Sie Ihren Code mithilfe des OP-Beitrags veröffentlichen und ich kann Ihren Algorithmus bewerten? Mal sehen, ob deine Intuition stimmt. Ich bin gespannt auf die Leistung Ihrer Idee gegen den IsLeft-Algorithmus.
Majte