Jak skutecznie sprawdzić, czy punkt znajduje się w obróconym prostokącie?

Część ze względu na optymalizację, część w celach edukacyjnych, odważę się zapytać: jak mogę najskuteczniej sprawdzić, czy punkt 2D Pznajduje się w obróconym prostokącie 2D XYZW, używając C # lub C ++?

Obecnie używam algorytmu „punkt w trójkącie” znalezionego w książce Wykrywanie kolizji w czasie rzeczywistym i uruchamiam go dwukrotnie (dla dwóch trójkątów tworzących prostokąt, powiedzmy XYZ i 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;
}

Mam jednak wrażenie, że może istnieć czystszy i szybszy sposób. W szczególności, aby zmniejszyć liczbę operacji matematycznych.

Łatwą i bezpośrednią optymalizacją byłaby zmiana ostatecznego warunku w 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; }
  }
}

kod został dość dużo PointInRectanglejuż, warunek (u + v) < 1był tam, aby sprawdzić, czy nie ma w „drugi” trójkąt prostokąt.

Alternatywnie, możesz również wykonać isLeftczterokrotnie test (pierwszy przykład kodu na stronie, również doskonale wyjaśniony) i sprawdzić, czy wszystkie zwracają wyniki z tym samym znakiem (który zależy od tego, czy punkty zostały podane w kolejności zgodnej z ruchem wskazówek zegara, czy przeciwnie do wskazówek zegara) dla punkt, aby być w środku. Działa to również w przypadku każdego innego wypukłego wielokąta.

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

Edycja: Komentarz POs sceptycznie odnosi się do skuteczności sugerowanego ujemnego testu kołysania w celu ulepszenia algorytmu w celu sprawdzenia, czy dowolny punkt 2D znajduje się w obróconym i / lub ruchomym prostokącie. Bawiąc się trochę w moim silniku gier 2D (OpenGL / C ++), uzupełniam moją odpowiedź, dostarczając test porównawczy wydajności mojego algorytmu w stosunku do obecnych algorytmów sprawdzania punktu i prostokątów OP (i odmian).

Początkowo zasugerowałem pozostawienie algorytmu na miejscu (ponieważ jest on prawie optymalny), ale uproszczenie poprzez samą logikę gry: (1) używając wstępnie przetworzonego okręgu wokół oryginalnego prostokąta; (2) wykonaj kontrolę odległości i czy punkt leży w danym okręgu; (3) użyj OP lub innego prostego algorytmu (zalecam algorytm isLeft podany w innej odpowiedzi). Logika, na której opiera się moja sugestia, polega na tym, że sprawdzenie, czy punkt znajduje się w okręgu jest znacznie wydajniejsze niż sprawdzenie granicy obróconego prostokąta lub dowolnego innego wielokąta.

Mój początkowy scenariusz testu porównawczego polega na uruchomieniu dużej liczby pojawiających się i znikających kropek (których pozycja zmienia się w każdej pętli gry) w ograniczonej przestrzeni, która zostanie wypełniona około 20 obracającymi się / ruchomymi kwadratami. Opublikowałem film ( link do youtube ) w celach ilustracyjnych. Zwróć uwagę na parametry: liczbę losowo pojawiających się kropek, liczbę lub prostokąty. Przeprowadzę testy porównawcze z następującymi parametrami:

WYŁ : Prosty algorytm dostarczony przez PO bez kontroli ujemnych na granicy okręgu

WŁ . : Używanie okręgów przetworzonych (granicznych) wokół prostokątów jako pierwszej kontroli wykluczenia

ON + Stack : Tworzenie granic okręgu w czasie wykonywania w pętli na stosie

ON + Dystans kwadratowy: Wykorzystanie odległości kwadratowych jako dodatkowej optymalizacji, aby uniknąć stosowania droższego algorytmu pierwiastka kwadratowego (Pieter Geerkens).

Oto podsumowanie różnych wydajności różnych algorytmów, pokazujące czas potrzebny na iterację w pętli.

