我试图在这里使用以下库(模板化版本),但在库中显示的示例中,用户定义了边界框。在我的问题中,我每次都有未知维度的数据,所以我不知道如何使用它。除此之外,R-Tree不应该能够在每次插入时计算边界框吗?
这是库的示例代码,您可以看到用户每次都定义了边界框:
#include <stdio.h>
#include "RTree.h"
struct Rect
{
Rect() {}
Rect(int a_minX, int a_minY, int a_maxX, int a_maxY)
{
min[0] = a_minX;
min[1] = a_minY;
max[0] = a_maxX;
max[1] = a_maxY;
}
int min[2];
int max[2];
};
struct Rect rects[] =
{
Rect(0, 0, 2, 2), // xmin, ymin, xmax, ymax (for 2 dimensional RTree)
Rect(5, 5, 7, 7),
Rect(8, 5, 9, 6),
Rect(7, 1, 9, 2),
};
int nrects = sizeof(rects) / sizeof(rects[0]);
Rect search_rect(6, 4, 10, 6); // search will find above rects that this one overlaps
bool MySearchCallback(int id, void* arg)
{
printf("Hit data rect %dn", id);
return true; // keep going
}
void main()
{
RTree<int, int, 2, float> tree;
int i, nhits;
printf("nrects = %dn", nrects);
for(i=0; i<nrects; i++)
{
tree.Insert(rects[i].min, rects[i].max, i); // Note, all values including zero are fine in this version
}
nhits = tree.Search(search_rect.min, search_rect.max, MySearchCallback, NULL);
printf("Search resulted in %d hitsn", nhits);
// Iterator test
int itIndex = 0;
RTree<int, int, 2, float>::Iterator it;
for( tree.GetFirst(it);
!tree.IsNull(it);
tree.GetNext(it) )
{
int value = tree.GetAt(it);
int boundsMin[2] = {0,0};
int boundsMax[2] = {0,0};
it.GetBounds(boundsMin, boundsMax);
printf("it[%d] %d = (%d,%d,%d,%d)n", itIndex++, value, boundsMin[0], boundsMin[1], boundsMax[0], boundsMax[1]);
}
// Iterator test, alternate syntax
itIndex = 0;
tree.GetFirst(it);
while( !it.IsNull() )
{
int value = *it;
++it;
printf("it[%d] %dn", itIndex++, value);
}
getchar(); // Wait for keypress on exit so we can read console output
}
我想在R-Tree中保存的一个例子是:
-------------------------------
| ID | dimension1 | dimension2|
-------------------------------
| 1 | 8 | 9 |
| 2 | 3 | 5 |
| 3 | 2 | 1 |
| 4 | 6 | 7 |
-------------------------------
维度
你对维度的要求会有一些限制。这是因为计算机只有无限的存储空间,所以不能存储无限的维度。实际上,这是你想要支持多少维度的决定。最常见的数字当然是2和3。你真的需要支持11个人吗?你打算什么时候用它?
您可以通过始终使用具有您支持的最大数量的r树并传递零作为其他坐标来做到这一点,或者最好创建几个代码路径,每个支持的维度数一个。也就是说,你可以为二维数据设置一组例程,为三维数据设置另一组例程,以此类推。
计算边界框
边界框是与轴对齐的矩形或长方体,完全包围你想要添加的对象。
- 所以如果你插入的是轴对齐的矩形/长方体等,那么形状就是边界框。
- 如果要插入点,则每个维度的最小值和最大值就是该维度的点值。
- 任何其他形状,你必须计算边界框。例如,如果你要插入一个三角形,你需要计算完全包围三角形的矩形作为边界框。
库不能为你做这个,因为它不知道你插入的是什么。你可能会插入圆心+半径的球体,或者复杂的三角形网格形状。R-Tree可以提供空间索引,但需要您提供一些信息来填补空白。