存储对象以通过 x,y 坐标定位 [英] Storing objects for locating by x,y coordinates

问题描述

我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个 x 和 y 坐标值，以便我可以快速检索某个矩形或圆形内的所有对象.对于一小组对象(~100)，简单地将它们存储在一个列表中并遍历它的简单方法相对较快.然而，对于更大的群体，这预计会很慢.我也尝试将它们存储在一对 TreeMap 中，一个在 x 坐标上排序，一个在 y 坐标上排序，使用以下代码:

I'm trying to determine a fast way of storing a set of objects, each of which have an x and y coordinate value, such that I can quickly retrieve all objects within a certain rectangle or circle. For small sets of objects (~100) the naive approach of simply storing them in a list, and iterating through it, is relatively quick. However, for much larger groups, that is expectedly slow. I've tried storing them in a pair of TreeMaps as well, one sorted on the x coordinate, and one sorted on the y coordinate, using this code:

xSubset = objectsByX.subSet( minX, maxX );
ySubset = objectsByY.subSet( minY, maxY );
result.addAll( xSubset );
result.retainAll( ySubset );

这也有效，并且对于更大的对象集更快，但仍然比我想要的要慢.部分问题还在于这些对象会四处移动，需要重新插入到该存储中，这意味着将它们从树/列表中删除并重新添加到树/列表中.我不禁认为必须有更好的解决方案.我正在 Java 中实现它，如果它有任何不同，但我希望任何解决方案都将更多地采用有用的模式/算法的形式.

This also works, and is faster for larger sets of objects, but is still slower than I would like. Part of the problem is also that these objects move around, and need to be inserted back into this storage, which means removing them from and re-adding them to the trees/lists. I can't help but think there must be better solutions out there. I'm implementing this in Java, if it makes any difference, though I expect any solution will be more in the form of a useful pattern/algorithm.

推荐答案

Quadtrees 似乎可以解决我问的具体问题.Kd-Trees 是一种更通用的形式，适用于任意数量的维度，而不仅仅是两个维度.

Quadtrees seem to solve the specific problem I asked. Kd-Trees are a more general form, for any number of dimensions, rather than just two.

R-Trees 如果存储的对象具有边界矩形，则也可能有用，而不仅仅是一个简单的点.

R-Trees may also be useful if the objects being stored have a bounding rectangle, rather than being just a simple point.

这些类型结构的通用术语是空间索引.

The general term for these type of structures is Spatial Index.

有一个Quadtree<的Java实现/a> 和 R-Tree.

这篇关于存储对象以通过 x,y 坐标定位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！