标签: r-tree

我看了KD树和R树的定义.在我看来,他们几乎是一样的.

KD树和R树之间有什么区别？

有没有人知道在生产代码R-tree实现中使用的好和简单？(实际上,任何实现 - R*, R+或者PR-tree会很棒)

它是一个模板或库实现无关紧要,但谷歌发现的一些实现看起来非常令人失望......

我在C#中找到了一些开源的R-Tree实现,但没有一个带有文档,也没有被开发者以外的其他人使用的迹象.

我想比较地理空间数据的R-Tree和Quadtree.虽然有文献,但我很难找到涵盖真正基本比较的文件.所以我决定问这个问题.

在我看来,R-Tree具有平衡的优点,树没有空叶.作为缺点,插入或删除等基本操作可能导致重构整个索引.

四叶树是相反的,它不平衡并且有空叶,但它不需要被重新修剪.

因此,作为一个讽刺,我会说R-Tree确实需要更少的内存,并且由于最小的高度,搜索速度更快.当有许多更新操作时,四叉树更好,但结果树可能是不平衡的.

您认为这些观点是否正确？那里有没有涵盖这个主题的好文件？

Auf Wiedersehen,安德烈

我需要Java中的商业友好(Apache许可证,LGPL,Mozilla公共许可证等)R-tree实现,以便将地理名称 Web Service 替换为时区,如问题"在不使用Web的情况下从纬度/经度确定时区 "中所建议的那样像Geonames.org这样的服务 ".我已经发现 了一些 身边,但我想知道,如果有人评估或在实践中使用它们.

我正在寻找一个稳定的实现R树与支持无限尺寸(20左右就足够了)的最后几天.我只找到了这个http://sourceforge.net/projects/jsi/,但它们只支持2个维度.

另一个选项是区间树的多维实现.

也许我完全错误地使用了R-Tree或Intervall-tree来解决我的问题,所以我简单地说明了问题,你可以把你的想法发给我.

我需要解决的问题是某种最近邻搜索.我有一套天线和房间,每个天线有一个整数间隔.例如天线1,最小-92,最大-85.实际上它可以表示为房间 - >天线组 - >天线间隔.这个想法是每个房间在天线的尺寸上跨越R树中的一个盒子,并且在每个维度上跨越间隔.

如果我得到N-Antennas的查询和每个天线的值,那么我可以将信息表示为房间中的查询点并检索"最接近"点的房间.

希望你对问题和我的想法有所了解.

建立

• 函数需要提供从点到多边形最近边缘的距离
• 已知点在多边形内部
• 多边形可以是凸面或凹面
• 需要测试许多点(数百万)
• 每个点需要运行许多单独的多边形(数十个)
• 预先计算和持久存储的数据结构是一种选择.
• 最终的搜索功能将使用C++

对于函数实现,我知道一个简单的方法是使用标准距离到线段公式来测试到多边形的所有段的距离.这个选项规模相当慢,我相信应该有更好的选择.

我的直觉是,对于这种类型的功能应该有一些非常快速已知的算法,这些算法可以在游戏引擎中实现,但我不知道在哪里看.

我找到了一个用于在四叉树中存储线段的参考,这将提供非常快速的搜索,我认为它可以用于我的目的,以快速缩小哪个段看作最近的段然后只需要计算到一个线段的距离. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

我无法找到任何代码示例来说明这将如何工作.我不介意从头开始实现算法,但是如果存在一个可用的,经过测试的代码库,那么就不会明白这一点.

我一直在寻找几个四叉树实现,我认为它的工作方式是每个多边形创建一个四叉树,并将每个多边形的线段与一个边界框插入到该多边形的四叉树中.

我将要制作的函数的"查询"部分将包括创建一个点作为一个非常小的边界框,然后将其用于搜索四叉树结构,然后只能找到多边形的最接近的部分.

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

和

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

我真正的问题是,这对于快速搜索时间功能来说似乎是一种合理的方法吗？

有什么东西可以更快地运作吗？

编辑:我一直在环顾四周,发现使用四叉树的一些问题.四叉树的工作方式有利于碰撞检测,但不能设置为允许有效的最近邻搜索. https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-Trees看起来是更好的选择. https://en.wikipedia.org/wiki/R-tree

和

处理2d线段的有效方法

基于这些帖子,R树看起来像赢家.也很方便看到C++ Boost已经实现了它们.这看起来足够接近我计划做的事情,我将继续实施并验证结果.

我在哪里可以找到足够的文档来实现R*-Tree？具体来说,我需要能够:

• 插入节点
• 删除节点
• 搜索K最近的邻居
• 查找距离x内所有最近的邻居.

有没有一个地方可以清楚地记录这个算法？或者,我可以研究一个干净,开源的实现吗？更好的是,如果你能指出我的javascript实现,那么我的工作已经完成.

我有大量的2D线段.所以,我知道; 每个线段的行号,Begin(X,Y,Z)和End(x,Y,Z).我想获得给定线段的接近线段.同样对所有人.

为了找到距离,我可以应用它

如果我说我的数据是;

所以,最后我希望将接近线作为每个线段的矢量.我听说这种矢量矢量可以用r树数据结构.我正在搜索它,但仍然无法找到相关的一个.我也看了一下opencv,有一个r-tree但它说了一些关于分类器和训练阶段...所以,我想它不适合我.

任何人都可以知道如何得到 行号,然后它的邻居行为前;

1 = {2,4,,7,66,32,12}

2 = {1,4,5,6}

3 = {...} .. ..这种类型的矢量使用r树.

我知道,我们可以使用kd-tree获得这种类型的向量.但它是专为点数据而设计的.因此,我认为很难在这种情况下使用kd-tree.请帮忙,谢谢.

可能重复:
.NET是否有任何记录的免费R-Tree实现？

F#中是否有任何R-Tree实现？

假设是:不需要插入或删除固定的Geo-Fences(区域)集合.需求是:搜索时间非常快.

谢谢