Javascript 将纬度和经度坐标排序为顺时针排序的四边形
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2855189/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sort latitude and longitude coordinates into clockwise ordered quadrilateral
提问by Dave Jarvis
Problem
问题
Users can provide up to four latitude and longitude coordinates, in any order. They do so with Google Maps. Using Google's PolygonAPI (v3), the coordinates they select should highlight the selected area between the four coordinates.
用户可以按任意顺序提供最多四个纬度和经度坐标。他们使用谷歌地图这样做。使用 Google 的PolygonAPI (v3)，他们选择的坐标应突出显示四个坐标之间的选定区域。
Question
题
How do you sort an array of latitude and longitude coordinates in (counter-)clockwise order?
如何按（逆）时针顺序对纬度和经度坐标数组进行排序？
Solutions and Searches
解决方案和搜索
StackOverflow Questions
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
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
- 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)
- Recursive Convex Hull (removes a point)
- 格雷厄姆的扫描（太复杂了）
- Jarvis March 算法（处理 N 个点）
- 递归凸包（删除一个点）
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.
谢谢你。
回答by Bart Kiers
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 miand mjof the lines each pair of points (excluding Ptop!) Piand Pjmake when passing through Ptop
- if miand mjare equal, let the point Pior Pjclosest to Ptopcome first
- if miis positive and mjis negative (or zero), Pjcomes first
- if both miand mjare either positive or negative, let the point belonging to the line with the largest slope come first
- 找到点集中的最高点 P top。在平局的情况下，选择具有最小 x 坐标的点
- 通过比较每对点（不包括 P top！）P i和 P j在通过 P top时产生的直线的斜率 m i和 m j对所有点进行排序
- 如果 m i和 m j相等，则让最靠近 P top的点 P i或 P j先到
- 如果 m i为正且 m j为负（或零），则 P j先出现
- 如果 m i和 m j都是正数或负数，让属于斜率最大的直线的点在前
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,lonto x,yas I am a novice if it comes to GIS!!! But perhaps you don't even need to convert anything. If you don't, the upperLeftfunction might just return the lowest point instead of the highest, depending on the locations of the points in question. Again: triple check these assumptions!
注意：如果涉及到 GIS ，您应该对从lat,lon到的转换进行两次或三次检查，x,y因为我是新手！！！但也许你甚至不需要转换任何东西。如果不这样做，该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;
}
回答by kevingessner
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".
算法思路：对四个点取平均值，得到多边形内的一个点。然后使用反三角函数计算该中心点和每个点之间的光线角度，如解释here。然后按角度排序。这应该给你一个（逆）顺时针排序，取决于排序顺序和你认为的“零度”。
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}逆时针排序点（像 的对象数组）。
回答by Adrian
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.
这样做的重要性使得无法保证在所选步行范围内的结果区域中包含任何地图位置。
