finden überlappende Rechtecke Algorithmus

Persönlich würde ich dies lösen, mit einem KD-Baum oder ein BIH-Baum. Sie sind beide adaptive räumliche Datenstrukturen, die eine log(n) bei der Suche Zeit. Ich habe eine Implementierung für meine Ray-Tracer, und Sie Schreien.

-- UPDATE --

Speichern Sie alle Ihre festen Rechtecke in dem KD-Baum. Wenn Sie testen Kreuzungen, Durchlaufen die KD-Baum wie folgt:

function FindRects(KDNode node, Rect searchRect, List<Rect> intersectionRects)

//searchRect is the rectangle you want to test intersections with
//node is the current node. This is a recursive function, so the first call
//   is the root node
//intersectionRects contains the list of rectangles intersected

int axis = node.Axis;

//Only child nodes actually have rects in them
if (node is child)
{
    //Test for intersections with each rectangle the node owns
    for each (Rect nRect in node.Rects)
    {
        if (nRect.Intersects(searchRect))
              intersectionRects.Add(nRect);
    }
}
else
{
    //If the searchRect's boundary extends into the left bi-section of the node
    //we need to search the left sub-tree for intersections
    if (searchRect[axis].Min  //Min would be the Rect.Left if axis == 0, 
                              //Rect.Top if axis == 1
                < node.Plane) //The absolute coordinate of the split plane
    {
        FindRects(node.LeftChild, searchRect, intersectionRects);
    }

    //If the searchRect's boundary extends into the right bi-section of the node
    //we need to search the right sub-tree for intersections
    if (searchRect[axis].Max  //Max would be the Rect.Right if axis == 0
                              //Rect.Bottom if axis == 1
                > node.Plane) //The absolute coordinate of the split plane
    {
        FindRects(node.RightChild, searchRect, intersectionRects);
    }
}

Diese Funktion sollte funktionieren, nach der Umwandlung von pseudo-code, aber der Algorithmus ist korrekt. Dies ist eine log(n) search-Algorithmus, und wahrscheinlich die langsamste Implementierung von it - (konvertieren von rekursiv mit stack-basiert).

-- UPDATE -- Hinzugefügt eine einfache KD-Baum-Gebäude-Algorithmus

Die einfachste form eines KD-Baumes, enthält die Flächen/Volumen-Formen ist die folgende:

Rect bounds = ...; //Calculate the bounding area of all shapes you want to 
              //store in the tree
int plane = 0; //Start by splitting on the x axis

BuildTree(_root, plane, bounds, insertRects);

function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)

if (insertRects.size() < THRESHOLD /* Stop splitting when there are less than some
                                      number of rects. Experiment with this, but 3
                                      is usually a decent number */)
{
     AddRectsToNode(node, insertRects);
     node.IsLeaf = true;
     return;
}

float splitPos = nodeBds[plane].Min + (nodeBds[plane].Max - nodeBds[plane].Min) / 2;

//Once you have a split plane calculated, you want to split the insertRects list
//into a list of rectangles that have area left of the split plane, and a list of
//rects that have area to the right of the split plane.
//If a rect overlaps the split plane, add it to both lists
List<Rect> leftRects, rightRects;
FillLists(insertRects, splitPos, plane, leftRects, rightRects); 

Rect leftBds, rightBds; //Split the nodeBds rect into 2 rects along the split plane

KDNode leftChild, rightChild; //Initialize these
//Build out the left sub-tree
BuildTree(leftChild, (plane + 1) % NUM_DIMS, //2 for a 2d tree
          leftBds, leftRects);
//Build out the right sub-tree
BuildTree(rightChild, (plane + 1) % NUM_DIMS,
          rightBds, rightRects);

node.LeftChild = leftChild;
node.RightChild = rightChild;

Gibt es eine Reihe von offensichtlichen Optimierungen hier, aber die build-Zeit ist in der Regel nicht so wichtig wie die Suche nach Zeit. That being said, eine gut bauen Baum ist, was macht die Suche schnell. Look-up SAH-KD-Tree, wenn Sie möchten lernen, wie man eine schnelle kd-Baum.

Können Sie erstellen, die zwei Vektoren Rechteck Indizes (weil zwei Diagonale Punkte eindeutig definieren das Rechteck), und Sortieren Sie Sie, indem Sie eine der Koordinaten. Dann suchen Sie überlappt mit diesen beiden index-arrays, die gehen, um logarithmische statt lineare Komplexität.

