将纬度和经度坐标分为顺时针有序的四边形
Dav*_*vis 32 javascript geometry coordinates grahams-scan
问题
用户可以按任何顺序提供最多四个纬度和经度坐标.他们使用谷歌地图.使用Google的PolygonAPI(v3),他们选择的坐标应突出显示四个坐标之间的选定区域.
题
如何按(逆时针)顺序排列纬度和经度坐标数组？
解决方案和搜索
StackOverflow问题
相关网站
- 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
已知算法
- 格雷厄姆的扫描(太复杂了)
- 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;
}
谢谢.
Bar*_*ers 39
鉴于要点:
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 顶部.如果是平局,请选择x坐标最小的点
- 通过比较线的斜率m i和m j对每个点进行排序每一对点(不包括P top!)P i和P j在通过P top时产生
- 如果m i和m j相等,则让最靠近P top的点P i或P j成为第一个
- 如果m i为正且m j为负(或为零),则P j为第一个
- 如果m i和m j都是正数或负数,则将属于具有最大斜率的线的点放在第一位
这是地图的快速演示:
(我知道很少的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;
}
算法思路：对四个点取平均值，得到多边形内的一个点。然后使用反三角函数计算该中心点和每个点之间的光线角度，如解释here。然后按角度排序。这应该给你一个（逆）顺时针排序，这取决于排序顺序和你认为的“零度”。
更新：这是一些代码。大多数未经测试，但它的想法。
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}逆时针排序点（像 的对象数组）。