Sort latitude and longitude coordinates into clockwise ordered quadrilateral
- by Dave Jarvis
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.
Solutions and Searches
http://www.geocodezip.com/map-markers_ConvexHull_Polygon.asp
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
http://stackoverflow.com/questions/2374708/how-to-sort-points-in-a-google-maps-polygon-so-that-lines-do-not-cross
http://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order
http://en.literateprograms.org/Quickhull_%28Javascript%29
Graham's scan seems too complicated for four coordinates
Sort the coordinates into two arrays (one by latitude, the other longitude) ... then?
Jarvis March algorithm?
Question
How do you sort the coordinates in (counter-)clockwise order, using JavaScript?
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;
}
What is a better approach?
The recursive Convex Hull algorithm is overkill for four points in the data set.
Thank you.
