我有城市名称和GPS坐标的文本文件（UTF-8〜50K线）。 示例行：
San Pedro locality -3367 -5968 Argentina Buenos Aires San Pedro
Talagante locality -3366 -7093 Chile Metropolitana Talagante
Peñaflor locality -3362 -7092 Chile Metropolitana Talagante
第三和第四列是最后一列城市的GPS坐标。
给定一个坐标GPS，我需要找到衣柜里的城市。 我需要做的这数亿倍。 什么是一些工具，可以帮助我完成这个任务？ 的Java / Python的解决方案将是理想的。
你所寻找的是一个KD树 。 我发现了一个链接到一个Python实现它在这里，但我不Python开发，从来没有尝试过。 该KD树将寻找最近的点在一个平面上，这是也许你能得到的最好的复杂性平方根复杂性支持。 你能负担得起做大概一万次查询第二。
编辑：其实你的问题让我做一点更深入的研究。 也许正是被描述为在可能的方法，你会发现有用此页面 。 你感兴趣的是，对于近邻的许多查询提供最佳的解决方案。
我会在SQLite数据库中存储这些记录。 有一个名为项目SpatiaLite ，增加了空间查询和类型上的SQLite的顶部。 这使您可以问这样的“给20米x的范围内的所有项目”数据库的东西。
如果你不想使用一个数据库，你可以使用一个四叉树 。 在Python几种实现。 四叉树分割的矩形空间分成4个部分，然后每细分部分成4个更多部分。 搜索是非常有效的。
对于像你这样的几何查询请求（最近点）KD树是出色的数据结构。 除了不是非常艰难的实现。 我有一个Java实现。 不知道这将是多么高效为您服务。 这是我的任务。 Point2D和其他实用工具类实现此 。 您可以查看有其源代码。 RectHV需要另一个实用工具类。 这是我写的。
public class RectHV {
private final double xmin, ymin; // minimum x- and y-coordinates
private final double xmax, ymax; // maximum x- and y-coordinates
// construct the axis-aligned rectangle [xmin, xmax] x [ymin, ymax]
public RectHV(double xmin, double ymin, double xmax, double ymax) {
if (xmax < xmin || ymax < ymin) {
throw new IllegalArgumentException("Invalid rectangle");
}
this.xmin = xmin;
this.ymin = ymin;
this.xmax = xmax;
this.ymax = ymax;
}
// accessor methods for 4 coordinates
public double xmin() { return xmin; }
public double ymin() { return ymin; }
public double xmax() { return xmax; }
public double ymax() { return ymax; }
// width and height of rectangle
public double width() { return xmax - xmin; }
public double height() { return ymax - ymin; }
// does this axis-aligned rectangle intersect that one?
public boolean intersects(RectHV that) {
return this.xmax >= that.xmin && this.ymax >= that.ymin
&& that.xmax >= this.xmin && that.ymax >= this.ymin;
}
// draw this axis-aligned rectangle
public void draw() {
StdDraw.line(xmin, ymin, xmax, ymin);
StdDraw.line(xmax, ymin, xmax, ymax);
StdDraw.line(xmax, ymax, xmin, ymax);
StdDraw.line(xmin, ymax, xmin, ymin);
}
// distance from p to closest point on this axis-aligned rectangle
public double distanceTo(Point2D p) {
return Math.sqrt(this.distanceSquaredTo(p));
}
// distance squared from p to closest point on this axis-aligned rectangle
public double distanceSquaredTo(Point2D p) {
double dx = 0.0, dy = 0.0;
if (p.x() < xmin) dx = p.x() - xmin;
else if (p.x() > xmax) dx = p.x() - xmax;
if (p.y() < ymin) dy = p.y() - ymin;
else if (p.y() > ymax) dy = p.y() - ymax;
return dx*dx + dy*dy;
}
// does this axis-aligned rectangle contain p?
public boolean contains(Point2D p) {
return (p.x() >= xmin) && (p.x() <= xmax)
&& (p.y() >= ymin) && (p.y() <= ymax);
}
// are the two axis-aligned rectangles equal?
public boolean equals(Object y) {
if (y == this) return true;
if (y == null) return false;
if (y.getClass() != this.getClass()) return false;
RectHV that = (RectHV) y;
if (this.xmin != that.xmin) return false;
if (this.ymin != that.ymin) return false;
if (this.xmax != that.xmax) return false;
if (this.ymax != that.ymax) return false;
return true;
}
// return a string representation of this axis-aligned rectangle
public String toString() {
return "[" + xmin + ", " + xmax + "] x [" + ymin + ", " + ymax + "]";
}
}
这里是KD树：
public class KdTree {
private static class Node {
private Point2D p; // the point
private RectHV rect; // the axis-aligned rectangle corresponding to this node
private Node lb; // the left/bottom subtree
private Node rt; // the right/top subtree
Node() {
p = null;
rect = null;
lb = null;
rt = null;
}
}
private Node tree;
private Point2D nearestPoint, infinitePoint;
private int sz;
private double nearestDist;
// construct an empty set of points
public KdTree() {
tree = new Node();
sz = 0;
infinitePoint = new Point2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
// is the set empty?
public boolean isEmpty() {
return (sz == 0);
}
// number of points in the set
public int size() {
return sz;
}
////////////////////////////////////////////////
// private function for inserting any element //
////////////////////////////////////////////////
private void privateInsert( Node nd, Point2D p, int lv, double xmin, double ymin, double xmax, double ymax) {
if(nd.p == null) {
nd.p = p;
nd.rect = new RectHV(xmin, ymin, xmax, ymax);
nd.lb = new Node();
nd.rt = new Node();
sz = sz + 1;
}
else if( lv % 2 == 0 ) {
double X = nd.p.x();
double x = p.x();
if( x <= X ) {
xmax = X;
privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax);
}
else {
xmin = X;
privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax);
}
}
else {
double Y = nd.p.y();
double y = p.y();
if( y <= Y ) {
ymax = Y;
privateInsert(nd.lb, p, lv+1, xmin, ymin, xmax, ymax);
}
else {
ymin = Y;
privateInsert(nd.rt, p, lv+1, xmin, ymin, xmax, ymax);
}
}
}
////////////////////////////////////////////////
// private function for searching any element //
////////////////////////////////////////////////
private Node privateSearch( Node nd, Point2D p, int lv ) {
if( nd.p == null ) return nd;
else if( p.equals( nd.p ) == true ) return nd;
if(lv % 2 == 0) {
double X = nd.p.x();
double x = p.x();
if( x <= X ) {
return privateSearch( nd.lb, p, lv+1 );
}
else {
return privateSearch( nd.rt, p, lv+1);
}
}
else {
double Y = nd.p.y();
double y = p.y();
if( y <= Y ) {
return privateSearch(nd.lb, p, lv+1);
}
else {
return privateSearch(nd.rt, p, lv+1);
}
}
}
/////////////////////////////////////////////////
// private function for drawing all the points //
/////////////////////////////////////////////////
private void privateDraw (Node nd) {
if(nd.p == null) return;
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(.01);
double x = nd.p.x();
double y = nd.p.y();
StdDraw.point( x, y );
privateDraw( nd.lb );
privateDraw( nd.rt );
}
//////////////////////////////////////////
// private function for range searching //
//////////////////////////////////////////
private void privateRange(Node nd, RectHV rect, Queue<Point2D> que){
if(nd.p == null) return;
if( rect.contains( nd.p ) == true ) que.enqueue( nd.p );
if( nd.rect.intersects(rect) == true ) {
privateRange(nd.lb, rect, que);
privateRange(nd.rt, rect, que);
return;
}
else return;
}
//////////////////////////////////////////////////////
// private function for searching nearest neighbour //
//////////////////////////////////////////////////////
private void privateNearest( Node nd, Point2D p ) {
if(nd.p == null) return;
double d = p.distanceSquaredTo(nd.p);
if(d < nearestDist) {
nearestDist = d;
nearestPoint = nd.p;
}
if(nd.lb.p != null && ( nd.lb.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.lb, p);
if(nd.rt.p != null && ( nd.rt.rect.distanceSquaredTo(p) < nearestDist) ) privateNearest(nd.rt, p);
}
// add the point p to the set (if it is not already in the set)
public void insert(Point2D p) {
if( contains( p ) == true ) {
return;
}
else {
privateInsert(tree, p, 0, 0.00, 0.00, 1.00, 1.00);
}
}
// does the set contain the point p?
public boolean contains(Point2D p) {
Node nd = privateSearch(tree, p, 0);
if(nd.p == null) return false;
else return true;
}
// draw all of the points to standard draw
public void draw() {
privateDraw(tree);
}
// all points in the set that are inside the rectangle
public Iterable<Point2D> range( RectHV rect ) {
Queue<Point2D> que = new Queue<Point2D>();
privateRange(tree, rect, que);
return que;
}
// a nearest neighbor in the set to p; null if set is empty
public Point2D nearest(Point2D p) {
nearestPoint = infinitePoint;
nearestDist = Double.POSITIVE_INFINITY;
privateNearest(tree, p);
return nearestPoint;
//return p;
}
}
地理散列是给你的另一种选择，这是相当每一实施，高效快速。
