Jaki jest najszybszy sposób opracowania przecięcia obwiedni 2D?

Załóżmy, że każdy obiekt ramki ma właściwości x, y, szerokość, wysokość i ma swój początek w środku, i że ani obiekty, ani obwiednia nie obracają się.

(Pseudokod C-ish - odpowiednio dostosuj optymalizacje języka)

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

W języku angielskim: Na każdej osi sprawdź, czy środki pól są wystarczająco blisko, aby się przecinały. Jeśli przecinają się na obu osiach, to przecinają się pola. Jeśli nie, to nie.

Możesz zmienić <na <=, jeśli chcesz liczyć dotykanie krawędzi jako przecinające się. Jeśli potrzebujesz konkretnej formuły dotykającej tylko krawędzi, nie możesz użyć == - to powie ci, czy rogi się stykają, a nie jeśli się stykają. Chciałbyś zrobić coś logicznie równoważnego return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Warto wspomnieć, że można uzyskać niewielki, ale znaczący wzrost prędkości, przechowując połowę szerokości i połowę wysokości oprócz (lub zamiast) pełnej szerokości i pełnej wysokości. Z drugiej strony przecięcie 2d ramki ograniczającej jest wąskim gardłem wydajności.

Działa to dla dwóch prostokątów wyrównanych z osią X i Y.
Każdy prostokąt ma właściwości:
„lewy”, współrzędna x jego lewej strony,
„góra”, współrzędna y jego górnej strony,
„prawa”, współrzędna x jego prawej strony,
„dół”, współrzędna y jego dolna strona,

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

Zauważ, że jest to zaprojektowane dla układu współrzędnych, w którym oś + y jest skierowana w dół, a oś + x jest skierowana w prawo (tj. Typowe współrzędne ekranu / piksela). Aby dostosować to do typowego systemu kartezjańskiego, w którym + y jest skierowane do góry, porównania wzdłuż osi pionowych zostałyby odwrócone, np .:

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

Chodzi o to, aby uchwycić wszystkie możliwe warunki, w których prostokąty się nie nakładają, a następnie zanegować odpowiedź, aby sprawdzić, czy się pokrywają. Bez względu na kierunek osi łatwo zauważyć, że dwa prostokąty nie zachodzą na siebie, jeśli:

• lewa krawędź r2 znajduje się dalej w prawo niż prawa krawędź r1

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

• lub prawa krawędź r2 jest bardziej lewa niż lewa krawędź r1

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

• lub górna krawędź r2 znajduje się poniżej dolnej krawędzi r1

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

• lub dolna krawędź r2 znajduje się powyżej górnej krawędzi r1

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

Oryginalną funkcję - i alternatywny opis jej działania - można znaleźć tutaj: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- siebie nawzajem lub nie /

Jeśli chcesz obwiedni wyrównanych obiektowo, wypróbuj ten samouczek na temat twierdzenia o osi rozdzielania autorstwa metanetu: http://www.metanetsoftware.com/technique/tutorialA.html

SAT nie jest najszybszym rozwiązaniem, ale jest stosunkowo prosty. Próbujesz znaleźć pojedynczą linię (lub płaszczyznę, jeśli 3D), która rozdzieli twoje obiekty. Jeśli ta linia istnieje, to prawdopodobnie jest równoległa do krawędzi jednego z twoich pudełek, więc iterujesz wszystkie testy krawędzi, aby sprawdzić, czy oddziela pudełka.

Działa to również w przypadku pól wyrównanych do osi poprzez ograniczenie tylko do osi x / y.

Powyższe DoBoxesIntersect jest dobrym rozwiązaniem dla par. Jednakże, jeśli masz dużo pudełek, nadal masz problem z O (N ^ 2) i może się okazać, że musisz zrobić coś więcej niż to, o czym mówi Kaj. (W literaturze dotyczącej wykrywania kolizji 3D jest to znane jako algorytm szerokofazowy i wąskofazowy. Zrobimy coś naprawdę szybko, aby znaleźć wszystkie możliwe pary nakładających się na siebie, a następnie coś droższego, aby sprawdzić, czy nasze możliwe pary są rzeczywistymi parami).

Algorytmem wielofazowym, którego użyłem wcześniej, jest „zamiatanie i przycinanie”; dla 2D zachowałbyś dwie posortowane listy początku i końca każdego pola. Dopóki ruch ramki nie jest >> przeskalowaniem ramki od ramki do ramki, kolejność tych list nie zmieni się zbyt wiele, więc możesz użyć sortowania bąbelkowego lub wstawiania, aby go utrzymać. Książka „Rendering w czasie rzeczywistym” ma ładny opis optymalizacji, które możesz zrobić, ale sprowadza się do czasu O (N + K) w szerokiej fazie, dla N-boxów, z których K zachodzi na siebie, i z doskonałym realnym światem wydajność, jeśli stać Cię na booleany N ^ 2, aby śledzić, które pary pól przecinają się klatka po klatce. Następnie masz całkowity czas O (N + K ^ 2), który wynosi << O (N ^ 2), jeśli masz wiele pól, ale tylko kilka zakładek.

