1
\$\begingroup\$

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> resultMBR1, resultMBR2, resultMBR3, resultMBR4; //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))
    {
        resultMBR1.push_back((*itSpatialId));
    }

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

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

    if(intersects((*itSpatialId),MBR4)||contains((*itSpatialId),MBR4)||touches((*itSpatialId),MBR4))
    {
        resultMBR4.push_back((*itSpatialId));
    }   
}
\$\endgroup\$
  • \$\begingroup\$ Do they move? How often do you do the query? What does 'needs to intersect' - with each other? Can you include more details on the use case? Finally, have you run a profiler to identify what is actually slow? \$\endgroup\$ – Steven Apr 5 '16 at 3:32
  • \$\begingroup\$ @Steven No the points do not move. I need to query frequently. I mean I need to store in resultMBR1 the spatial regions amongst the 1 million regions which intersect MBR1, similarly for MBR2, MBR3 and MBR4, etc. The intersection test is the most time-consuming according to the profiler. \$\endgroup\$ – Jannat Arora Apr 5 '16 at 6:28
1
\$\begingroup\$

I suggest using a space-partitioning data structure, i.e. Quadtrees. They reduce running time from linear to logarithmic in the number of rectangles, which will give you the desired performance boost.

Here is a nice tutorial on how to implement and use them.

http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

\$\endgroup\$
  • 1
    \$\begingroup\$ An Interval Tree may also be an effective acceleration structure for this particular use case. \$\endgroup\$ – DMGregory Jul 8 '16 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.