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

Luego de investigar con expertos en este tema, programadores de deferentes áreas y maestros hemos dado con la respuesta a la interrogande y la dejamos plasmada en este post.

Solución:

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 el siguiente paseo enlazado:

   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 alto, P_cima, 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 cada par de puntos (excluyendo P_cima!) PAGS_I y P_j hacer al pasar por P_cima
  • si m_I y M_j son iguales, sea el punto P_I o P_j más cercano a P_cima ven 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 positivos o negativos, deje que el punto perteneciente a la línea con la mayor pendiente sea el primero

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

(Conozco poco JavaScript, por lo que podría, o probablemente haya violado, algunas convenciones del 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++) 
    return top;

Nota: debe verificar dos o tres veces las conversiones de lat,lon para x,y como soy un novato si se trata de GIS!!! Pero tal vez ni siquiera necesite convertir nada. Si no lo hace, el upperLeft la función podría devolver el punto más bajo en lugar del más alto, dependiendo de las ubicaciones de los puntos en cuestión. Nuevamente: ¡verifique tres veces estas suposiciones!

Al ejecutar el fragmento 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 alternativa

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;

Idea de algoritmo: promediar los cuatro puntos para obtener un punto dentro del polígono. Luego calcula el ángulo del rayo entre ese punto central y cada punto, usando funciones trigonométricas inversas, como se explica aquí. 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 considere "cero grados".

ACTUALIZACIÓN: aquí hay algo de código. Mayormente sin probar, 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 los puntos (un array de objetos como x: 1, y: 1) en sentido anti-horario.

Comentarios y puntuaciones del tutorial

Si para ti ha sido de provecho este post, sería de mucha ayuda si lo compartes con el resto entusiastas de la programación y nos ayudes a dar difusión a nuestra información.

---

---

Utiliza Nuestro Buscador