我正在努力开发一款应用程序，它不仅可以根据像我一样从A到B的人，而且即使我正在从别人的A到B。
例如，如果有人搜索从泽西海岸到曼哈顿的骑行路线，并且有很多骑行路线在那里附近行驶，我需要一个算法来计算谁离这个人最近。这很有挑战性，因为我不是在搜索到某个点的距离，而是在搜索到一条路线的距离(例如，司机最初可能输入了他从华盛顿特区到曼哈顿的路线)
谷歌地图API很好，但我需要一个算法/程序，可以解决节点到边缘的距离，可能还有一个先进的GIS系统。
有人知道我在哪里可以找到这方面的工作吗？
您可以尝试一些空间数据结构，例如四叉树、r-trees、delaunay三角测量：查找图中最近的边。
由于您没有提到您正在使用的技术，我无法了解具体细节，但以下是一些可以帮助您入门的东西/库：
-
API：
- JTS(Java拓扑套件)：包含查找点和线之间距离的函数，以及加快搜索附近线(R树、四叉树…)的数据结构
- NetTopologySuite:JTS的.NET端口，对于.NET还有DotSpattial API
- geos:JTS的C++端口
- Python有Shapely、RTree
-
各种数据库都有空间扩展，但有两个值得注意的是：
- PostgreSQL与PostGIS，例如索引最近邻搜索
- 带有Spatialite的SqlLite(特别容易上手)
如果您在Windows上工作，还可以看看OSGeo4W，它是各种程序和库的方便安装程序。
请注意，还有一个stackexchange站点专门用于GIS。
您可以从您的点到代表他人路径的行字符串的"距离"开始。您可以使用Samuel提到的技术来实现这一点，也可以编写自己的代码。对于LineString上的距离测试，可以将其分解为两个问题。查找线段和点之间的最短距离。然后对字符串中的每个线段重复该测试。这里发布的代码是简单的暴力测试，不试图做任何优化，但除非你要处理数百万条路径，否则你可能不必这样做。在这种情况下，一些简单的扩展测试或R-树可以通过缩小测试路径来帮助优化。此外，这里的代码是用Java编写的，但应该足够简单，可以很容易地翻译成其他语言。
查找点到段距离的段代码：
/**
* Gets the closest point that is on the segment to the specified point, which
* can be anywhere.
* @param point The point to get the closest point to.
* @return The Coordinate closest to the specified point.
*/
public Coord closestPointTo(Coord point)
{
EndPointInteraction endPointFlag = EndPointInteraction.OnLine;
return closestPointTo(point, false, endPointFlag);
}
/**
* Gets the closest point the the specified point, given information about
* whether the line is allowed to be infinite or not.
* @param point The point to find the closest point to.
* @param isInfiniteLine boolean. If this is true, the segment is treated as if
* it defines an infinite line.
* @param endPointFlag This contains extra information about whether the point
* is past the start or end of the segment or whether the segment is degenerate.
* @return The Coordinate that is the closest point on the line to the specified point.
*/
public Coord closestPointTo(Coord point, boolean isInfiniteLine,
EndPointInteraction endPointFlag) {
// If the points defining this segment are the same, we treat the segment as a point
// special handling to avoid 0 in denominator later
if (P2.X == P1.X && P2.Y == P1.Y) {
endPointFlag = EndPointInteraction.P1equalsP2;
return P1;
}
//http://softsurfer.com/Archive/algorithm_0102/algorithm_0102.htm
Vector v = toVector(); // vector from p1 to p2 in the segment
v.Z = 0;
Vector w = new Vector(P1, point); // vector from p1 to Point
w.Z = 0;
double c1 = w.dot(v); // the dot product represents the projection onto the line
if (c1 < 0) {
endPointFlag = EndPointInteraction.PastP1;
if (!isInfiniteLine) // The closest point on the segment to Point is p1
{
return P1;
}
}
double c2 = v.dot(v);
if (c2 <= c1) {
endPointFlag = EndPointInteraction.PastP2;
if (!isInfiniteLine) // The closest point on the segment to Point is p2
{
return P2;
}
}
// The closest point on the segment is perpendicular to the point,
// but somewhere on the segment between P1 and P2
endPointFlag = EndPointInteraction.OnLine;
double b = c1 / c2;
v = v.multiply(b);
Coord pb = new Coord(P1.X + v.X, P1.Y + v.Y);
return pb;
}
/**
* Gets the minimum distance to the specified coordinate.
* @param point The point to get the distance from this segment to.
* @return The double distance.
*/
public double distanceTo(Coord point)
{
return closestPointTo(point).distance(point);
}
LineString(或任何有坐标列表的零件)代码，用于在分段中循环以获得距离：
/**
* Gets the minimum distance to an edge of the part. This does not consider whether the point
* is inside the part or not.
* @param coordinate
* @return
*/
public double distance(Coord coordinate)
{
List<Segment> segs = this.getSegments();
double minDist = Double.MAX_VALUE;
for(Segment seg : segs)
{
double dist = seg.distanceTo(coordinate);
if(dist < minDist)
{
minDist = dist;
}
}
return minDist;
}
/**
* Generates a set of segments that represent this part.
* @return
*/
public List<Segment> getSegments()
{
List<Segment> result = new ArrayList<Segment>();
if(getCoordinates().size() < 2) {
return result;
}
for(int i = 0; i < getCoordinates().size()-1; i++)
{
result.add(new Segment(getCoordinates().get(i), getCoordinates().get(i+1)));
}
if(closed)
{
result.add(new Segment(getCoordinates().get(getCoordinates().size()-1), getCoordinates().get(0)));
}
return result;
}