c++ - 计算相邻矩形的数量

Question

我的代码在 [0,1] 范围内的二维空间中打印一组 (X,Y) 坐标。

void Rect_Print() {
    cout << "In counter-clockwise fashion" << endl;
    cout << "#Rectangle    (   x0,   y0)   (   x1,   y1) " << endl;

    for (int b=0; b<Rect_Count; b++) {
       double Area = (Rect[b].x0 - Rect[b].x1) * (Rect[b].y0 - Rect[b].y1);

       cout << fixed << setprecision(4) << (b+1) <<
               "  (" << Rect[b].x0 << "," << Rect[b].y0 <<
             ")   (" << Rect[b].x1 << "," << Rect[b].y1 << ")" << endl;
    }

    cout << "Number of divisions (N = 3j-2) = " << Rect_Count << endl;
}

这些点将一个单位正方形划分为 (3j-2) 个子矩形(不均匀)。对于每个特定的矩形，我想计算与其相邻的矩形的总数。

示例

1. 假设第一个坐标将单位正方形分成四个矩形，如:

   

   在这张图片中你可以看到，有 三个矩形 与 rectangle-3 相邻。

2. 如果我继续这样做，在我的第六步之后单位正方形分成 19 个矩形。所以它看起来像:

   

   现在有 五个矩形 与 rectangle-3 相邻。 六个矩形与矩形 11 相邻。

假设我有一组 一万个 坐标，它们将正方形 segmentation 为小的子矩形。我想用 C++ 来计算与每个相邻的矩形的数量。我该怎么做？

在 Internet 上搜索后，Flann 似乎可以帮我解决这个问题。我阅读了用户手册，但不明白我该怎么做。

谁能帮帮我？

Answer 1

我建议您使用类似于四叉树的东西来构建它(参见 Wikipedia Quadtree article )。此处的区别在于您不会均匀地拆分四叉树的子节点 - 您会在插入的点处拆分。

然后您可以遍历树，搜索相交边。

如果一个节点没有与您的查询矩形相交的边，那么您不需要递归到它的子节点，这将在对 10,000 个矩形执行此操作时节省 CPU 时间，因为复杂度是对数的而不是线性的.

树的叶 block 是您的矩形列表，因此您应该只计算作为树叶并与查询矩形相交的矩形。

这也是一种处理矩形 segmentation 的便捷方式——当您插入一个点时，您可以递归到树中以快速找到要分割的矩形。