Classer les coordonnées de latitude et de longitude dans un quadrilatère ordonné dans le sens des aiguilles d'une montre

Question

Problème

Les utilisateurs peuvent fournir jusqu'à quatre coordonnées de latitude et de longitude, dans n'importe quel ordre. Ils le font avec Google Maps. En utilisant la fonction Polygon API (v3), les coordonnées sélectionnées doivent mettre en évidence la zone sélectionnée entre les quatre coordonnées.

Question

Comment trier un tableau de coordonnées de latitude et de longitude dans le sens (inverse) des aiguilles d'une montre ?

Solutions et recherches

Questions de StackOverflow

• Dessiner des polygones redimensionnables (sans intersection)
• Comment trier les points d'un polygone Google maps pour que les lignes ne se croisent pas ?
• Classer quatre points dans le sens des aiguilles d'une montre

Sites connexes

• 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

Algorithmes connus

• Scan de Graham (trop compliqué)
• Algorithme de Jarvis March (traite N points)
• Coque convexe récursive (enlève un point)

Code

Voici ce que j'ai pour l'instant :

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

Nous vous remercions.

Answer 1

Compte tenu des points :

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

vous voulez trouver la marche liée suivante :

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

?

Si c'est le cas, voici une solution :

• trouver le point le plus élevé, P _sommet dans l'ensemble des points. En cas d'égalité, on choisit le point dont la coordonnée x est la plus petite
• trier tous les points en comparant les pentes m _i et m _j des lignes chaque paire de points (à l'exclusion de P _sommet !) P _i et P _j en passant par P _sommet
  • si m _i et m _j sont égaux, laissez le point P _i ou P _j le plus proche de P _sommet venir en premier
  • si m _i est positif et m _j est négatif (ou nul), P _j vient en premier
  • si les deux m _i et m _j sont soit positives, soit négatives, le point appartenant à la droite ayant la plus grande pente vient en premier

Voici une démonstration rapide de la carte :

(Je connais peu JavaScript, il se peut donc que j'aie violé, ou probablement violé, certaines conventions du code 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 : vous devez vérifier deux ou trois fois les conversions de lat,lon a x,y car je suis un novice en matière de SIG ! Mais peut-être que vous n'avez même pas besoin de convertir quoi que ce soit. Si ce n'est pas le cas, le upperLeft peut renvoyer le point le plus bas au lieu du plus haut, en fonction de l'emplacement des points en question. Encore une fois, vérifiez ces hypothèses à trois reprises !

Lors de l'exécution de l'extrait ci-dessus, le texte suivant est imprimé :

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

Fonction de distance alternative

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

Idée d'algorithme : faire la moyenne des quatre points pour obtenir un point à l'intérieur du polygone. Ensuite, calculez l'angle du rayon entre ce point central et chaque point, en utilisant les fonctions trigonométriques inverses, comme expliqué ci-dessous. ici . Puis trier par angle. Vous devriez ainsi obtenir un classement dans le sens (inverse) des aiguilles d'une montre, en fonction de l'ordre de tri et de ce que vous considérez comme "zéro degré".

MISE À JOUR : voici un peu de code. Il n'a pas été testé, mais c'est l'idée.

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

Il trie les points (un tableau d'objets comme {x: 1, y: 1} ) dans le sens inverse des aiguilles d'une montre.

Answer 3

Pour ceux qui arrivent ici et qui ont un problème similaire un an plus tard :

Je ne suis pas d'accord avec la marche liée de la réponse choisie. Il n'y a pas de solution singulière à la commande, même avec une direction d'horloge donnée. L'enveloppe convexe des coordonnées données élimine les points e et f. Ceux-ci peuvent alors être attachés n'importe où le long du chemin. Objectivement, h,e,f,c peut être amélioré en h,f,e,c en gardant la direction de la composante x cohérente - dans ce cas, négative.

L'importance de ce phénomène fait qu'il est impossible de garantir l'inclusion de n'importe quel lieu de la carte dans la zone résultante délimitée par la marche choisie.