tìm điểm gần nhất của Gps tới vị trí người dùng trong danh sách

Question

những gì tôi đang cố gắng thực hiện: người dùng chọn bắt đầu và đích trên bản đồ và sau đó từ tọa độ của họ tôi muốn hiển thị vị trí điểm gần nhất từ ​​danh sách vị trí trên bản đồ . tôi có một cơ sở dữ liệu Sqlite đơn giản chứa kinh độ, vĩ độ và tên của các vị trí có thể.

tôi đã làm một số nghiên cứu và đây là những gì tôi tìm thấy:

http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

nhưng điều này có nghĩa là để sử dụng nó với MySQL và một số loại phần mở rộng tìm kiếm không gian. là có khả năng tôi có thể làm điều gì đó tương tự bằng cách sử dụng api android hoặc libs bên ngoài?

public Point dialogFindClosestLocationToPoint(geometry.Point aStartPoint){ 
List<PointWithDistance> helperList=new ArrayList<PointWithDistance>(); 
try { 
openDataBase(); 
Cursor c=getCursorQueryWithAllTheData(); 
if(c.moveToFirst()) 
do{ 
    PointWithDistance helper=new PointWithDistance(c.getDouble(1),c.getDouble(2),c.getString(3)); 
    int distance=returnDistanceBetween2Points(aStartPoint, helper); 
    if(distance<MAX_SEARCH_DISTANCE){ 
    helper.setDistance(distance); 
    Log.i("values", helper.name); 
    helperList.add(helper); 
    } 
}while (c.moveToNext()); 
Collections.sort(helperList,new PointComparator()); 

if(helperList!=null) 
return helperList.get(0); 
else return null; 
}catch(SQLException sqle){ 

throw sqle; 

} 
finally{ 
close(); 
} 

đây là mã trong() lớp PointComparator:

public int compare(PointWithDistance o1, PointWithDistance o2) { 
    return (o1.getDistance()<o2.getDistance() ? -1 : (o1.getDistance()==o2.getDistance() ? 0 : 1)); 
} 

nơi PointWithDistance là một đối tượng có chứa: lat, dài, khoảng cách, tên

tuy nhiên giải pháp này không cung cấp thông tin trả về đúng ... và tôi nhận ra rằng nó không có khả năng mở rộng và rất chậm. tôi cần một giải pháp mà sẽ thực thi nhanh chóng với một cơ sở dữ liệu với tối đa 1000 hàng.

chỉnh sửa: tôi đã có một sai lầm trong mã này trong sắp xếp bây giờ tôi có nó thay đổi (nên < thay vì>)

Answer 1

tôi đang tìm kiếm một cái gì đó rất giống một số thời gian trước đây:

Android sqlite sort on calculated column (co-ordinates distance)

Tôi đã sử dụng một tra cứu MySQL trên máy chủ của tôi, MySQL cho phép bạn tạo ra một cột ảo, thực hiện các tính toán và các loại theo khoảng cách , và sau đó bạn có thể thiết lập các kết quả tối đa trả lại hoặc khoảng cách tối đa - nó hoạt động rất tốt:

Select Lat, Lon, acos(sin($lat)*sin(radians(Lat)) + cos($lat)*cos(radians(Lat))cos(radians(Lon)-$lon))$R As dist From MyTable ORDER BY dist DESC 

tôi muốn thực hiện các hoạt động tương tự trong ứng dụng của tôi - kéo tất cả các điểm để tách từ về vị trí người dùng cho phép tôi hiển thị những cái gần nhất.Tôi đã kết thúc với một giải pháp dọc theo dòng của một trong những đề nghị trên liên kết ở trên nhưng nhận ra nó có lẽ không phải là giải pháp tối ưu nhưng làm việc cho mục đích tôi muốn.

Answer 2

tôi đã không cố gắng chạy mã của bạn, nhưng nó có vẻ như nó sẽ làm việc , nó chỉ là nó không hiệu quả. như bạn không thực sự cần phải sắp xếp, bạn cần giải nén tối thiểu.

bạn có thể giới hạn truy vấn của mình chỉ với hình vuông có kích thước (2 * MAX_SEARCH_DISTANCE)^2 (với điểm của bạn ở giữa. Bằng cách này bạn đang bản địa hóa truy vấn của mình và sẽ trả về kết quả ít hơn để tính toán khoảng cách . (? có lẽ khó xảy ra). cho Tất nhiên điều này sẽ không giúp đỡ nếu tất cả các địa điểm bạn đang ở quảng trường cục bộ

Ngoài ra, tôi cho rằng bạn có thể sử dụng khoảng cách Hamiltonian thay vì Euclide Euclide khoảng cách = sqrt ((lat0. - lat1)^2 + (lon0 - lon1)^2) khoảng cách hamitonian = (lat0 - lat1) + (lon0 - lon1)

Answer 3

Thi s loại điều được thực hiện hiệu quả nhất bằng cách sử dụng một R-Tree. JSI library cung cấp triển khai Java mà tôi đã sử dụng thành công với chỉ mục 80.000 vị trí, xử lý hàng nghìn lần tra cứu mỗi giây. Tuy nhiên, nó có thể không chạy trên Android.