Sau khi cập nhật cho câu hỏi
Sử dụng hai Red-Black Tree hoặc Skip_list bản đồ. Cả hai cấu trúc dữ liệu tự cân bằng nhỏ gọn đều cho bạn thời gian O (log n) để tìm kiếm, chèn và xóa các hoạt động. Một bản đồ sẽ sử dụng toạ độ X cho mọi điểm dưới dạng khóa và điểm chính nó dưới dạng giá trị và giá trị kia sẽ sử dụng toạ độ Y làm khóa và điểm chính là giá trị.
Như một sự cân nhắc, tôi đề xuất ban đầu hạn chế khu vực tìm kiếm xung quanh con trỏ bằng một hình vuông. Đối với kết hợp hoàn hảo, cạnh vuông phải bằng đường kính của "vòng tròn nhạy cảm" xung quanh con trỏ, tức là nếu bạn chỉ quan tâm đến một người hàng xóm gần nhất trong phạm vi bán kính 10 pixel từ con trỏ thì cạnh vuông phải là 20px. , nếu bạn là người hàng xóm gần nhất bất kể bạn ở gần bạn có thể thử tìm ranh giới động bằng cách đánh giá sàn và trần tương đối so với con trỏ.
Sau đó truy xuất hai tập con của các điểm từ bản đồ nằm trong ranh giới, hợp nhất để chỉ bao gồm các điểm trong cả hai tập con.
Lặp lại kết quả, tính khoảng cách đến mỗi điểm (dx^2 + dy^2, tránh căn bậc hai vì bạn không quan tâm đến khoảng cách thực, chỉ gần), tìm người hàng xóm gần nhất.
Lấy ô vuông từ hình gần để đo khoảng cách đến hàng xóm gần nhất, xem nếu nó lớn hơn bán kính của “vòng tròn nhạy cảm”, nếu nó có nghĩa là không có điểm nào trong vòng tròn.
Tôi khuyên bạn nên thực hiện một số tiêu chí chuẩn cho mọi cách tiếp cận; thật dễ dàng để vượt lên trên cùng với sự tối ưu hóa. Trên phần cứng khiêm tốn của tôi (Duo Core 2) tìm kiếm đơn luồng ngây thơ của một người hàng xóm gần nhất trong vòng 10 nghìn điểm lặp lại hàng nghìn lần mất 350 mili giây trong Java. Miễn là thời gian tái tạo giao diện người dùng tổng thể dưới 100 mili giây, nó sẽ có vẻ ngay lập tức đối với người dùng, hãy nhớ rằng ngay cả tìm kiếm ngây thơ có thể cung cấp cho bạn phản hồi đủ nhanh.
Generic Giải pháp
Cấu trúc dữ liệu hiệu quả nhất phụ thuộc vào các thuật toán bạn đang lập kế hoạch để sử dụng, buôn bán thời gian-không gian tắt và phân phối tương đối dự kiến điểm:
- Nếu không gian không phải là vấn đề, cách hiệu quả nhất có thể là tính toán trước hàng xóm gần nhất cho mỗi điểm trên màn hình và sau đó lưu trữ id hàng xóm gần nhất trong mảng hai chiều biểu diễn màn hình.
- Nếu thời gian không phải là vấn đề lưu trữ 10K điểm trong một mảng 2D đơn giản và thực hiện tìm kiếm ngây thơ mỗi lần, tức là lặp qua từng điểm và tính khoảng cách có thể là tùy chọn dễ bảo trì và đơn giản.
- Đối với một số thỏa hiệp giữa hai, đây là một bài thuyết trình tốt trên nhiều gần tùy chọn Neighbor Tìm kiếm có sẵn: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
- Một loạt các tài liệu chi tiết tốt cho gần các thuật toán Neighbor kiếm khác nhau: http://simsearch.yury.name/tutorial.html, chỉ cần chọn một trong đó phù hợp với nhu cầu của bạn nhất.
Vì vậy, thật sự không thể đánh giá cấu trúc dữ liệu được tách biệt khỏi thuật toán mà khó có thể đánh giá mà không có ý tưởng tốt về ràng buộc và ưu tiên của tác vụ.
Mẫu Java thực hiện
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;
}
}
Điều này có thể giúp: http://en.wikipedia.org/wiki/Nearest_neighbor_search – Aziz
Xác nhận rằng người dùng chỉ có thể sửa đổi điểm cuối của đoạn đường và số điểm là không đổi tại n (ví dụ: "10000"). Hầu hết các thuật toán cấu trúc dữ liệu được thiết kế để cung cấp bảo đảm hiệu suất tiệm cận cho việc sử dụng * chung *. – alphazero
Làm rõ, 10000 là số xấp xỉ để cho thấy rằng bản vẽ có thể lớn mà người dùng có thể thêm và xóa các dòng như mong muốn, tôi đang tìm cách tạo một chương trình vẽ vector đơn giản và hiệu suất là một cân nhắc chính. – Tom