Erstellen Sie eine matrix mit "quadrant" - Elementen, wobei jeder quadrant repräsentiert eine N*M Speicherplatz in Ihrem system, mit N und M wird die Höhe und Breite an der breitesten und höchsten Rechtecke, jeweils. Jedes Rechteck wird platziert in einem Quadranten element auf der Grundlage der oberen linken Ecke (jedes Rechteck wird in genau einem Quadranten). Gegeben ein Rechteck Ein, überprüfen Sie auf Kollisionen zwischen Rechtecke in Einem eigenen Quadranten und die 8 angrenzenden Quadranten.

Dies ist ein Algorithmus, den ich erinnere mich da empfohlen, als eine einfache Optimierung für brute-force-hit-tests bei der Kollisionsprüfung für game design. Es funktioniert am besten, wenn Sie hauptsächlich den Umgang mit kleinen Objekten, obwohl, wenn Sie ein paar große Objekte können Sie vermeiden, wrecking seine Effizienz durch durchführen der Kollisionserkennung für Sie separat und nicht indem Sie in einem Quadranten, wodurch quadrant Größe.

Topcoder bietet eine Möglichkeit, um zu bestimmen, liegt ein Punkt innerhalb eines Rechtecks. Es sagt, dass, sagen wir, wir haben einen Punkt x1,y1 und ein Rechteck. Sollten wir wählen einen beliebigen Punkt sehr weit Weg vom aktuellen Ort des Verweises in dem rechteckigen Koordinatensystem sagen, x2,y2.

Nun wir sollten ein Liniensegment, das die Punkte x1,y1 und x2,y2. Wenn das Liniensegment schneidet ungerade Anzahl von Seiten des gegebenen Rechtecks (es werden 1 in unserem Fall, kann diese Methode erweitert werden, um Allgemeine Polygone als gut), dann ist der Punkt x1,y1 liegt innerhalb des Rechtecks und, wenn es schneidet sogar die Anzahl der Seiten liegt außerhalb des Rechtecks.

Gegeben sind zwei Rechtecke, wir müssen wiederholen Sie diesen Vorgang für jede Ecke der 1 Dreieck möglicherweise liegen in der zweiten Dreieck. Auf diese Weise wären wir in der Lage, um zu bestimmen, ob sich zwei Rechtecke überlappen, auch wenn Sie nicht ausgerichtet auf die x-oder y-Achse.

Lassen Sie Ihre Rechteck sein (Xi1,Yi1,Xi2,Yi2), wo ich variiert von 0 bis N.

Rechteck A und B können sich NICHT kreuzenden, wenn Ax1 > Bx2 || Ay1 < By2 || Bx1 > Ax2 || By1 < Ay2.

Erstellen von Baum ist optimiert für range/interval (Für exa: segment-Baum oder Intervall-Baum)
Sehen http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l5cs4235.pdf

Verwenden Sie diesen Baum zu finden set von triangle, während Ihr Dreieck ist das ändern von Koordinaten.

Methode (A)

Man könnte eine Intervall-Baum oder segment-Baum. Wenn die Bäume waren so angelegt, dass Sie würde ausgeglichen werden, dies würde Ihnen eine Laufzeit von O(log n). Ich nehme an, diese Art der Vorverarbeitung ist praktisch, denn es würde nur passieren, wenn (wie es scheint, Sie beschäftigen sich mehr mit der Laufzeit, sobald das Rechteck beginnt sich zu bewegen, als Sie mit der Menge der anfänglichen Vorverarbeitung für die erste Zeit). Der Speicherplatz wäre O(n) oder O(n log n) je nach Ihrer Auswahl oben.

Methode (B)

Gegeben, dass Ihre große Menge der Rechtecke mit fester Größe, und nie ändern Sie Ihre Koordinaten, und dass Sie sich nicht überlappen, könnten Sie versuchen, einen etwas anderen Stil des Algorithmus/Heuristik als vorgeschlagen, von anderen hier (vorausgesetzt, Sie Leben können mit einer einmaligen, im Voraus Vorverarbeitung Gebühr).

Preprocessing-Algorithmus [O(n log n) oder O(n^2) Laufzeit {nur einmal ausgeführt, obwohl}, O(n) space]

