logo标签列表

将纬度和经度坐标按顺时针排序为四边形。

javascriptgeometrycoordinatesgrahams-scan
36

问题

用户可以提供最多四个纬度和经度坐标，任意顺序。他们使用 Google Maps 提供这些坐标。使用 Google 的 Polygon API（v3），他们选择的坐标应该突出显示所选区域。

问题

如何按(逆)时针顺序排序一个纬度和经度坐标数组？

解决方法和搜索

StackOverflow问题

相关网站

已知算法

  • Graham's scan (过于复杂)
  • Jarvis March 算法（处理 N 个点）
  • 递归凸包（删除一个点）

代码

这是我目前的代码：

// Ensures the markers are sorted: NW, NE, SE, SW
function sortMarkers() {
  var ns = markers.slice( 0 );
  var ew = markers.slice( 0 );

  ew.sort( function( a, b ) {
    if( a.position.lat() < b.position.lat() ) {
      return -1;
    }
    else if( a.position.lat() > b.position.lat() ) {
      return 1;
    }

    return 0;
  });

  ns.sort( function( a, b ) {
    if( a.position.lng() < b.position.lng() ) {
      return -1;
    }
    else if( a.position.lng() > b.position.lng() ) {
      return 1;
    }

    return 0;
  });

  var nw;
  var ne;
  var se;
  var sw;

  if( ew.indexOf( ns[0] ) > 1 ) {
    nw = ns[0];
  }
  else {
    ne = ns[0];
  }

  if( ew.indexOf( ns[1] ) > 1 ) {
    nw = ns[1];
  }
  else {
    ne = ns[1];
  }

  if( ew.indexOf( ns[2] ) > 1 ) {
    sw = ns[2];
  }
  else {
    se = ns[2];
  }

  if( ew.indexOf( ns[3] ) > 1 ) {
    sw = ns[3];
  }
  else {
    se = ns[3];
  }

  markers[0] = nw;
  markers[1] = ne;
  markers[2] = se;
  markers[3] = sw;
}

谢谢您。

3个回答
45

给定如下点：

   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

如果这是正确的话，这里是一种方法：

  • 找到点集中最上面的点Ptop。如果有多个点满足条件，则选择x坐标最小的点
  • 通过比较每对点（不包括Ptop！）Pi和Pj在通过Ptop时形成的直线斜率mi和mj来排序所有点
    • 如果mi和mj相等，则让距离Ptop更近的点Pi或Pj先出现
    • 如果mi为正数且mj为负数（或零），则Pj先出现
    • 如果mi和mj都是正数或负数，则让属于斜率最大的直线的点先出现

这是一个关于地图的快速演示：

enter image description here

(我知道很少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,lon到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;
}
这是一个很棒的解决方案，但也许我对原问题有些困惑。假设按顺时针方向，似乎不应该出现布雷梅。我本来期望的排序应该是：汉堡、布拉格、斯图加特、巴黎、加莱、鹿特丹、阿姆斯特丹、不来梅。 - Public Profile
@Jon Stevens，不，它按照预期进行排序。可以这样想：将一根绳子系在顶部城市（汉堡）上，并在末端挂上一个小重物。将重物拖到最右边，使绳子变直，然后放开重物。绳子通过城市的顺序是正确的排序顺序。希望有所帮助。 - Bart Kiers
Bart，我理解那一部分，但从你的 ASCII 地图来看，排序顺序似乎更符合那个。此外，最初的要求是按（逆）时针方向。不一定基于字符串/绳索。 - Public Profile
@Jon Stevens，不，ASCII映射也是这样排序的，d位于顶部，其次是g，h，e，f，c，b，a。原始要求并不是非常精确：OP还提到了“凸包”，但那与此无关。我知道的是，OP说：“...正是我想要实现的”，并接受了这个答案作为正确的答案。 - Bart Kiers
7
算法思想：求多边形内部任意一点，将四个顶点坐标平均后求出中心点。然后计算该中心点与各个点之间的夹角，使用反三角函数计算，如这里所解释的那样。最后按照角度排序，就可以获得（逆）时针方向的顺序了，具体取决于排序顺序以及你认为的“零度”是什么。
更新： 以下是一些代码，主要是算法思路，尚未经过充分测试。
function sorted_points(points) {
    points = points.slice(0); // copy the array, since sort() modifies it
    var stringify_point = function(p) { return p.x + ',' + p.y; };

    // finds a point in the interior of `pts`
    var avg_points = function(pts) {
        var x = 0;
        y = 0;
        for(i = 0; i < pts.length; i++) {
            x += pts[i].x;
            y += pts[i].y;
        }
        return {x: x/pts.length, y:y/pts.length};
    }
    var center = avg_points(points);

    // calculate the angle between each point and the centerpoint, and sort by those angles
    var angles = {};
    for(i = 0; i < points.length; i++) {
        angles[stringify_point(points[i])] = Math.atan(points[i].x - center.x, points[i].y - center.y);
    }
    points.sort(function(p1, p2) {
        return angles[stringify_point(p1)] - angles[stringify_point(p2)];
    });
    return points;
}

它按逆时针顺序排序点（一个类似于{x: 1, y: 1}的对象数组）。

真棒，如此简单和美好。 - Tran Quan
我不了解你的代码，但是这个算法是正确的答案 - 对于四点组成的四边形来说，这显然是正确的，正如原帖所要求的。这应该被提升为正确答案。 - cbn
对于一些真实世界的区域来说，平均的x/y坐标（或经纬度）并不在多边形内部。最近遇到一个情况，该区域大致呈弧形（类似于车轮边缘的四分之一），计算出的“中心点”并不在形状内部。 - undefined
1

对于那些在一年后遇到类似问题的人：

我不同意所选择答案的边界行走。即使在给定的时钟方向下，也没有单一的解决方案来确定顺序。 给定坐标的凸包消除了点e和f。然后可以将它们附加在路径的任何位置。 客观地说，h，e，f，c可以改进为h，f，e，c，保持x分量方向一致-在这种情况下，为负。

这个意义使得不可能保证任何地图位置都包含在所选择的行走所限定的区域内。

唯一保证包含性的方法是创建一个带有最外层点的多边形，选择该形状中的两个点并缩进该行以循环遍历次外层点，并递归重复该过程。你最终得到的形状类似于迷宫。但是，OP的复杂度并不是很大。他们建议使用4个点，我们知道4个点始终是四边形，无论这些点在哪里。因此，给定的解决方案将起作用。 - Lee Louviere
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接