鉴于要点：
4 + [d] [g]
|
3 [a] [e]
|
2 + [f] [h]
|
1 + [b]
|
0 +----+---[c]---+----+----+----+
0 1 2 3 4 5 6
您想找到以下绑定步行：
4 + ___[d]------------[g]
| __/ \
3 [a]/ [e]__ \
| \ \_ ```--- \
2 + \ `[f] \___[h]
| \ __/
1 + [b] __/
| \ /
0 +----+--`[c]---+----+----+----+
0 1 2 3 4 5 6
?
如果这是正确的，这里有一个方法：
- 找到点集中的最高点 P top。在平局的情况下，选择 x 坐标最小的点
- 通过比较每对点的斜率 m i和 m j对所有点进行排序（不包括 P top！） P i和 P j在通过 P top时形成
- 如果 m i和 m j相等，让最接近 P top的点 P i或 P j先出现
- 如果 m i为正且 m j为负（或零），则 P j先出现
- 如果 m i和 m j都是正数或负数，则让属于斜率最大的线的点先出现
这是地图的快速演示：
（我对 JavaScript 知之甚少，所以我可能或可能已经违反了一些 JavaScript 代码约定......）：
var points = [
new Point("Stuttgard", 48.7771056, 9.1807688),
new Point("Rotterdam", 51.9226899, 4.4707867),
new Point("Paris", 48.8566667, 2.3509871),
new Point("Hamburg", 53.5538148, 9.9915752),
new Point("Praha", 50.0878114, 14.4204598),
new Point("Amsterdam", 52.3738007, 4.8909347),
new Point("Bremen", 53.074981, 8.807081),
new Point("Calais", 50.9580293, 1.8524129),
];
var upper = upperLeft(points);
print("points :: " + points);
print("upper :: " + upper);
points.sort(pointSort);
print("sorted :: " + points);
// A representation of a 2D Point.
function Point(label, lat, lon) {
this.label = label;
this.x = (lon + 180) * 360;
this.y = (lat + 90) * 180;
this.distance=function(that) {
var dX = that.x - this.x;
var dY = that.y - this.y;
return Math.sqrt((dX*dX) + (dY*dY));
}
this.slope=function(that) {
var dX = that.x - this.x;
var dY = that.y - this.y;
return dY / dX;
}
this.toString=function() {
return this.label;
}
}
// A custom sort function that sorts p1 and p2 based on their slope
// that is formed from the upper most point from the array of points.
function pointSort(p1, p2) {
// Exclude the 'upper' point from the sort (which should come first).
if(p1 == upper) return -1;
if(p2 == upper) return 1;
// Find the slopes of 'p1' and 'p2' when a line is
// drawn from those points through the 'upper' point.
var m1 = upper.slope(p1);
var m2 = upper.slope(p2);
// 'p1' and 'p2' are on the same line towards 'upper'.
if(m1 == m2) {
// The point closest to 'upper' will come first.
return p1.distance(upper) < p2.distance(upper) ? -1 : 1;
}
// If 'p1' is to the right of 'upper' and 'p2' is the the left.
if(m1 <= 0 && m2 > 0) return -1;
// If 'p1' is to the left of 'upper' and 'p2' is the the right.
if(m1 > 0 && m2 <= 0) return 1;
// It seems that both slopes are either positive, or negative.
return m1 > m2 ? -1 : 1;
}
// Find the upper most point. In case of a tie, get the left most point.
function upperLeft(points) {
var top = points[0];
for(var i = 1; i < points.length; i++) {
var temp = points[i];
if(temp.y > top.y || (temp.y == top.y && temp.x < top.x)) {
top = temp;
}
}
return top;
}
注意：如果涉及 GIS，您应该双重或三重检查从lat,lonto的转换，x,y因为我是新手！！！但也许你甚至不需要转换任何东西。如果不这样做，该upperLeft函数可能只返回最低点而不是最高点，具体取决于相关点的位置。再次：三重检查这些假设！
执行上面的代码片段时，将打印以下内容：
points :: Stuttgard,Rotterdam,Paris,Hamburg,Praha,Amsterdam,Bremen,Calais
upper :: Hamburg
sorted :: Hamburg,Praha,Stuttgard,Paris,Bremen,Calais,Rotterdam,Amsterdam
交替距离函数
function distance(lat1, lng1, lat2, lng2) {
var R = 6371; // km
var dLat = (lat2-lat1).toRad();
var dLon = (lng2-lng1).toRad();
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
return R * c;
}