Überschneidende Rechtecke im Raum

Question

Ich muss 1 Million räumliche Polygone (spezifiziert mit ihren Minimum Bounding Rectangles) mit 4 völlig disjunkten MBRs (MBR1, MBR2, MBR3, MBR4) im Raum schneiden. MBR1, MBR2, MBR3 und MBR4 teilen den gesamten Raum in vier disjunkte Teile. Dafür habe ich den folgenden Code geschrieben. Es stellt sich jedoch heraus, dass der Code für 1 Million Punkte sehr langsam läuft. Gibt es eine Möglichkeit, den Code zu verbessern, damit er etwas schneller läuft? Wenn ja, kann jemand bitte mit dem gleichen helfen

//--------------------------------------------------------------------------- 
struct MBR 
{ 
    double xRight, xLeft, yBottom, yTop; 
}; 
bool intersects(MBR spatialId,MBR mbr) 
{ 
    if (mbr.yBottom > spatialId.yTop || mbr.yTop < spatialId.yBottom) return false; 
    if (mbr.xLeft > spatialId.xRight || mbr.xRight < spatialId.xLeft) return false;   
    return true;  
} 
//--------------------------------------------------------------------------- 
bool contains(MBR spatialId,MBR mbr) 
{ 
    if (mbr.yBottom > spatialId.yBottom || mbr.yTop < spatialId.yTop) return false; 
    if (mbr.xLeft > spatialId.xLeft || mbr.xRight < spatialId.xRight) return false; 
    return true;  
} 
//--------------------------------------------------------------------------- 
bool touches(MBR spatialId,MBR mbr) 
{ 
    if ( (mbr.yBottom >= spatialId.yBottom + std::numeric_limits<double>::epsilon() && 
      mbr.yBottom <= spatialId.yBottom - std::numeric_limits<double>::epsilon()) || 
      (mbr.yTop >= spatialId.yTop + std::numeric_limits<double>::epsilon() && 
      mbr.yTop <= spatialId.yTop - std::numeric_limits<double>::epsilon())) 
      return true; 
    if ( (mbr.xLeft >= spatialId.xLeft + std::numeric_limits<double>::epsilon() && 
      mbr.xLeft <= spatialId.xLeft - std::numeric_limits<double>::epsilon()) || 
      (mbr.xRight >= spatialId.xRight + std::numeric_limits<double>::epsilon() && 
      mbr.xRight <= spatialId.xRight - std::numeric_limits<double>::epsilon())) 
      return true;  
    return false;  
} 
//--------------------------------------------------------------------------- 
MBR MBR1,MBR2,MBR3,MBR4; 
vector<unsigned> spatialIds; //contain 1 million spatial identifiers which are intersected with MBR1, MBR2, MBR3, MBR4 
//MBR1, MBR2, MBR3, MBR4 are again specified using their Minimum Bounding Rectangles 
vector<unsigned> result; //contains the resulting intersecting spatial ids 
for(vector<MBR>::iterator itSpatialId=spatialIds.begin(),lSpatialId=spatialIds.end();itSpatialId!=lSpatialId;++itSpatialId) 
{ 
    if(intersects((*itSpatialId),MBR1)||contains((*itSpatialId),MBR1)||touches((*itSpatialId),MBR1)) 
    { 
     result.push_back((*itSpatialId)); 
    } 

    if(intersects((*itSpatialId),MBR2)||contains((*itSpatialId),MBR2)||touches((*itSpatialId),MBR2)) 
    { 
     result.push_back((*itSpatialId)); 
    }      

    if(intersects((*itSpatialId),MBR3)||contains((*itSpatialId),MBR3)||touches((*itSpatialId),MBR3)) 
    { 
     result.push_back((*itSpatialId)); 
    } 

    if(intersects((*itSpatialId),MBR4)||contains((*itSpatialId),MBR4)||touches((*itSpatialId),MBR4)) 
    { 
     result.push_back((*itSpatialId)); 
    } 
} 

Answer 1

Ich denke, Sie können den Schnittpunkttest vereinfachen.

Erstens, ich glaube nicht, dass epsilon notwendig ist, wenn zwei Werte verglichen werden, der Vergleichsoperator führt keinen numerischen Fehler ein.

Zweitens müssen Sie nur folgendes überprüfen:

bool intersectsContainsOrTouches(MBR spatialId,MBR mbr) 
{ 
    return (mbr.yBottom <= spatialId.yTop && mbr.yTop >= patialId.yBottom) &&  
     (mbr.xLeft <= spatialId.xRight && mbr.xRight >= spatialId.xLeft); 
} 

Normalerweise würden Sie BSP verwenden oder einen mehrdimensionalen Index eine räumliche 'JOIN Operation auszuführen. Da Sie jedoch nur 4 Rechtecke haben, sollte es schneller sein, einfach durch alle 1M Rechtecke zu iterieren und jedes mit den 4 MBRs zu vergleichen. Ich bin mir nicht sicher, dass mehrdimensionale Indizes oder Binärraum-Partitionierung hier helfen würde.

Btw, wie lange dauert es? Es sollte deutlich weniger als eine Minute sein, ist das ein Problem?

EDIT

Wenn Sie dies immer wieder zu tun haben, würde ich die Daten in einen räumlichen Index setzen, dann können Sie für jede Ihrer MBRs vier Fenster Abfragen auf dem Index durchzuführen. Es gibt auch dedizierte Algorithmen wie TOUCH. Wenn Sie Java verwenden, werfen Sie einen Blick auf meine PH-Tree (was auch gut ist, wenn einzelne Rechtecke hinzugefügt/entfernt oder verschoben werden. Für andere Sprachen, überprüfen Sie R-Baum (R + Baum, X-Baum, ..), kd -Bäume oder Quadtrees.

für C++, können Sie einen Blick auf ODE haben. Es ist eine Physik-Engine 3D-Spiel, die intern mehrere Algorithmen zur Erkennung MBR überlappt hat (Quadtrees, SAP-Raum, ...).