我有最多10,000个随机位置的点在一个空间内，并且需要能够在任何时候确定鼠标最接近哪个点。为了提供一些背景信息，这些点是以向量图形式存在的，因此用户可以随时快速地添加和删除它们，并且在画布空间中可能不平衡分布。
因此，我正在尝试找到最有效的数据结构来存储和查询这些点。如果可能的话，我希望保持这个问题语言无关。
存储数千个向量的数据结构
13
- Tom
6
3好的，我会尽力进行翻译。这可能有所帮助：http://en.wikipedia.org/wiki/Nearest_neighbor_search。 - Aziz
请确认用户只能修改线段的端点，并且点的数量保持不变，为常数n（例如："10000"）。大多数数据结构算法都是为了提供一般使用情况下的渐进性能保证而设计的。 - alphazero
澄清一下，10000只是一个大致的数字，用来说明图纸可能很大，用户可以根据需要添加和删除线条，我实际上是想创建一个简单的矢量绘图程序，性能是一个重要考虑因素。 - Tom
今天关于算法的问题真是太多了！！！ - Pratik Deoghare
@Tom：也许你可以告诉我们找到最接近光标的点的目的。如果是为了用鼠标选择一个点，那么你可能只想在光标周围的指定区域内选择最近的点（例如，如果屏幕左上角只有一个点，而光标在右下角，你可能不想选择它）。 - Matthijs Wessels
那是正确的，它是用于使用鼠标选择点的，最终我还需要选择向量端点、线、弧等等... - Tom
7个回答
7
更新问题后
使用两个红黑树或跳表映射。两者都是紧凑的自平衡数据结构，可以在搜索、插入和删除操作中以 O(log n) 的时间复杂度运行。一个映射将每个点的 X 坐标作为键，点本身作为值；另一个映射将每个点的 Y 坐标作为键，点本身作为值。
作为权衡，建议最初通过正方形限制光标周围的搜索区域。对于完美匹配，正方形的边长应等于光标周围“敏感圆”的直径。例如，如果您只关心光标半径为 10 像素内的最近邻，则正方形的边长需要为 20px。或者，如果您想要最近邻而不考虑接近程度，可以通过相对于光标的 floor 和 ceiling 来动态查找边界。
然后从映射中检索出两个子集，这些子集在边界内，合并以仅包括两个子集中的点。
循环遍历结果，计算到每个点的接近程度（dx^2+dy^2，避免平方根，因为您只关心接近程度，而不是实际距离），找到最近的邻居。
从接近程度图中取根平方以测量到最近邻的距离，查看它是否大于“敏感圆”的半径，如果是，则表示圆内没有点。
建议对每个方法进行一些基准测试；优化很容易过头。在我的普通硬件（双核 2）上，Java 中一个最近邻搜索的单线程搜索重复 1000 次，耗时 350 毫秒。只要整体 UI 反应时间在 100 毫秒以下，对用户来说就会显得瞬间完成，记住即使是朴素搜索也可能给您足够快速的响应。
通用解决方案
最有效的数据结构取决于您计划使用的算法、时间空间权衡和预期的点的相对分布：
- 如果空间不是问题，最有效的方法可能是为屏幕上每个点预先计算最近的邻居，然后将最近的邻居唯一ID存储在表示屏幕的二维数组中。
- 如果时间不是问题，在简单的2D数组中存储10K个点并每次进行朴素搜索（即循环遍历每个点并计算距离）可能是一个好的简单易于维护的选择。
- 有许多权衡的选项，这里是关于各种最近邻搜索选项的良好演示：http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
- 一堆关于各种最近邻搜索算法的好详细材料：http://simsearch.yury.name/tutorial.html，只需选择最适合您需求的算法即可。
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
class Test
{
public static void main (String[] args)
{
Drawing naive = new NaiveDrawing();
Drawing skip = new SkipListDrawing();
long start;
start = System.currentTimeMillis();
testInsert(naive);
System.out.println("Naive insert: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testSearch(naive);
System.out.println("Naive search: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testInsert(skip);
System.out.println("Skip List insert: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testSearch(skip);
System.out.println("Skip List search: "+(System.currentTimeMillis() - start)+"ms");
}
public static void testInsert(Drawing d)
{
Random r = new Random();
for (int i=0;i<100000;i++)
d.addPoint(new Point(r.nextInt(4096),r.nextInt(2048)));
}
public static void testSearch(Drawing d)
{
Point cursor;
Random r = new Random();
for (int i=0;i<1000;i++)
{
cursor = new Point(r.nextInt(4096),r.nextInt(2048));
d.getNearestFrom(cursor,10);
}
}
}
// A simple point class
class Point
{
public Point (int x, int y)
{
this.x = x;
this.y = y;
}
public final int x,y;
public String toString()
{
return "["+x+","+y+"]";
}
}
// Interface will make the benchmarking easier
interface Drawing
{
void addPoint (Point p);
Set<Point> getNearestFrom (Point source,int radius);
}
class SkipListDrawing implements Drawing
{
// Helper class to store an index of point by a single coordinate
// Unlike standard Map it's capable of storing several points against the same coordinate, i.e.
// [10,15] [10,40] [10,49] all can be stored against X-coordinate and retrieved later
// This is achieved by storing a list of points against the key, as opposed to storing just a point.
private class Index
{
final private NavigableMap<Integer,List<Point>> index = new ConcurrentSkipListMap <Integer,List<Point>> ();
void add (Point p,int indexKey)
{
List<Point> list = index.get(indexKey);
if (list==null)
{
list = new ArrayList<Point>();
index.put(indexKey,list);
}
list.add(p);
}
HashSet<Point> get (int fromKey,int toKey)
{
final HashSet<Point> result = new HashSet<Point> ();
// Use NavigableMap.subMap to quickly retrieve all entries matching
// search boundaries, then flatten resulting lists of points into
// a single HashSet of points.
for (List<Point> s: index.subMap(fromKey,true,toKey,true).values())
for (Point p: s)
result.add(p);
return result;
}
}
// Store each point index by it's X and Y coordinate in two separate indices
final private Index xIndex = new Index();
final private Index yIndex = new Index();
public void addPoint (Point p)
{
xIndex.add(p,p.x);
yIndex.add(p,p.y);
}
public Set<Point> getNearestFrom (Point origin,int radius)
{
final Set<Point> searchSpace;
// search space is going to contain only the points that are within
// "sensitivity square". First get all points where X coordinate
// is within the given range.
searchSpace = xIndex.get(origin.x-radius,origin.x+radius);
// Then get all points where Y is within the range, and store
// within searchSpace the intersection of two sets, i.e. only
// points where both X and Y are within the range.
searchSpace.retainAll(yIndex.get(origin.y-radius,origin.y+radius));
// Loop through search space, calculate proximity to each point
// Don't take square root as it's expensive and really unneccessary
// at this stage.
//
// Keep track of nearest points list if there are several
// at the same distance.
int dist,dx,dy, minDist = Integer.MAX_VALUE;
Set<Point> nearest = new HashSet<Point>();
for (Point p: searchSpace)
{
dx=p.x-origin.x;
dy=p.y-origin.y;
dist=dx*dx+dy*dy;
if (dist<minDist)
{
minDist=dist;
nearest.clear();
nearest.add(p);
}
else if (dist==minDist)
{
nearest.add(p);
}
}
// Ok, now we have the list of nearest points, it might be empty.
// But let's check if they are still beyond the sensitivity radius:
// we search area we have evaluated was square with an side to
// the diameter of the actual circle. If points we've found are
// in the corners of the square area they might be outside the circle.
// Let's see what the distance is and if it greater than the radius
// then we don't have a single point within proximity boundaries.
if (Math.sqrt(minDist) > radius) nearest.clear();
return nearest;
}
}
// Naive approach: just loop through every point and see if it's nearest.
class NaiveDrawing implements Drawing
{
final private List<Point> points = new ArrayList<Point> ();
public void addPoint (Point p)
{
points.add(p);
}
public Set<Point> getNearestFrom (Point origin,int radius)
{
int prevDist = Integer.MAX_VALUE;
int dist;
Set<Point> nearest = Collections.emptySet();
for (Point p: points)
{
int dx = p.x-origin.x;
int dy = p.y-origin.y;
dist = dx * dx + dy * dy;
if (dist < prevDist)
{
prevDist = dist;
nearest = new HashSet<Point>();
nearest.add(p);
}
else if (dist==prevDist) nearest.add(p);
}
if (Math.sqrt(prevDist) > radius) nearest = Collections.emptySet();
return nearest;
}
}
- Vlad Gudim
5
循环遍历数组并检查坐标是否在灵敏度范围内，这样做的强度几乎与距离计算相同吗？每个点需要四个OR语句吗？ - Tom
距离计算包括两个乘法、加法和最昂贵的平方根（如果你只关心接近程度，可以避免使用）。每个点的比较可以达到四个AND操作，但大多数情况下你会用到更少的操作（因为如果第一个操作失败，其余操作将不会被执行等）。你还可以将这种“敏感性”方法与某种树索引相结合，具体取决于哪些操作需要更频繁地进行：点的重新排序或接近度检查。 - Vlad Gudim
我打算尝试跳表的方法，你的方法看起来很清晰易懂，谢谢。 - Tom
Tom刚刚在Java中实现了使用Java标准ConcurrentSkipListMap进行尝试，相同的测试（在10K个点内进行千次搜索）只需要大约60-70毫秒，即提高了5倍。你对这段代码感兴趣吗？ - Vlad Gudim
Totophil，是的，如果你提供的话，我会有兴趣看一下。性能真的很重要。我想我还需要存储一个单独的结构来确定哪些点与线连接以创建绘图。 - Tom
6
我建议创建一个 Voronoi 图 和一个 Trapezoidal Map（基本上是我给出 this 问题的相同 答案）。 Voronoi 图 将把空间划分为多边形。每个点都将有一个描述所有最接近它的点的多边形。 现在，当您得到一个点的查询时，您需要找出它位于哪个多边形中。这个问题被称为 Point Location，可以通过构建 Trapezoidal Map 来解决。
使用 Fortune's algorithm可以创建 Voronoi Diagram，它需要O(n log n)的计算步骤和O(n)的空间成本。 此网站向您展示如何制作梯形图并查询它。您还可以在那里找到一些限制:
- 预期创建时间：O(n log n)
- 预期空间复杂度：O(n) 但是
- 最重要的是，预期查询时间：O(log n)。
（理论上）这比kD-tree的O(√n)更好。 - 更新将是线性的（O(n)）我认为。
在那里，您将找到有关这两个数据结构的详细信息（包括详细证明）。 Google图书版本只有您需要的部分，但其他链接应该足以满足您的目的。如果您对这种事情感兴趣，只需购买这本书（它是一本好书）。
- Matthijs Wessels
4
我已经为问题添加了更多的上下文，这些点采用向量图形的形式，这个解决方案仍然适用吗？ - Tom
我已经删除了之前的评论，并在我的回答中添加了更新时间。我认为更新数据结构需要O(n)的时间。我仍然认为这对于响应用户交互是可以接受的。 - Matthijs Wessels
有一些算法可以对 Voronoi 图进行增量更新，每次更新只需要 O(log n) 的时间。http://www.springerlink.com/content/p8377h68j82l6860。 - Keith Randall
我此刻无法访问您提供的论文（我得去大学里），但我认为它并不仅涵盖任何更新。我认为它给出了一个O（log n）的平均更新时间来构建图表，从而导致总体构建时间为O（n log n）。对于常规更新，情况并非如此。以一组n个点全部位于圆上为例，在中间添加和删除一个点始终需要O（n）的时间，因为必须添加/删除O（n）条线段。 - Matthijs Wessels
5
最高效的数据结构应该是kd树。 链接
- DiggerMeUp
4
1我不明白为什么这个被投票赞成了，因为原帖写道：“这样用户就可以不断快速地更改它们”。KD树平衡将很快变成一场噩梦。 - MaR
@MaR 我同意重新平衡的需求可能是一个问题。我认为这里的教训是：1）如果新点的位置仍在同一区域内，则树不需要更改（每个节点只需要存储原始点和当前点）。2）每次只更改一个点，因此会有一个删除和一个插入。3）只有当矢量绘图被改变成完全不同的东西并且最近邻搜索的性能下降太多时，树才需要重新平衡。4）在二维中不是很重要。这需要测试。 - DiggerMeUp
@MaR - 另一个值得一提的观点是，Tom在我发布答案后添加了“以便用户可以不断快速地更改它们”的编辑，尽管我仍然认为围绕KD-Tree的变体可能最适合。 - DiggerMeUp
可能kd-tree的动态变体是最好的选择。例如，参见http://www.daimi.au.dk/~large/Papers/bkdsstd03.pdf。 - martinus
2
这些点是否均匀分布？
您可以建立一个四叉树，深度为8。在顶部，您有一个将屏幕分成四个象限的树节点。在每个节点上存储：
- 左上角和右下角坐标
- 指向四个子节点的指针，将节点分成四个象限
将树建立到深度为8的位置，并在叶节点中存储与该区域相关联的点列表。您可以线性地搜索该列表。
如果需要更细的粒度，则将四叉树构建到更大的深度。
- xcut
1
这听起来就像我想的那种东西，但是点不是均匀分布的，画布大小也是可变的... 这并不排除这种方法的可能性。 - Tom
1
这取决于更新和查询的频率。对于快速查询，慢速更新，Quadtree（一种二维jd-tree形式）可能是最好的选择。Quadtree非常适用于非均匀点。
如果您具有低分辨率，则可以考虑使用预先计算值的宽度x高度的原始数组。
如果您只有很少的点或快速更新，则简单的数组就足够了，或者可能是简单的分区（朝向四叉树）。
因此，答案取决于您动态参数。此外，我想补充说，现在算法并不是一切；使其使用多个处理器或CUDA可以大大提高性能。
- Wernight
0
您没有指定点的尺寸，但如果是2D线条绘图，则位图桶 - 一个区域中点的2D列表数组，其中您扫描与光标相对应且靠近的桶可以表现得非常好。大多数系统都可以轻松处理100x100到1000x1000的位图桶，其中最小的端点会在每个桶中放置一个点的平均值。虽然渐近性能为O（N），但实际性能通常非常好。将单个点移动到不同的桶之间可以很快；如果将对象放入桶而不是点，则也可以使对象的移动变得快速（因此，12个点的多边形将由12个桶引用；将其移动变为12倍的插入和删除成本；在2D数组中查找桶的时间是恒定的）。主要成本是在画布大小以许多小跳跃增长时重新组织所有内容。
- Pete Kirkham
0
如果是2D的话，你可以创建一个虚拟网格覆盖整个空间（宽度和高度取决于你实际点的空间），并找到属于每个单元格的所有2D点。之后，一个单元格将成为哈希表中的一个桶。
- D_K
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接