Javascript implementation of Andrew's Monotone Chain convex hull algorithm. Useful for Google Maps work.
JavaScript
Latest commit 29a8d94 Jan 11, 2012 @mgomes Merge pull request #1 from andrewjshults/googleMapsV3
Compatibility with Google Maps v3 API
Permalink
Failed to load latest commit information.
README.textile . Apr 27, 2009
convex_hull.js Compatibility with Google Maps v3 API Jan 11, 2012

README.textile

Javascript Convex Hull

Javascript implementation of Andrew’s Monotone Chain algorithm for calculating a 2D convex hull. This can work directly with the Google Maps API’s GPoints.

The algorithm is described and a C++ implementation can be found at http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

A sample of this algorithm implemented with Google Maps can be found at http://www.geocodezip.com/map-markers_ConvexHull_Polygon.asp

  • Please note the algorithm used in the Google Maps’ implementation contains a bug that his been fixed in this repository.

Usage


// Use Google Maps’ point class or any point class with x() and y() methods defined
var points = [];
var hullPoints = [];
var hullPoints_size;
// Add a couple sample points to the array
points.push(new GLatLng(37.454299, -122.173925));
points.push(new GLatLng(37.4435, -122.108162));
points.push(new GLatLng(37.446743, -122.181095));
points.push(new GLatLng(37.432331, -122.129714));
points.push(new GLatLng(37.425287, -122.178195));
points.push(new GLatLng(37.436747, -122.131826));
points.push(new GLatLng(37.446781, -122.154234));
points.push(new GLatLng(37.456276, -122.136304));
points.push(new GLatLng(37.428799, -122.164018));
points.push(new GLatLng(37.428198, -122.125469));
// Sort the points by X, then by Y (required by the algorithm)
points.sort(sortPointY);
points.sort(sortPointX);
// Calculate the convex hull
// Takes: an (1) array of points with x() and y() methods defined
//          (2) Size of the points array
//          (3) Empty array to store the hull points
// Returns: The number of hull points, which may differ the the hull points array’s size
hullPoints_size = chainHull_2D(points, points.length, hullPoints);

Changes

  • 1.0.1: Fixed bug that was causing the algorithm to double back onto itself.