javascript - 将纬度和经度坐标排序为顺时针有序四边形

问题

用户可以按任意顺序最多提供四个纬度和经度坐标。他们使用Google map 来做到这一点。使用Google的Polygon API(v3)，他们选择的坐标应突出显示四个坐标之间的选定区域。

问题

如何按(逆时针)顺序对经纬度坐标数组进行排序？

解决方案和搜索

StackOverflow问题

Drawing resizable (not intersecting) polygons

How to sort points in a Google maps polygon so that lines do not cross?

Sort Four Points in Clockwise Order

http://en.literateprograms.org/Quickhull_%28Javascript%29

http://www.geocodezip.com/map-markers_ConvexHull_Polygon.asp

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

已知算法

Graham的扫描(太复杂)

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;
}

谢谢你。

最佳答案

鉴于要点:

   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均为正或负，则让属于具有最大斜率线的点排在最前面

这是 map 的快速演示:

(我几乎不了解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;
}

注意:您应该仔细检查从lat,lon到x,y的转换，因为我是GIS的新手!但是也许您甚至不需要转换任何内容。如果不这样做，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;
}

关于javascript - 将纬度和经度坐标排序为顺时针有序四边形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2855189/