Oś X pokazuje zwiększoną złożoność poprzez dodanie większej liczby kropek (a tym samym spowolnienie pętli). (Na przykład przy 1000 losowo pojawiających się punktach sprawdza się w przestrzeni zwierzeń z 20 prostokątami, pętla iteruje i wywołuje algorytm 20000 razy.) Oś y pokazuje czas (ms) ukończenia całej pętli przy użyciu wysokiej rozdzielczości licznik wydajności. Więcej niż 20 ms byłoby problematyczne dla przyzwoitej gry, ponieważ nie skorzystałby z wysokiej liczby klatek na sekundę do interpolacji płynnej animacji, a gra może czasami wydawać się „trudna”.

Wynik 1 : Wstępnie przetworzony algorytm związany z kołem z szybką kontrolą ujemną w pętli poprawia wydajność o 1900% w porównaniu do zwykłego algorytmu (5% pierwotnego czasu pętli bez kontroli). Wynik jest w przybliżeniu proporcjonalny do liczby iteracji w pętli, dlatego nie ma znaczenia, czy sprawdzimy 10 lub 10000 losowo pojawiających się punktów. Zatem na tej ilustracji można bezpiecznie zwiększyć liczbę obiektów do 10k bez odczuwania utraty wydajności.

Wynik 2 : W poprzednim komentarzu zasugerowano, że algorytm może być szybszy, ale wymaga dużej ilości pamięci. Pamiętaj jednak, że przechowywanie liczby zmiennoprzecinkowej dla wstępnie przetworzonego rozmiaru okręgu zajmuje zaledwie 4 bajty. Nie powinno to stanowić prawdziwego problemu, chyba że PO planuje uruchomić jednocześnie ponad 100 000 obiektów. Alternatywnym i efektywnym podejściem do pamięci jest obliczenie maksymalnego rozmiaru okręgu na stosie w pętli i pozostawienie go poza zakresem przy każdej iteracji, a tym samym praktycznie bez użycia pamięci dla nieznanej ceny prędkości. Rzeczywiście wynik pokazuje, że to podejście jest rzeczywiście wolniejsze niż użycie wstępnie przetworzonego rozmiaru koła, ale nadal wykazuje znaczną poprawę wydajności o około 1150% (tj. 8% pierwotnego czasu przetwarzania).

Wynik 3 : Ulepszam algorytm wyniku 1, używając kwadratowych odległości zamiast rzeczywistych odległości i tym samym podejmując kosztownie obliczeniową operację pierwiastka kwadratowego. To tylko nieznacznie zwiększa wydajność (2400%). (Uwaga: wypróbowuję również tabele skrótów dla wstępnie przetworzonych tablic dla przybliżeń pierwiastków kwadratowych z podobnym, ale nieco gorszym wynikiem)

Wynik 4 : Dalej sprawdzam przesuwanie / zderzanie prostokątów; nie zmienia to jednak podstawowych wyników (zgodnie z oczekiwaniami), ponieważ kontrola logiczna pozostaje zasadniczo taka sama.

Rezultat 5 : Zmieniam liczbę prostokątów i stwierdzam, że algorytm staje się jeszcze bardziej wydajny, im mniej miejsca jest wypełnione (nie pokazano w wersji demo). Wynik jest również nieco oczekiwany, ponieważ prawdopodobieństwo maleje, gdy punkt pojawi się w niewielkiej przestrzeni między okręgiem a granicami obiektu. Z drugiej strony staram się zwiększyć liczbę prostokątów o zbyt 100 w tej samej ograniczonej przestrzeni ORAZ zmieniać ich dynamicznie rozmiar w czasie wykonywania w pętli (sin (iterator)). Nadal działa to wyjątkowo dobrze ze wzrostem wydajności o 570% (lub 15% pierwotnego czasu pętli).

Wynik 6 : Testuję zaproponowane tutaj alternatywne algorytmy i znajduję bardzo niewielką, ale nie znaczącą różnicę w wydajności (2%). Interesujący i prostszy algorytm IsLeft działa bardzo dobrze ze wzrostem wydajności o 17% (85% pierwotnego czasu obliczeń), ale nigdzie blisko wydajności algorytmu szybkiego testu negatywnego.

