После обновления вопроса
Используйте две Красно-Черное Дерево или Skip_list карт. Оба являются компактными самобалансирующими структурами данных, дающими вам O (log n) время для операций поиска, вставки и удаления. Одна карта будет использовать X-координату для каждой точки в качестве ключа и саму точку в качестве значения, а другая будет использовать Y-координату в качестве ключа, а сама точка - в качестве значения.
В качестве компромисса я предлагаю изначально ограничить область поиска вокруг курсора квадратом. Для идеального соответствия сторона квадрата должна равняться диаметру вашего «круга чувствительности» вокруг курсора. То есть, если вас интересует только ближайший сосед в радиусе 10 пикселей от курсора, тогда сторона квадрата должна быть 20 пикселей. В качестве альтернативы , если вы ищете ближайшего соседа независимо от близости, вы можете попытаться найти границу динамически, оценивая пол и потолок относительно курсора.
Затем извлеките два подмножества точек из карт, находящихся в границах, объедините, чтобы включить только точки в оба подмножества.
Переберите результат, вычислите близость к каждой точке (dx ^ 2 + dy ^ 2, избегайте квадратного корня, поскольку вас не интересует фактическое расстояние, просто близость), найдите ближайшего соседа.
Возьмите корень квадратный из фигуры близости, чтобы измерить расстояние до ближайшего соседа, посмотрите, больше ли он радиуса «круга чувствительности», если он означает, что в круге нет точек.
Я предлагаю выполнить некоторые тесты для каждого подхода; это два легко пройти через оптимизацию. На моем скромном оборудовании (Duo Core 2) наивный однопоточный поиск ближайшего соседа в пределах 10 тысяч точек, повторяемый тысячу раз, занимает в Java 350 миллисекунд. Пока общее время реакции пользовательского интерфейса составляет менее 100 миллисекунд, оно будет казаться пользователю мгновенным, учитывая, что даже наивный поиск может дать вам достаточно быстрый ответ.
Универсальный раствор
Наиболее эффективная структура данных зависит от алгоритма, который вы планируете использовать, компромисса между временем и пространством и ожидаемого относительного распределения точек:
- Если пробел не является проблемой, наиболее эффективным способом может быть предварительный расчет ближайшего соседа для каждой точки на экране, а затем сохранение уникального идентификатора ближайшего соседа в двумерном массиве, представляющем экран.
- Если время не является проблемой, сохраняя 10K точек в простом двумерном массиве и выполняя простой поиск каждый раз, то есть цикл по каждой точке и вычисление расстояния может быть хорошим и простым и простым в обслуживании вариантом.
- Для ряда компромиссов между ними, вот хорошее представление о различных доступных вариантах поиска ближайшего соседа: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
- Куча хороших подробных материалов для различных алгоритмов поиска ближайших соседей: http://simsearch.yury.name/tutorial.html, просто выберите тот, который лучше всего соответствует вашим потребностям.
Таким образом, действительно невозможно оценить структуру данных, изолированную от алгоритма, который, в свою очередь, трудно оценить без хорошего представления об ограничениях и приоритетах задач.
Пример реализации Java
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;
}
}