1. Art der Rechtecke, die durch Ihre horizontalen Koordinaten mit Ihrer Lieblings-Sortier-Algorithmus (ich gehe davon aus, dass O(n log n) Laufzeit).
2. Art der Rechtecke durch Ihre vertikalen Koordinaten mit Ihrer Lieblings-Sortier-Algorithmus (ich gehe davon aus, dass O(n log n) Laufzeit)

3. Berechnen Sie ein Verteilungsfunktion und ein cumulative distribution function der horizontalen Koordinaten. (Laufzeit von O(1) O(n^2) je nach Methode verwendet und welche Art von distribution Sie Ihre Daten verfügt)

   Wenn a) die Rechtecke die horizontalen Koordinaten Folgen einige natürlich vorkommenden Prozess, dann können Sie wahrscheinlich schätzen Ihre Verteilungsfunktion durch die Verwendung einer bekannten Verteilung (ex: normal, exponentielle, uniform, etc.).

   b) Wenn Ihr Rechtecke, horizontalen Koordinaten Folgen Sie einer bekannten Verteilung, dann berechnen Sie eine benutzerdefinierte/geschätzte Verteilung durch die Schaffung einer Histogramm.

4. Berechnen Sie ein Verteilungsfunktion und ein cumulative distribution function der vertikalen Koordinaten.

   Wenn a) die Rechtecke die vertikalen Koordinaten Folgen einige natürlich vorkommenden Prozess, dann können Sie wahrscheinlich schätzen Ihre Verteilungsfunktion durch die Verwendung einer bekannten Verteilung (ex: normal, exponentielle, uniform, etc.).

   b) Wenn die Rechtecke die vertikalen Koordinaten nicht nach einer bekannten Verteilung, dann berechnen Sie eine benutzerdefinierte/geschätzte Verteilung durch die Schaffung einer Histogramm.

Echtzeit-Kreuzung zu Finden-Algorithmus [Überall von O(1) O(log n) O(n) {Hinweis: wenn Sie O(n), dann ist die Konstante vor dem n wäre sehr klein} Laufzeit, je nachdem wie gut die Verteilungs-Funktionen, passen Sie das dataset]

1. Unter die horizontale Koordinate, Ihre beweglichen Rechteck und stecken Sie es in die kumulative Dichte-Funktion der horizontalen Koordinaten der vielen Rechtecke. Diese Ausgabe wird eine Wahrscheinlichkeit (Wert zwischen 0 und 1). Multiplizieren Sie diesen Wert mal n (wo n ist die Anzahl der vielen Rechtecke, die Sie haben). Dieser Wert wird dem array-index zu überprüfen, in der sortiert Rechteck-Liste. Wenn das Rechteck von diesem array-index geschieht, zu verschneiden, dann sind Sie fertig und können mit dem nächsten Schritt fortfahren. Andernfalls müssen Sie zum Scannen der umliegenden Nachbarn, um zu bestimmen, wenn die Nachbarn die sich mit der bewegten Rechtecks. Sie können angreifen, der diesen Teil des Problems mehrere Möglichkeiten:

   a) ein linear-scan, bis zu finden die sich überschneidenden Rechteck oder finden Sie ein Rechteck auf der anderen Seite der sich bewegenden Rechteck

   b) berechnen Sie eine Konfidenzintervall über die Wahrscheinlichkeits-Dichte-Funktionen, die Sie berechnet, um Ihnen eine bestmögliche Schätzung zu möglichen Grenzen (d.h. ein Intervall, in denen ein Schnittpunkt liegen muss). Führen Sie dann eine binäre Suche auf diesem kleinen Intervall. Wenn die binäre Suche nicht, dann wieder zurück zu einer linearen Suche in Teil (a).

2. Tun die gleiche Sache wie Schritt 1, aber tun Sie es für die vertikalen Teile anstatt der horizontalen Teile.

3. Wenn Schritt 1 ergab eine Kreuzung zu und Schritt 2 ergab eine Kreuzung und die sich überschneidenden Rechteck in Schritt 1 wurde das gleiche Rechteck wie in Schritt 2, dann ist das Rechteck muss die Schnittmenge mit dem beweglichen Rechteck. Ansonsten gibt es keinen Schnittpunkt.