Ordenar latitud y longitud coordenadas en sentido horario ordenado cuadrilátero

Question

Problema

Los usuarios pueden proporcionar hasta cuatro coordenadas de latitud y longitud, en cualquier orden. Lo hacen con Google Maps. Utilizando la API de Google Polygon (v3), las coordenadas que seleccionen deberían resaltar el área seleccionada entre las cuatro coordenadas.

Pregunta

¿Cómo ordenar un conjunto de coordenadas de latitud y longitud en (en sentido contrario) orden a la derecha?

Soluciones y Búsquedas

Stackoverflow Preguntas

• 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

Sitios Relacionados

• 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

algoritmos conocidos

• exploración de Graham (demasiado complicado) algoritmo
• Jarvis marzo (maneja N puntos)
• recursiva Convex Hull (elimina un punto)

Código

Aquí es lo que tengo hasta ahora:

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

Gracias yo tú

Answer 1

Dados los puntos:

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

desea encontrar los siguientes pasos cota:

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

?

Si esto es correcto, aquí hay una manera:

• encontrar el punto más superior, P _superior, en el conjunto de puntos. En caso de empate, recoger el punto con el más pequeño coordenada x
• tipo todos los puntos mediante la comparación de las pistas de m _i y m _j de las líneas de cada par de puntos (excluyendo P _superior!) P _i y P _j maquillaje cuando pasa a través de P _superior
  • si m _i y m _j son iguales, dejar que el punto P _i o P _j más cercana a P _superior venga primero
  • si m _i es positivo y m _j es negativo (o cero), P _j viene primero
  • si ambos m _i y m _j son ya sea positivo o negativo, que el punto que pertenece a la línea con la pendiente más grande venga primero

He aquí una demostración rápida para el mapa:

(yo sé poco de JavaScript, por lo que podría, o probablemente, violado algún código JavaScript convenciones ...):

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

Nota: su doble, o triple verificar las conversiones de lat,lon a x,y ya que soy un novato si se trata de GIS! Pero tal vez ni siquiera necesites convertir nada. Si no lo hace, la función upperLeft puede devolver el punto más bajo en lugar del más alto, según la ubicación de los puntos en cuestión. De nuevo: ¡comprueba tres veces estas suposiciones!

Cuando executing the snippet above, se imprime el siguiente:

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

Distancia alternativo Función

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

Answer 2

Idea de algoritmo: promedie los cuatro puntos para obtener un punto dentro del polígono. Luego calcule el ángulo del rayo entre ese punto central y cada punto, usando funciones trigonométricas inversas, como se explica en here. Luego ordena por los ángulos. Eso debería darle un orden (en sentido contrario a las agujas del reloj), según el orden de clasificación y lo que considera "cero grados".

ACTUALIZACIÓN: aquí hay algunos códigos. Mayormente no probado, pero es la 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; 
} 

ordena puntos (una matriz de objetos como {x: 1, y: 1}) en sentido antihorario.

Answer 3

Para los que llegan aquí con un problema similar un año más tarde:

no lo hago de acuerdo con la caminata de la respuesta elegida. No hay una solución única para la orden incluso con una dirección de reloj dada. El casco convexo de las coordenadas dadas elimina los puntos e y f. Estos se pueden unir en cualquier lugar a lo largo del camino. Objetivamente, h, e, f, c se puede mejorar a h, f, e, c manteniendo constante la dirección del componente x; en este caso, negativo.

La importancia de esto hace que sea imposible garantizar la inclusión de cualquier ubicación del mapa en el área resultante delimitada por la caminata elegida.