我必须从地图上的不同标记到设备当前位置的距离，然后选择最短的。我有标记的纬度和经度，并且可以动态获取当前位置经度和经度。
假设我在地图上有 5 个标记，班加罗尔（纬度：12.971599，经度：77.594563），德里（纬度：28.635308，经度：77.224960），孟买（纬度：19.075984，经度：72.877656），钦奈（纬度 414，经度：13.052） 80.250825），加尔各答（纬度：22.572646，经度：88.363895）。
现在假设用户站在海得拉巴附近的某个地方（纬度：17.385044，经度：78.486671）。当用户单击按钮时，应用程序应计算与每个标记的距离并拾取并返回最短的一个，即此处的班加罗尔。
有一种方法可以在本地数据库的帮助下完成。有人可以帮忙吗？
任何人都可以建议我一个很好的方法来做到这一点，或者如果可以的话，请提供一个好的代码。提前谢谢。
从您的评论中，我看到您预计最多有 70-80 个地点。这并不多。
您可以简单地对所有标记进行蛮力搜索并取最小值。
遍历所有标记，并搜索最小距离：
List<Marker> markers = createMarkers(); // returns an ArrayList<Markers> from your data source
int minIndex = -1;
double minDist = 1E38; // initialize with a huge value that will be overwritten
int size = markers.size();
for (int i = 0; i < size; i++) {
Marker marker = markers.get(i);
double curDistance = calcDistance(curLatitude, curLongitude, marker.latitude, marker.longitude);
if (curDistance < minDist) {
minDist = curDistance; // update neares
minIndex = i; // store index of nearest marker in minIndex
}
}
if (minIndex >= 0) {
// now nearest maker found:
Marker nearestMarker = markers.get(minIndex);
// TODO do something with nearesr marker
} else {
// list of markers was empty
}
对于calcDistance，使用android提供的距离计算方法。（例如Location.distanceTo()）
对于 70-80 个标记，无需使其更快和更复杂。如果您有数千个点，那么值得投资于更快的解决方案（使用空间索引和避免 sqrt 计算的自己的距离计算）。
只需在最近的制造商搜索开始和结束时以毫秒为单位打印当前时间，您就会发现它已经足够快了。
如何遍历所有标记并使用检查距离Location.distanceBetween？没有魔法;)
List<Marker> markers;
LatLng currentPosition;
float minDistance = Float.MAX_VALUE;
Marker closest = null;
float[] currentDistance = new float[1];
for (Marker marker : markers) {
LatLng markerPosition = marker.getPosition();
Location.distanceBetween(currentPosition.latitude, currentPosition.longitude, markerPosition.latitude, markerPosition.longitude, currentDistance);
if (minDistance > currentDistance[0]) {
minDistance = currentDistance[0];
closest = marker;
}
}
If you want to find the shortest one not list the closest and you want the process to scale to a large amount of locations, you can do some filtering before you calculate distances and you can simplify the formula to speed it up as you don't care about actual distances (i.e. remove the multiplication by the radius of the earth).
Filtering algorithm, looping through each location :
You can further help the algorithm by feeding it with what might be close locations first. For example if you know one of the points is in the same country or state.
Here is some Python code to do that, use it as pseudocode for your solution :
locations = {
'Bangalore' : (12.971599, 77.594563),
'Delhi' : (28.635308, 77.224960),
'Mumbai' : (19.075984, 72.877656),
'Chennai' : (13.052414, 80.250825),
'Kolkata' : (22.572646, 88.363895)
}
from math import sin, cos, atan2, sqrt
EARTH_RADIUS = 6373 # km
def distance(a, b): # pass tuples
(lat1, lon1) = a
(lat2, lon2) = b
dlon = lon2 - lon1
dlat = lat2 - lat1
a = (sin(dlat/2))**2 + cos(lat1) * cos(lat2) * (sin(dlon/2))**2
c = 2 * atan2( sqrt(a), sqrt(1-a) )
return EARTH_RADIUS * c
current = (17.385044, 78.486671) # current lat & lng
closest = None
closest_name = None
for name, cordinates in locations.iteritems():
d = distance(current, cordinates)
if closest is None or d < closest:
closest = d
closest_name = name
print "~%dkm (%s)" % (distance(current, cordinates), name)
print "\nClosest location is %s, %d km away." % (closest_name, closest)
Output :
~5700km (Kolkata)
~13219km (Chennai)
~12159km (Bangalore)
~7928km (Delhi)
~10921km (Mumbai)
Closest location is Kolkata, 5700 km away.
虽然已经发布了一些答案，但我想我会在 java 中展示我的实现。这已与包装在 AsyncTask 中的 4000 多个标记一起使用，并且一直在正常工作。
首先，计算距离的逻辑（假设您只有标记而不是 Location 对象，因为它们提供了执行 loc1.distanceTo(loc2) 的可能性）：
private float distBetween(LatLng pos1, LatLng pos2) {
return distBetween(pos1.latitude, pos1.longitude, pos2.latitude,
pos2.longitude);
}
/** distance in meters **/
private float distBetween(double lat1, double lng1, double lat2, double lng2) {
double earthRadius = 3958.75;
double dLat = Math.toRadians(lat2 - lat1);
double dLng = Math.toRadians(lng2 - lng1);
double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
+ Math.cos(Math.toRadians(lat1))
* Math.cos(Math.toRadians(lat2)) * Math.sin(dLng / 2)
* Math.sin(dLng / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
double dist = earthRadius * c;
int meterConversion = 1609;
return (float) (dist * meterConversion);
}
接下来是选择最近标记的代码：
private Marker getNearestMarker(List<Marker> markers,
LatLng origin) {
Marker nearestMarker = null;
double lowestDistance = Double.MAX_VALUE;
if (markers != null) {
for (Marker marker : markers) {
double dist = distBetween(origin, marker.getPosition());
if (dist < lowestDistance) {
nearestMarker = marker;
lowestDistance = dist;
}
}
}
return nearestMarker;
}
也许与您的用例无关，但我使用该算法根据预定义的距离选择最近的标记。这样我清除了很多不必要的标记：
private List<Marker> getSurroundingMarkers(List<Marker> markers,
LatLng origin, int maxDistanceMeters) {
List<Marker> surroundingMarkers = null;
if (markers != null) {
surroundingMarkers = new ArrayList<Marker>();
for (Marker marker : markers) {
double dist = distBetween(origin, marker.getPosition());
if (dist < maxDistanceMeters) {
surroundingMarkers.add(marker);
}
}
}
return surroundingMarkers;
}
希望这可以帮助你
这是我所谓的 KDTree 的实现，它由 3 个类组成：KDTree、KDTNode 和 KDTResult。您最终需要的是使用 KDTree.createTree() 创建 KDTree，它返回树的 rootNode 并获取传入的所有固定点。然后使用 KDTree.findNearestWp() 找到离给定位置最近的 Waypoint。
KD树：
public class KDTree {
private Comparator<LatLng> latComparator = new LatLonComparator(true);
private Comparator<LatLng> lonComparator = new LatLonComparator(false);;
/**
* Create a KDTree from a list of Destinations. Returns the root-node of the
* tree.
*/
public KDTNode createTree(List<LatLng> recList) {
return createTreeRecursive(0, recList);
}
/**
* Traverse the tree and find the nearest WP.
*
* @param root
* @param wp
* @return
*/
static public LatLng findNearestWp(KDTNode root, LatLng wp) {
KDTResult result = new KDTResult();
findNearestWpRecursive(root, wp, result);
return result.nearestDest;
}
private static void findNearestWpRecursive(KDTNode node, LatLng wp,
KDTResult result) {
double lat = wp.latitude;
double lon = wp.longitude;
/* If a leaf node, calculate distance and return. */
if (node.isLeaf) {
LatLng dest = node.wp;
double latDiff = dest.latitude - lat;
double lonDiff = dest.longitude - lon;
double squareDist = latDiff * latDiff + lonDiff * lonDiff;
// Replace a previously found nearestDest only if the new one is
// nearer.
if (result.nearestDest == null
|| result.squareDistance > squareDist) {
result.nearestDest = dest;
result.squareDistance = squareDist;
}
return;
}
boolean devidedByLat = node.depth % 2 == 0;
boolean goLeft;
/* Check whether left or right is more promising. */
if (devidedByLat) {
goLeft = lat < node.splitValue;
} else {
goLeft = lon < node.splitValue;
}
KDTNode child = goLeft ? node.left : node.right;
findNearestWpRecursive(child, wp, result);
/*
* Check whether result needs to be checked also against the less
* promising side.
*/
if (result.squareDistance > node.minSquareDistance) {
KDTNode otherChild = goLeft ? node.right : node.left;
findNearestWpRecursive(otherChild, wp, result);
}
}
private KDTNode createTreeRecursive(int depth, List<LatLng> recList) {
KDTNode node = new KDTNode();
node.depth = depth;
if (recList.size() == 1) {
// Leafnode found
node.isLeaf = true;
node.wp = recList.get(0);
return node;
}
boolean divideByLat = node.depth % 2 == 0;
sortRecListByDimension(recList, divideByLat);
List<LatLng> leftList = getHalfOf(recList, true);
List<LatLng> rightList = getHalfOf(recList, false);
// Get split point and distance to last left and first right point.
LatLng lastLeft = leftList.get(leftList.size() - 1);
LatLng firstRight = rightList.get(0);
double minDistanceToSplitValue;
double splitValue;
if (divideByLat) {
minDistanceToSplitValue = (firstRight.latitude - lastLeft.latitude) / 2;
splitValue = lastLeft.latitude + Math.abs(minDistanceToSplitValue);
} else {
minDistanceToSplitValue = (firstRight.longitude - lastLeft.longitude) / 2;
splitValue = lastLeft.longitude + Math.abs(minDistanceToSplitValue);
}
node.splitValue = splitValue;
node.minSquareDistance = minDistanceToSplitValue
* minDistanceToSplitValue;
/** Call next level */
depth++;
node.left = createTreeRecursive(depth, leftList);
node.right = createTreeRecursive(depth, rightList);
return node;
}
/**
* Return a sublist representing the left or right half of a List. Size of
* recList must be at least 2 !
*
* IMPORTANT !!!!! Note: The original list must not be modified after
* extracting this sublist, as the returned subList is still backed by the
* original list.
*/
List<LatLng> getHalfOf(List<LatLng> recList, boolean leftHalf) {
int mid = recList.size() / 2;
if (leftHalf) {
return recList.subList(0, mid);
} else {
return recList.subList(mid, recList.size());
}
}
private void sortRecListByDimension(List<LatLng> recList, boolean sortByLat) {
Comparator<LatLng> comparator = sortByLat ? latComparator
: lonComparator;
Collections.sort(recList, comparator);
}
class LatLonComparator implements Comparator<LatLng> {
private boolean byLat;
public LatLonComparator(boolean sortByLat) {
this.byLat = sortByLat;
}
@Override
public int compare(LatLng lhs, LatLng rhs) {
double diff;
if (byLat) {
diff = lhs.latitude - rhs.latitude;
} else {
diff = lhs.longitude - rhs.longitude;
}
if (diff > 0) {
return 1;
} else if (diff < 0) {
return -1;
} else {
return 0;
}
}
}
}
KDT节点：
/** Node of the KDTree */
public class KDTNode {
KDTNode left;
KDTNode right;
boolean isLeaf;
/** latitude or longitude of the nodes division line. */
double splitValue;
/** Distance between division line and first point. */
double minSquareDistance;
/**
* Depth of the node in the tree. An even depth devides the tree in the
* latitude-axis, an odd depth devides the tree in the longitude-axis.
*/
int depth;
/** The Waypoint in case the node is a leaf node. */
LatLng wp;
}
KDT结果：
/** Holds the result of a tree traversal. */
public class KDTResult {
LatLng nearestDest;
// I use the square of the distance to avoid square-root operations.
double squareDistance;
}
请注意，我正在使用简化的距离计算，这适用于我的情况，因为我只对非常附近的航点感兴趣。对于相距较远的点，这可能会导致不完全是最近的点。以米为单位的东西距离表示的两个经度的绝对差值取决于测量该差值的纬度。在我的算法中没有考虑到这一点，我不确定这种效果在你的情况下的相关性。
我认为将我的 KDTree（参见我的其他答案）也扩展到 3 维版本应该不会太难，这就是结果。但由于我自己目前还没有使用这个版本，所以要小心。我添加了一个单元测试，这表明它至少适用于您的示例。
/** 3 dimensional implementation of a KDTree for LatLng coordinates. */
public class KDTree {
private XYZComparator xComparator = new XYZComparator(0);
private XYZComparator yComparator = new XYZComparator(1);
private XYZComparator zComparator = new XYZComparator(2);
private XYZComparator[] comparators = { xComparator, yComparator,
zComparator };
/**
* Create a KDTree from a list of lat/lon coordinates. Returns the root-node
* of the tree.
*/
public KDTNode createTree(List<LatLng> recList) {
List<XYZ> xyzList = convertTo3Dimensions(recList);
return createTreeRecursive(0, xyzList);
}
/**
* Traverse the tree and find the point nearest to wp.
*/
static public LatLng findNearestWp(KDTNode root, LatLng wp) {
KDTResult result = new KDTResult();
XYZ xyz = convertTo3Dimensions(wp);
findNearestWpRecursive(root, xyz, result);
return result.nearestWp;
}
/** Convert lat/lon coordinates into a 3 dimensional xyz system. */
private static XYZ convertTo3Dimensions(LatLng wp) {
// See e.g.
// http://stackoverflow.com/questions/8981943/lat-long-to-x-y-z-position-in-js-not-working
double cosLat = Math.cos(wp.latitude * Math.PI / 180.0);
double sinLat = Math.sin(wp.latitude * Math.PI / 180.0);
double cosLon = Math.cos(wp.longitude * Math.PI / 180.0);
double sinLon = Math.sin(wp.longitude * Math.PI / 180.0);
double rad = 6378137.0;
double f = 1.0 / 298.257224;
double C = 1.0 / Math.sqrt(cosLat * cosLat + (1 - f) * (1 - f) * sinLat
* sinLat);
double S = (1.0 - f) * (1.0 - f) * C;
XYZ result = new XYZ();
result.x = (rad * C) * cosLat * cosLon;
result.y = (rad * C) * cosLat * sinLon;
result.z = (rad * S) * sinLat;
result.wp = wp;
return result;
}
private List<XYZ> convertTo3Dimensions(List<LatLng> recList) {
List<XYZ> result = new ArrayList<KDTree.XYZ>();
for (LatLng latLng : recList) {
XYZ xyz = convertTo3Dimensions(latLng);
result.add(xyz);
}
return result;
}
private static void findNearestWpRecursive(KDTNode node, XYZ wp,
KDTResult result) {
/* If a leaf node, calculate distance and return. */
if (node.isLeaf) {
double xDiff = node.xyz.x - wp.x;
double yDiff = node.xyz.y - wp.y;
double zDiff = node.xyz.z - wp.z;
double squareDist = xDiff * xDiff + yDiff * yDiff + zDiff * zDiff;
// Replace a previously found nearestDest only if the new one is
// nearer.
if (result.nearestWp == null || result.squareDistance > squareDist) {
result.nearestWp = node.xyz.wp;
result.squareDistance = squareDist;
}
return;
}
int devidedByDimension = node.depth % 3;
boolean goLeft;
/* Check whether left or right is more promising. */
if (devidedByDimension == 0) {
goLeft = wp.x < node.splitValue;
} else if (devidedByDimension == 1) {
goLeft = wp.y < node.splitValue;
} else {
goLeft = wp.z < node.splitValue;
}
KDTNode child = goLeft ? node.left : node.right;
findNearestWpRecursive(child, wp, result);
/*
* Check whether result needs to be checked also against the less
* promising side.
*/
if (result.squareDistance > node.minSquareDistance) {
KDTNode otherChild = goLeft ? node.right : node.left;
findNearestWpRecursive(otherChild, wp, result);
}
}
private KDTNode createTreeRecursive(int depth, List<XYZ> recList) {
KDTNode node = new KDTNode();
node.depth = depth;
if (recList.size() == 1) {
// Leafnode found
node.isLeaf = true;
node.xyz = recList.get(0);
return node;
}
int dimension = node.depth % 3;
sortWayPointListByDimension(recList, dimension);
List<XYZ> leftList = getHalfOf(recList, true);
List<XYZ> rightList = getHalfOf(recList, false);
// Get split point and distance to last left and first right point.
XYZ lastLeft = leftList.get(leftList.size() - 1);
XYZ firstRight = rightList.get(0);
double minDistanceToSplitValue;
double splitValue;
if (dimension == 0) {
minDistanceToSplitValue = (firstRight.x - lastLeft.x) / 2;
splitValue = lastLeft.x + Math.abs(minDistanceToSplitValue);
} else if (dimension == 1) {
minDistanceToSplitValue = (firstRight.y - lastLeft.y) / 2;
splitValue = lastLeft.y + Math.abs(minDistanceToSplitValue);
} else {
minDistanceToSplitValue = (firstRight.z - lastLeft.z) / 2;
splitValue = lastLeft.z + Math.abs(minDistanceToSplitValue);
}
node.splitValue = splitValue;
node.minSquareDistance = minDistanceToSplitValue
* minDistanceToSplitValue;
/** Call next level */
depth++;
node.left = createTreeRecursive(depth, leftList);
node.right = createTreeRecursive(depth, rightList);
return node;
}
/**
* Return a sublist representing the left or right half of a List. Size of
* recList must be at least 2 !
*
* IMPORTANT !!!!! Note: The original list must not be modified after
* extracting this sublist, as the returned subList is still backed by the
* original list.
*/
List<XYZ> getHalfOf(List<XYZ> xyzList, boolean leftHalf) {
int mid = xyzList.size() / 2;
if (leftHalf) {
return xyzList.subList(0, mid);
} else {
return xyzList.subList(mid, xyzList.size());
}
}
private void sortWayPointListByDimension(List<XYZ> wayPointList, int sortBy) {
XYZComparator comparator = comparators[sortBy];
Collections.sort(wayPointList, comparator);
}
class XYZComparator implements Comparator<XYZ> {
private int sortBy;
public XYZComparator(int sortBy) {
this.sortBy = sortBy;
}
@Override
public int compare(XYZ lhs, XYZ rhs) {
double diff;
if (sortBy == 0) {
diff = lhs.x - rhs.x;
} else if (sortBy == 1) {
diff = lhs.y - rhs.y;
} else {
diff = lhs.z - rhs.z;
}
if (diff > 0) {
return 1;
} else if (diff < 0) {
return -1;
} else {
return 0;
}
}
}
/** 3 Dimensional coordinates of a waypoint. */
static class XYZ {
double x;
double y;
double z;
// Keep also the original waypoint
LatLng wp;
}
/** Node of the KDTree */
public static class KDTNode {
KDTNode left;
KDTNode right;
boolean isLeaf;
/** latitude or longitude of the nodes division line. */
double splitValue;
/** Distance between division line and first point. */
double minSquareDistance;
/**
* Depth of the node in the tree. Depth 0,3,6.. devides the tree in the
* x-axis, depth 1,4,7,.. devides the tree in the y-axis and depth
* 2,5,8... devides the tree in the z axis.
*/
int depth;
/** The Waypoint in case the node is a leaf node. */
XYZ xyz;
}
/** Holds the result of a tree traversal. */
static class KDTResult {
LatLng nearestWp;
// We use the square of the distance to avoid square-root operations.
double squareDistance;
}
}
这是单元测试：
public void testSOExample() {
KDTree tree = new KDTree();
LatLng Bangalore = new LatLng(12.971599, 77.594563);
LatLng Delhi = new LatLng(28.635308, 77.224960);
LatLng Mumbai = new LatLng(19.075984, 72.877656);
LatLng Chennai = new LatLng(13.052414, 80.250825);
LatLng Kolkata = new LatLng(22.572646, 88.363895);
List<LatLng> cities = Arrays.asList(new LatLng[] { Bangalore, Delhi,
Mumbai, Chennai, Kolkata });
KDTree.KDTNode root = tree.createTree(cities);
LatLng Hyderabad = new LatLng(17.385044, 78.486671);
LatLng nearestWp = tree.findNearestWp(root, Hyderabad);
assertEquals(nearestWp, Bangalore);
}
在这里，我有一种方法可以使用数据库。这是一个计算距离函数：
public void calculateDistance() {
if (latitude != 0.0 && longitude != 0.0) {
for(int i=0;i<97;i++) {
Location myTargetLocation=new Location("");
myTargetLocation.setLatitude(targetLatitude[i]);
myTargetLocation.setLongitude(targetLongitude[i]);
distance[i]=myCurrentLocation.distanceTo(myTargetLocation);
distance[i]=distance[i]/1000;
mdb.insertDetails(name[i],targetLatitude[i], targetLongitude[i], distance[i]);
}
Cursor c1= mdb.getallDetail();
while (c1.moveToNext()) {
String station_name=c1.getString(1);
double latitude=c1.getDouble(2);
double longitude=c1.getDouble(3);
double dis=c1.getDouble(4);
//Toast.makeText(getApplicationContext(),station_name+" & "+latitude+" & "+longitude+" & "+dis,1).show();
}
Arrays.sort(distance);
double nearest_distance=distance[0];
Cursor c2=mdb.getNearestStationName();
{
while (c2.moveToNext()) {
double min_dis=c2.getDouble(4);
if(min_dis==nearest_distance)
{
String nearest_stationName=c2.getString(1);
if(btn_clicked.equals("source"))
{
source.setText(nearest_stationName);
break;
}
else if(btn_clicked.equals("dest"))
{
destination.setText(nearest_stationName);
break;
}
else
{
}
}
}
}
}
else
{
Toast.makeText(this, "GPS is Not Working Properly,, please check Gps and Wait for few second", 1).show();
}
}
我们所要做的就是创建一个名为 targetLatitude[i] 和 targetLongitude[i] 的数组，其中包含您要计算距离的所有地点的纬度和经度。然后创建一个数据库，如下图：
public class MyDataBase {
SQLiteDatabase sdb;
MyHelper mh;
MyDataBase(Context con)
{
mh = new MyHelper(con, "Metro",null, 1);
}
public void open() {
try
{
sdb=mh.getWritableDatabase();
}
catch(Exception e)
{
}
}
public void insertDetails(String name,double latitude,double longitude,double distance) {
ContentValues cv=new ContentValues();
cv.put("name", name);
cv.put("latitude", latitude);
cv.put("longitude",longitude);
cv.put("distance", distance);
sdb.insert("stations", null, cv);
}
public void insertStops(String stop,double latitude,double logitude)
{
ContentValues cv=new ContentValues();
cv.put("stop", stop);
cv.put("latitude", latitude);
cv.put("logitude", logitude);
sdb.insert("stops", null, cv);
}
public Cursor getallDetail()
{
Cursor c=sdb.query("stations",null,null,null,null,null,null);
return c;
}
public Cursor getNearestStationName() {
Cursor c=sdb.query("stations",null,null,null,null,null,null);
return c;
}
public Cursor getStops(String stop)
{
Cursor c;
c=sdb.query("stops",null,"stop=?",new String[]{stop},null, null, null);
return c;
}
class MyHelper extends SQLiteOpenHelper
{
public MyHelper(Context context, String name, CursorFactory factory,
int version) {
super(context, name, factory, version);
// TODO Auto-generated constructor stub
}
@Override
public void onCreate(SQLiteDatabase db) {
// TODO Auto-generated method stub
db.execSQL("Create table stations(_id integer primary key,name text," +
" latitude double, longitude double, distance double );");
db.execSQL("Create table stops(_id integer primary key,stop text," +
"latitude double,logitude double);");
}
@Override
public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {
// TODO Auto-generated method stub
}
}
public void deleteDetail() {
sdb.delete("stations",null,null);
sdb.delete("stops",null,null);
}
public void close() {
sdb.close();
}
}
然后在任何你想要的地方执行CalculateDistance函数，你可以获得最近的车站名称。
在二维中搜索单个点（可能经常变化）和大量点之间的最小距离的一种有效方法是使用QuadTree。最初构建 QuadTree 是有成本的（即，将标记位置添加到数据结构中），因此您只想执行一次（或尽可能不频繁地执行此操作）。但是，一旦构造完成，搜索最近点通常会比对大集合中的所有点进行蛮力比较更快。
BBN 的 OpenMap 项目有一个开源的 QuadTree Java 实现，我相信它应该可以在 Android 上运行，它有一种get(float lat, float lon)返回最近点的方法。
Google 的 android-maps-utils 库也有一个 QuadTree 的开源实现，旨在在 Android 上运行，但目前编写它只支持返回给定边界框中的一组点的search(Bounds bounds)操作，而不是点最接近输入点。但是，可以对其进行修改以执行最近点搜索。
如果您的点数相对较少（70-80 可能足够小），那么在实际性能中，蛮力比较可能会在与 QuadTree 解决方案类似的时间内执行。但是，这也取决于您打算重新计算最近点的频率 - 如果频繁，QuadTree 可能是更好的选择。