Ordenar coordenadas de latitud y longitud en cuadrilátero ordenado en el sentido de las agujas del reloj

Dados los puntos:

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

Usted quiere encontrar la siguiente caminata encuadernada:

   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:

• encuentra el punto más alto, P _top, en el conjunto de puntos. En caso de empate, elija el punto con la coordenada x más pequeña
• ordenar todos los puntos comparando las pendientes m _i y m_j de las líneas de cada par de puntos (excluyendo P_top!) P_i and P_j make when pasando por P _top
  • si m_i y m_j son iguales, deje que el punto P_i o P_j más cercano a P_top venir primero
  • si m_i es positivo y m_j es negativo (o cero), P_j viene el primer
  • si tanto m _i como m_j son positivos o negativos, que el punto perteneciente a la línea con la pendiente más grande sea primero

Aquí hay una demostración rápida para el mapa:

(Sé poco JavaScript, así que podría, o probablemente haya violado algunas convenciones de código 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;
}

Nota: debería duplicar o triplicar las conversiones de lat,lon a x,y ya que soy un novato si se trata de SIG!!! Pero tal vez ni siquiera necesitas convertir nada. Si no lo hace, la función upperLeft podría devolver el punto más bajo en lugar del más alto, dependiendo de las ubicaciones de los puntos en cuestión. De nuevo: triple ¡comprueba estas suposiciones!

Cuando ejecuta el fragmento de código anterior, se imprime lo siguiente:

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

Función de Distancia Alterna

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