Tag: 四叉树

基于空间代理的建模的数据结构: 在二维空间模拟中跟踪代理的一些好的数据结构是什么？我已经看到一些对四叉树（我理解）和kd树（我不太了解）的引用。我正在寻找一个代理人可以有效地说出的话，“我知道我的位置，而且我想知道哪些代理人在我附近（在我自己的某个半径范围内）。” 非常感谢示例（伪代码很好）。我在Java工作。

使用QuadTree获取边界圆内的所有点: 我有一套100到200点（x，y）。我必须检查哪些落在其他人的特定距离内。整个程序的特定距离是固定的，例如50.假设点1落在点5,7,25,90,96,105等的范围内。类似地，点2落在23,45等范围内…… 存储用于通过x，y坐标定位的对象这里建议使用QuadTree，但它可用于获取边界矩形内的所有点。但是如何获得一个边界内的所有点？有一种方法可以在最大距离内返回最接近纬度/经度的点，但是如何获得距离内的所有点？ http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float,love，float，float，int）一种方法可能是在我得到它时从树中删除每个点，然后再次查询最近的点，直到我得到null。这是唯一的方法吗？

存储用于通过x，y坐标定位的对象: 我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个x和y坐标值，这样我就可以快速检索某个矩形或圆形内的所有对象。对于小型对象集（~100），简单地将它们存储在列表中并通过它迭代的简单方法相对较快。但是，对于规模更大的群体来说，这预计会很慢。我已经尝试将它们存储在一对TreeMaps中，一个在x坐标上排序，一个在y坐标上排序，使用以下代码： xSubset = objectsByX.subSet( minX, maxX ); ySubset = objectsByY.subSet( minY, maxY ); result.addAll( xSubset ); result.retainAll( ySubset ); 这也适用，对于较大的对象集更快，但仍然比我想要的慢。部分问题还在于这些对象移动，需要插回到此存储中，这意味着将它们从树中删除并重新添加到树/列表中。我不禁想到那里必须有更好的解决方案。我在Java中实现这个，如果它有任何区别，尽管我希望任何解决方案都会以有用的模式/算法的forms出现。