You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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.
About
Javascript implementation of Andrew's Monotone Chain convex hull algorithm. Useful for Google Maps work.