README.textile

h1. 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.

h2. 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);
   
   

h3. Changes

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