CODEWITHSUNDEEP
c++data-structuresspatial
Jannat Arora
Jannat Arora

Reputation: 2989

Intersecting rectangles in space

I need to intersect 1 million spatial polygons (specified using their Minimum Bounding Rectangles) with 4 completely disjoint MBR's (MBR1,MBR2,MBR3,MBR4) in space. MBR1, MBR2, MBR3 and MBR4 divide the entire space into 4 disjoint parts. For doing so, I wrote the following code. However, it turns out that for 1 million points the code is running very slowly. Is there some way by which I may improve the code so that it may run a bit faster. If yes, then can someone please help with the same

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

Upvotes: 1

Views: 93

Answers (1)

TilmannZ
TilmannZ

Reputation: 1889

I think you can simplify the intersection test.

First, I don't think the epsilon is necessary when comparing two values, the comparison operator does not introduce any numerical error.

Second, you only need to check the following:

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

Normally, you would use BSP or a multidimensional index to perform a spatial 'JOIN' operation. But since you have only 4 rectangles to join with, it should be faster to simply iterate through all 1M rectangles and compare each one with the 4 MBRs. I'm not sure that multi-dimensional indexes or binary space partitioning would help here.

Btw, how long does it take? It should clearly be less than a minute, is that a problem?

EDIT

If you have to do this repeatedly, I would put the data into a spatial index, then you can perform four window queries on the index for each of your MBRs. There are also dedicated algorithms, such as TOUCH. If you are using Java, have a look at my PH-Tree (which is also good when individual rectangles are added/removed or moved. For other languages, check R-Tree (R+tree, X-Tree, ..), kd-trees or quadtrees.

For C++, you could have a look at ODE. It's a 3D game physics engine that internally has several algorithms for detecting MBR overlaps (Quadtrees, SAP-Space, ...).

Upvotes: 1

Related Questions