c++ - 空间中的相交矩形

Question

我需要将 100 万个空间多边形(使用它们的最小边界矩形指定)与空间中的 4 个完全不相交的 MBR(MBR1、MBR2、MBR3、MBR4)相交。 MBR1、MBR2、MBR3和MBR4将整个空间分成4个不相交的部分。为此，我编写了以下代码。然而，事实证明，对于 100 万个点，代码运行非常缓慢。有什么方法可以改进代码，使其运行得更快。如果是，那么有人可以帮忙吗

//---------------------------------------------------------------------------
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

我认为你可以简化相交测试。

首先，我认为比较两个值时不需要 epsilon，比较运算符不会引入任何数值错误。

其次，您只需检查以下内容:

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

通常，您会使用 BSP 或多维索引来执行空间“JOIN”操作。但是由于您只有 4 个矩形可以连接，因此简单地遍历所有 1M 的矩形并将每个矩形与 4 个 MBR 进行比较应该会更快。我不确定多维索引或二进制空间分区在这里是否有帮助。

顺便问一下，需要多长时间？显然应该不到一分钟，这有问题吗？

编辑

如果您必须重复执行此操作，我会将数据放入一个空间索引中，然后您可以对每个 MBR 的索引执行四个窗口查询。还有专用的算法，比如TOUCH .如果您使用的是 Java，请查看我的 PH-Tree (这在添加/删除或移动单个矩形时也很好。对于其他语言，请检查 R-Tree(R+tree、X-Tree、..)、kd-trees 或四叉树。

对于 C++，您可以查看 ODE .它是一个 3D 游戏物理引擎，内部具有多种用于检测 MBR 重叠的算法(四叉树、SAP-Space 等)。