将纬度和经度坐标分为顺时针有序的四边形 [英] Sort latitude and longitude coordinates into clockwise ordered quadrilateral

查看：446
本文介绍了将纬度和经度坐标分为顺时针有序的四边形的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

问题



用户可以按任意顺序提供最多四个纬度和经度坐标。他们使用Google地图进行操作。使用Google的 Polygon API（v3），它们选择的坐标应突出显示四个坐标之间的选定区域。



问题



你如何排列经纬度坐标数组（顺时针）？



解决方案和搜索

StackOverflow问题

b $ b

相关网站





已知算法


  • Graham扫描（太复杂）

  • Jarvis March算法（处理N个点）
  • 递归凸包（删除点）



C ode



以下是我到目前为止：

  //确保标记排序：NW，NE，SE，SW 
函数sortMarkers（）{
 var ns = markers.slice（0）; 
 var ew = markers.slice（0）; 
 
 ew.sort（函数（a，b）{
 if（a.position.lat（） return -1 ; 
} 
 else if（a.position.lat（）> b.position.lat（））{
 return 1; 
} 
 
返回0; 
}）; 
 
 ns.sort（function（a，b）{
 if（a.position.lng（） return -1 ; 
} 
 else if（a.position.lng（）> b.position.lng（））{
 return 1; 
} 
 
返回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]; 
} 
 
标记[0] = nw; 
标记[1] = ne; 
标记[2] = se; 
标记[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

？



如果这是正确的，这里有一个方法：


  • 在点集中找到最高点P top 。在平局的情况下，选择具有最小x坐标的点

  • 通过比较斜率m i 和m j 在通过P top 时，每对点（不包括P top ）P 如果m 和m 是相等的，那么让P 和 > i 或P j 最接近P top 先行

  • if m i 是正值且mj为负值（或零）时，如果两者都是m i ，则第一 sub>和m j 是正数或负数，让属于斜率最大的那一行的点先到达



以下是地图的快速演示：

（我知道JavaScript很少，所以我可能或者可能违反了一些JavaScript代码转换...）： 

  var points = [
 new Point（Stuttgard，48.7771056，9.1807688）， 
新点（鹿特丹，51.9226899,4.4707867），
新点（巴黎，48.8566667,2.3509871），
新点（汉堡，53.5538148,9.9915752），
新Point（Praha，50.0878114,14.4204598），
新点（阿姆斯特丹，52.3738007,4.8909347），
新点（Bremen，53.074981,8.807081），
新点（加来，50.9580293,1.8524129），
]; 
 var upper = upperLeft（points）; 
 
 print（points ::+ points）; 
 print（upper ::+ upper）; 
 points.sort（pointSort）; 
 print（sorted ::+ points）; 
 
 // 2D点的表示。 
函数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; 
返回dY / dX; 
} 
 
 this.toString = function（）{
 return this.label; 
 
 
 
 //一个自定义的排序函数，它根据它们的斜率
 //对p1和p2进行排序，这些函数是从数组的最高点形成的点。 
函数pointSort（p1，p2）{
 //排除排序中的'upper'点（应该先排列）。 
 if（p1 == upper）return -1; 
 if（p2 == upper）return 1; 
 
 //当通过'上'点从这些点中抽取一条线
 //时，找到'p1'和'p2'的斜率。 
 var m1 = upper.slope（p1）; 
 var m2 = upper.slope（p2）; 
 
 //'p1'和'p2'在'upper'的同一行上。 
 if（m1 == m2）{
 //最接近'upper'的点将首先出现。 
 return p1.distance（upper）< p2.distance（上）？ -1：1; 
} 
 
 //如果'p1'在'upper'的右边，'p2'在左边。如果（m1 <= 0&& m2> 0）返回-1，则
; 
 
 //如果'p1'在'upper'的左边，'p2'在右边。如果（m1> 0&< m2< = 0）返回1，
; 
 
 //看起来这两个斜坡都是正面的，或者是负面的。 
返回m1> m2？ -1：1; 
} 
 
 //找到最高点。在平局的情况下，得到最左边的点。 
函数upperLeft（points）{
 var top = points [0]; 
 for（var i = 1; 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 函数可能会返回最低点而不是最高点，具体取决于所讨论点的位置。再次：三重检查这些假设！



当执行上面的代码片段

a>，打印出以下内容：

 分数:: Stuttgard，鹿特丹，巴黎，汉堡，布拉格，阿姆斯特丹，不来梅，加来
 upper ::汉堡
已分类::汉堡，布拉格，斯图加特，巴黎，不来梅，加来，鹿特丹，阿姆斯特丹

交替距离函数 

 函数距离（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））; 
返回R * c; 
}


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.

Question

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

Solutions and Searches

StackOverflow Questions

Related Sites

Known Algorithms

  • Graham's scan (too complicated)
  • Jarvis March algorithm (handles N points)
  • 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.

解决方案

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, Ptop, in the set of points. In case of a tie, pick the point with the smallest x coordinate
  • sort all points by comparing the slopes mi and mj of the lines each pair of points (excluding Ptop!) Pi and Pj make when passing through Ptop
    • if mi and mj are equal, let the point Pi or Pj closest to Ptop come first
    • if mi is positive and mj is negative (or zero), Pj comes first
    • if both mi and mj are either positive or negative, let the point belonging to the line with the largest slope come first

Here's a quick demo for the map:

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

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!

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

这篇关于将纬度和经度坐标分为顺时针有序的四边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
前端开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