Spatial Query
I recently had the need to build sets of polygons and compute an overall union of them; being the painfully naive person I am, I jumped right into the task thinking that it would be relatively easy. A week later, I had finally arrived at a working polygon clipper modified for boolean operations on poygons (mostly, see the README), but boy was it ugly. Throughout the entire process, I kept thinking “wouldn’t it be nice if I had a decent Vector/Matrix/Polygon data structure”. I made a few dirty attempts at writing something I liked looking at, but none of them were very satisfactory – really, I wanted something that looked a lot like JQuery. Something that just took whatever data I threw at it, and most of the time did something sane with it.
So, I decided I’d write Spatial Query, a small JS library that lets you do all the gruntwork Vector/Matrix/Polygon work easily. And some not so gruntwork stuff, that I just needed anyways – like generating a convex hull, or the union of two polygons.
$p([[0,0], [0, 10], [10, 10], [10, 0]]).convex_hull_2d(); $p([[0,0], [0, 10], [10, 10], [10, 0]]).union_2d([[5,5], [5, 7], [15, 7], [15, 5]]);
Since the project that spawned this library dealt with geometric data, there is also some functionality that will allow you to compute distances between latitude and longitude, as well as conversion between Latitude / Longitude and WSG84 coordinates:
$ll([lat1, lon1]).distance_to([lat2, lon2]); $ll([lat1, lon1]).vector();
Better explanation and more is available in the README
There are still some kinks in this version that I’ve got to iron out, so I’ve not even bothered assigning a number to it. Consider it version zero point ugly.
Thanks to my employer, the Indianapolis Star, for letting me open this to the public.
License ?
Mik
MIT X11′d – sorry about that.
convex_hull_2d_fast: function(){
var points = this.to_point_array();
if (points.length 0);
};
var deque = [];
if (right(points[0], points[1], points[2])) {
// right
deque.push(points[0]);
deque.push(points[1]);
} else {
// left
deque.push(points[1]);
deque.push(points[0]);
}
deque.push(points[2]);
deque.unshift(points[2]);
for (var i = 3; i points.length) {
deque.pop();
return _polygon(deque);
}
}
while (!right(deque[s-2], deque[s-1], points[i])) {
deque.pop();
s = deque.length;
}
deque.push(points[i]);
while (!right(points[i], deque[0], deque[1])) {
deque.shift();
}
deque.push(points[i]);
}
deque.pop();
return _polygon(deque);
}
Thanks for that Anton – unfortunately, I think my blog royally screwed your formatting on that method.
I looked up the algorithm that your function is based on, and put it into my current WC of Spatial Query. I haven’t pushed this to Github yet, but I will as soon as I have some time to actually write a test suite: I felt like I should definitely provide some more visual feedback on the libraries operation, as well as some micro benchmarks for evaluation. All in time.
Wow, I think what you stated earlier could be very true. Reflects what I’m experiencing. Well since I’m already right here, ponder whether you would be kind enough to change hyperlinks with my site. I shall be placing your hyperlink within the blogroll part, and I hope that our link alternate might help us make our blogs better. Hope you’ll be able to fulfill my humble request.