1

我的代码在 [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. 假设第一个坐标将单位正方形分成四个矩形，如：

    图片

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

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

    图片

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

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

在互联网上搜索后，似乎 Flann 可以帮助我做到这一点。我阅读了用户手册，但不明白我该怎么做。

谁能帮我？

4

2 回答 2

0

您可以查找 r-tree 或 kd-tree。树形图算法的工作原理类似。一个好的开始是对盒子进行排序，然后通过在 2 轴上递归拆分盒子并将它们放入树中，然后查看下一个盒子适合的位置。

于 2013-08-26T14:37:29.137 回答
0

我建议您使用类似于四叉树的东西来构建它（参见维基百科四叉树文章）。这里的区别在于您没有均匀地拆分四叉树的子节点 - 您在插入的点处拆分。

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

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

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

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

于 2013-06-24T12:25:35.557 回答