Dużo matematyki dla bardzo prostego problemu, załóżmy, że mamy wyznaczone 4 punkty dla prostego, górnego, lewego, dolnego, prawego ...

W przypadku ustalenia, czy zderzają się 2 prostokąty, wystarczy spojrzeć tylko na to, że wszystkie możliwe skrajności, które zapobiegłyby kolizjom, jeśli żadna z nich nie zostanie spełniona, to 2 prostki MUSZĄ zderzyć się, jeśli chcesz uwzględnić kolizje graniczne, po prostu zamień> i < z odpowiednimi> = i = <.

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

Alternatywna wersja odpowiedzi 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);
}

W zależności od problemu, który próbujesz rozwiązać, lepiej jest śledzić obiekt podczas przenoszenia, tj. Przechowywać listę posortowanych x pozycji początkowej i końcowej oraz jedną pozycję początkową i końcową. Jeśli musisz wykonać wiele nakładających się kontroli i dlatego musisz zoptymalizować, możesz to wykorzystać na swoją korzyść, ponieważ możesz od razu sprawdzić, kto kończy się po twojej lewej stronie, każdy, kto kończy się po lewej, może zostać przycięty natychmiast. To samo dotyczy górnego, dolnego i prawego.
Księgowość kosztuje oczywiście czas, więc bardziej nadaje się do sytuacji, w której kilka ruchomych obiektów ma wiele nakładających się kontroli.
Inną opcją jest haszowanie przestrzenne, w którym obiekty są grupowane w oparciu o przybliżoną pozycję (rozmiar może umieścić je w wielu segmentach), ale tam znowu, tylko jeśli jest dużo obiektów, a stosunkowo niewiele z nich porusza się na iterację z powodu kosztów księgowych.
Zasadniczo wszystko, co pozwala uniknąć (n * n) / 2 (jeśli zaznaczysz obiekt a względem b, nie będziesz musiał oczywiście sprawdzać b względem oczywistego), pomaga to bardziej niż optymalizacja sprawdzania obwiedni. Jeśli kontrole pola ograniczającego są wąskim gardłem, poważnie radzę poszukać alternatywnych rozwiązań tego problemu.

Odległość między środkami nie jest taka sama, jak odległość między narożnikami (gdy na przykład jedno pudełko znajduje się w drugim), więc OGÓLNIE to rozwiązanie jest prawidłowe (myślę).

odległość między środkami (na przykład x): abs(x1+1/2*w1 - x2+1/2*w2)lub1/2 * abs(2*(x1-x2)+(w1-w2)

Minimalna odległość wynosi 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). połówki anulują się, więc ..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));

Oto moja implementacja w Javie przy założeniu architektury z dwoma komplementami . Jeśli nie używasz uzupełnień dwójkowych, zamiast tego użyj standardowego wywołania funkcji Math.abs :

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

Zakładając, że w połowie przyzwoity kompilator / wbudowany LLVM rozszerza te funkcje, aby uniknąć kosztownego żonglowania stosem i przeszukiwania tabeli v. Nie powiedzie się to dla wartości wejściowych zbliżonych do ekstremów 32-bitowych (tj. Integer.MAX_VALUEI Integer.MIN_VALUE).

Najszybszym sposobem jest połączenie wszystkich 4 wartości w jednym rejestrze wektorowym.

Przechowuj pola w wektorze o następujących wartościach [ min.x, min.y, -max.x, -max.y ]. Jeśli przechowujesz takie pudełka, test przecięcia zajmuje tylko 3 instrukcje procesora:

_mm_shuffle_ps aby zmienić kolejność drugiego pola o min. i maks. o połowę.

_mm_xor_psz magiczną liczbą, _mm_set1_ps(-0.0f)aby przerzucić znaki wszystkich 4 wartości w drugim polu.

_mm_cmple_ps aby porównać ze sobą wszystkie 4 wartości, porównując następujące dwa rejestry:

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

Wreszcie, jeśli to konieczne, _mm_movemask_psaby uzyskać wynik z jednostki wektorowej w rejestrze skalarnym. Wartość 0 oznacza przecinające się pola. Lub jeśli masz więcej niż 2 pola, nie jest to konieczne, pozostaw wartości w rejestrach wektorowych i użyj operacji bitowych, aby połączyć wyniki z wielu pól.

Nie określiłeś języka ani platformy, ale obsługa SIMD, taka jak ta lub bardzo podobna, jest dostępna we wszystkich platformach i językach. Na urządzeniach mobilnych ARM ma NEON SIMD z bardzo podobnymi rzeczami. .NET ma Vector128 w przestrzeni nazw System.Runtime.Intrinsics i tak dalej.