Chodzi mi przede wszystkim o rozważenie szczupłego projektowania i logiki gry, szczególnie w przypadku granic i zdarzeń kolizyjnych. Obecny algorytm PO jest już dość wydajny, a dalsza optymalizacja nie jest tak istotna jak optymalizacja samej koncepcji. Ponadto dobrze jest przekazać zakres i cel gry, ponieważ wydajność algorytmu zależy od nich krytycznie.

Sugeruję, aby zawsze próbować przeprowadzić analizę porównawczą dowolnego złożonego algorytmu na etapie projektowania gry, ponieważ samo spojrzenie na prosty kod może nie ujawnić prawdy o rzeczywistej wydajności w czasie wykonywania. Sugerowany algorytm może nie być tutaj nawet potrzebny, jeśli na przykład chcemy po prostu przetestować, czy kursor myszy znajduje się w prostokącie, czy też nie, lub gdy większość obiektów już się dotyka. Jeśli większość punktów jest w prostokącie, algorytm będzie mniej wydajny. (Jednak wówczas możliwe byłoby ustanowienie granicy „wewnętrznego koła” jako dodatkowej kontroli ujemnej.) Kontrole granicy koła / kuli są bardzo przydatne do każdego przyzwoitego wykrywania kolizji dużej liczby obiektów, które mają naturalnie trochę przestrzeni między nimi .

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

Zdefiniowanie prostokąta z 4 punktami umożliwia utworzenie trapezu. Jeśli jednak zdefiniujesz go za pomocą x, y, szerokości, wysokości i obrotu wokół jego środka, możesz po prostu obrócić sprawdzany punkt przez odwrócenie obrotu prostokąta (wokół tego samego początku), a następnie sprawdzić, czy jest to w oryginalnym prostokącie.

Nie miałem czasu na testowanie tego, ale moją sugestią byłoby przechowywanie macierzy transformacji, która przekształca prostokąt w kwadrat wyrównany do osi w zakresie x i y od 0 do 1. Innymi słowy, przechowuj macierz, która przekształca jeden narożnik prostokąta w (0,0), a przeciwny narożnik w (1,1).

Byłoby to oczywiście droższe, gdyby prostokąt był często przesuwany, a kolizja jest sprawdzana raczej rzadko, ale jeśli jest o wiele więcej kontroli niż aktualizacji prostokąta, byłoby to co najmniej szybsze niż pierwotne podejście do testowania dwóch trójkątów, ponieważ produkty sześciu kropek zostaną zastąpione jednym pomnożeniem macierzy.

Ale jak zawsze szybkość tego algorytmu zależy w dużej mierze od rodzaju kontroli, których się spodziewasz. Jeśli większość punktów nie znajduje się nawet blisko prostokąta, wykonanie prostej kontroli odległości (np. (Point.x - firstCorner.x)> aLargeDistance) może spowodować duże przyspieszenie, a nawet może spowolnić, jeśli prawie wszystkie punkty znajdują się w prostokącie.

EDYCJA: Tak wyglądałaby moja klasa 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);
    }
};

Oto pełna lista mojego testu porównawczego:

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

Kod z pewnością nie jest piękny, ale nie widzę od razu żadnych większych błędów. Dzięki temu kodowi otrzymuję wyniki, które wskazują, że moje rozwiązanie jest około dwa razy szybsze, jeśli prostokąt jest przenoszony między każdym czekiem. Jeśli się nie porusza, mój kod wydaje się ponad pięć razy szybszy.

Jeśli wiesz, w jaki sposób będzie używany kod, możesz go nawet przyspieszyć, oddzielając transformację i kontrole w dwóch wymiarach. Na przykład w grze wyścigowej prawdopodobnie szybciej byłoby sprawdzić współrzędną, która wskazuje kierunek jazdy, ponieważ wiele przeszkód będzie przed lub za samochodem, ale prawie żadna nie będzie po prawej ani lewej stronie.