Sortieren Breiten- und Längenkoordinaten in Uhrzeigerrichtung geordnete Viereck

Question

Problem

Benutzer bis zu vier Breiten- und Längenkoordinaten, in beliebiger Reihenfolge zur Verfügung stellen können. Sie tun dies mit Google Maps. Mit der Google-API Polygon (v3) sollten die ausgewählten Koordinaten den ausgewählten Bereich zwischen den vier Koordinaten markieren.

Frage

Wie sortieren Sie eine Reihe von Breiten- und Längenkoordinaten in (Gegen-) Uhrzeigersinn?

Lösungen und Suchen

Stackoverflow Fragen

• 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

Verwandte Seiten

• 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

Bekannte Algorithmen

• Grahams Scan (zu kompliziert)
• Jarvis March-Algorithmus (Griffe N Punkte)
• rekursive Convex Hull (entfernt einen Punkt)

-Code

Hier ist, was ich habe so weit:

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

Vielen Dank u.

Answer 1

Angesichts der Punkte:

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

Sie folgende Schranke zu Fuß finden wollen:

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

?

Wenn dies richtig ist, hier ist ein Weg:

• den obersten Punkt finden, P _oben, in der Menge von Punkten. Im Fall eines Gleichstands holt den Punkt mit dem kleinsten x
• sortiert alle Koordinatenpunkte durch die Steigungen m _i und m Vergleich _j der Linien jedes Paar von Punkten (mit Ausnahme von P _oben!) P _i und P _j machen, wenn die durch P _oben
  • wenn m _i und m _j gleich sind, lassen Sie den Punkt P _i oder P _j am nächsten P _oben kommen zuerst
  • wenn m _i positiv ist, und m _j negativ (oder Null), P _j ersten i
  • wenn sowohl m _kommt und m _j sind entweder positiv oder negativ, lassen den Punkt mit der größten Steigung zu der Linie gehört, kommt zuerst

Hier ist eine kurze Demo für die Karte:

(Ich weiß wenig JavaScript, so dass ich könnte, oder wahrscheinlich haben, verletzt einige Code-Konventionen 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; 
} 

Hinweis: Sie sollten die Conversions von lat,lon zu x,y verdoppeln oder verdreifachen, da ich ein Anfänger bin, wenn es um GIS geht !!! Aber vielleicht musst du gar nichts konvertieren. Wenn Sie dies nicht tun, gibt die Funktion upperLeft möglicherweise nur den niedrigsten Punkt statt des höchsten Punkts zurück, abhängig von den Positionen der fraglichen Punkte. Nochmals: Prüfe diese Annahmen dreifach!

Wenn executing the snippet above, wird die folgende gedruckt:

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

Alternative Distanzfunktion

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

Algorithmus Idee: Durchschnitt der vier Punkte, um einen Punkt innerhalb des Polygons zu erhalten. Dann berechne den Winkel des Strahls zwischen diesem Mittelpunkt und jedem Punkt unter Verwendung von inversen trigonometrischen Funktionen, wie erläutert here. Dann sortiere nach den Winkeln. Das sollte Ihnen eine (gegen-) Uhrzeigerreihenfolge geben, abhängig von der Sortierreihenfolge und dem, was Sie als "null Grad" betrachten.

UPDATE: hier ist ein Code. Meist ungeprüft, aber es ist die Idee.

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

Es sortiert Punkte (ein Array von Objekten wie {x: 1, y: 1}) gegen den Uhrzeigersinn.

Answer 3

Für die Ankunft hier ein ähnliches Problem mit einem Jahr später:

ich nicht tun stimme mit dem gebundenen Spaziergang der gewählten Antwort überein. Es gibt keine singuläre Lösung für die Reihenfolge selbst bei einer gegebenen Taktrichtung. Die konvexe Hülle der gegebenen Koordinaten eliminiert Punkte e und f. Diese können dann an beliebiger Stelle entlang des Pfades angebracht werden. Objektiv kann h, e, f, c zu h, f, e, c verbessert werden, wobei die Richtung der x-Komponente konsistent bleibt - in diesem Fall negativ.

Die Bedeutung von dies macht es unmöglich zu garantieren, die Aufnahme eines Kartenstandortes in dem entstandenen Gebiet durch den gewählten Spaziergang begrenzt.