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

• 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? – Steven Apr 5 '16 at 3:32
• @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. – Jannat Arora Apr 5 '16 at 6:28