Sort latitude and longitude coordinates into clockwise ordered quadrilateral
Problem
Users can provide up to four latitude and longitude coordinates, in any order. They do so with Google Maps. Using Google's Polygon API (v3), the coordinates they select should highlight the selected area between the four coordinates.
Question
How do you sort an array of latitude and longitude coordinates in (counter-)clockwise order?
Solutions and Searches
StackOverflow Questions
- 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
Related Sites
- 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
Known Algorithms
- Graham's scan (too complicated)
- Jarvis March algorithm (handles N points)
- Recursive Convex Hull (removes a point)
Code
Here is what I have so far:
// 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;
}
Thank you.
Answer
Given the points:
4 + [d] [g]
|
3 [a] [e]
|
2 + [f] [h]
|
1 + [b]
|
0 +----+---[c]---+----+----+----+
0 1 2 3 4 5 6
you want to find the following bound walk:
4 + ___[d]------------[g]
| __/ \
3 [a]/ [e]__ \
| \ \_ ```--- \
2 + \ `[f] \___[h]
| \ __/
1 + [b] __/
| \ /
0 +----+--`[c]---+----+----+----+
0 1 2 3 4 5 6
?
If this is correct, here's a way:
- find the upper most point, Ptop, in the set of points. In case of a tie, pick the point with the smallest x coordinate
- sort all points by comparing the slopes mi and mj of the lines each pair of points (excluding Ptop!) Pi and Pj make when passing through Ptop
- if mi and mj are equal, let the point Pi or Pj closest to Ptop come first
- if mi is positive and mj is negative (or zero), Pj comes first
- if both mi and mj are either positive or negative, let the point belonging to the line with the largest slope come first
Here's a quick demo for the map:
(I know little JavaScript, so I might, or probably have, violated some JavaScript code conventions...):
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: your should double, or triple check the conversions from lat,lon to x,y as I am a novice if it comes to GIS!!! But perhaps you don't even need to convert anything. If you don't, the upperLeft function might just return the lowest point instead of the highest, depending on the locations of the points in question. Again: triple check these assumptions!
When executing the snippet above, the following gets printed:
points :: Stuttgard,Rotterdam,Paris,Hamburg,Praha,Amsterdam,Bremen,Calais
upper :: Hamburg
sorted :: Hamburg,Praha,Stuttgard,Paris,Bremen,Calais,Rotterdam,Amsterdam
Alternate Distance Function
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;
}