将纬度和经度坐标分为顺时针有序的四边形

Problem

Users can provide up to four latitude and longitude coordinates, in any order. They do so with Google Maps. Using Google's Polygon API (v3), the coordinates they select should highlight the selected area between the four coordinates.

用户可以按任何顺序提供最多四个纬度和经度坐标。他们使用谷歌地图。使用Google的Polygon API(v3),他们选择的坐标应突出显示四个坐标之间的选定区域。

Question

How do you sort an array of latitude and longitude coordinates in (counter-)clockwise order?

如何按(逆时针)顺序排列纬度和经度坐标数组?

Solutions and Searches

解决方案和搜索

* Questions

• Drawing resizable (not intersecting) polygons

绘制可调整大小(不相交)的多边形

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

如何对Google地图多边形中的点进行排序,以便线条不会交叉?

• Sort Four Points in Clockwise Order

按顺序排序四点

Related Sites

• http://www.daftlogic.com/projects-google-maps-area-calculator-tool.htm
• 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

Known Algorithms

• Graham's scan (too complicated)

格雷厄姆的扫描(太复杂了)

• Jarvis March algorithm (handles N points)

Jarvis March算法(处理N点)

• Recursive Convex Hull (removes a point)

递归凸壳(删除一个点)

Code

Here is what I have so far:

这是我到目前为止:

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

Thank you.

3 个解决方案

#1

Given the points:

鉴于要点:

   4  +        [d]            [g]                 
      |                             
   3 [a]            [e]                 
      |                             
   2  +                  [f]       [h]    
      |                             
   1  +   [b]                             
      |                             
   0  +----+---[c]---+----+----+----+
      0    1    2    3    4    5    6

you want to find the following bound walk:

你想找到以下绑定步行:

   4  +     ___[d]------------[g]                 
      |  __/                     \    
   3 [a]/           [e]__         \       
      | \             \_ ```---    \  
   2  +  \              `[f]   \___[h]    
      |   \           __/            
   1  +   [b]      __/                   
      |      \    /                
   0  +----+--`[c]---+----+----+----+
      0    1    2    3    4    5    6

?

If this is correct, here's a way:

如果这是正确的,这是一种方式:

• find the upper most point, P_top, in the set of points. In case of a tie, pick the point with the smallest x coordinate

在点集中找到最高点Ptop。如果是平局,请选择x坐标最小的点

• sort all points by comparing the slopes m_i and m_j of the lines each pair of points (excluding P_top!) P_i and P_j make when passing through P_top
  • if m_i and m_j are equal, let the point P_i or P_j closest to P_top come first

  如果mi和mj相等,则让Pi或Pj最接近Ptop

  • if m_i is positive and m_j is negative (or zero), P_j comes first

  如果mi为正且mj为负(或为零),则Pj首先出现

  • if both m_i and m_j are either positive or negative, let the point belonging to the line with the largest slope come first

  如果mi和mj都是正数或负数,则让属于具有最大斜率的线的点首先出现

通过比较每对点(不包括Ptop!)Pi和Pj的线的斜率mi和mj对所有点进行排序,如果mi和mj相等,则通过Ptop时,如果mi,则最接近Ptop的点Pi或Pj首先出现是正的,mj是负的(或零),如果mi和mj都是正数或负数,则Pj首先出现,让属于具有最大斜率的线的点首先出现

Here's a quick demo for the map:

这是地图的快速演示:

(I know little JavaScript, so I might, or probably have, violated some JavaScript code conventions...):

(我知道很少的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;
}

Note: your should double, or triple check the conversions from lat,lon to x,y as I am a novice if it comes to GIS!!! But perhaps you don't even need to convert anything. If you don't, the upperLeft function might just return the lowest point instead of the highest, depending on the locations of the points in question. Again: triple check these assumptions!

注意:你应该加倍或三倍检查从lat,lon到x,y的转换,因为我是新手,如果涉及到GIS!但也许你甚至不需要转换任何东西。如果不这样做,则upperLeft函数可能只返回最低点而不是最高点,具体取决于所讨论的点的位置。再次:三重检查这些假设!

When executing the snippet above, the following gets printed:

执行上面的代码段时,会打印以下代码:

points :: Stuttgard,Rotterdam,Paris,Hamburg,Praha,Amsterdam,Bremen,Calais
upper  :: Hamburg
sorted :: Hamburg,Praha,Stuttgard,Paris,Bremen,Calais,Rotterdam,Amsterdam

Alternate Distance Function

替代距离函数

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

#2

Algorithm idea: average the four points to get a point inside the polygon. Then calculate the angle of the ray between that center point and each point, using inverse trigonometric functions, like explained here. Then sort by the angles. That should give you a (counter-)clockwise ordering, depending on the sort order and what you consider "zero degrees".

算法思路:平均四个点以获得多边形内的一个点。然后使用反三角函数计算该中心点与每个点之间的光线角度,如此处所述。然后按角度排序。这应该给你一个(反)顺时针顺序,取决于排序顺序和你认为“零度”。

UPDATE: here's some code. Mostly untested, but it's the idea.

更新:这是一些代码。大多数未经测试,但这是主意。

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

It sorts points (an array of objects like {x: 1, y: 1}) counter-clockwise.

它逆时针对点(像{x:1,y:1}的对象数组)进行排序。

#3

For those arriving here having a similar problem a year later:

对于那些一年后来到这里有类似问题的人:

I do not agree with the chosen answer's bound walk. There is no singular solution to the order even with a given clock direction. The convex hull of the given coordinates eliminates points e and f. These can then be attached anywhere along the path. Objectively, h,e,f,c can be improved to h,f,e,c keeping the direction of the x component consistent - in this case, negative.

我不同意所选答案的约束行走。即使使用给定的时钟方向,也没有单一的解决方案。给定坐标的凸包消除了点e和f。然后可以将它们连接到路径的任何位置。客观上,h,e,f,c可以改进为h,f,e,c,保持x分量的方向一致 - 在这种情况下为负。

The significance of this makes it impossible to guarantee the inclusion of any map location in the resulted area bounded by the chosen walk.

这一点的重要性使得无法保证在由所选步行限定的结果区域中包含任何地图位置。