Skip to content

Instantly share code, notes, and snippets.

@milkbread
Created June 5, 2013 12:54
Show Gist options
  • Save milkbread/5713643 to your computer and use it in GitHub Desktop.
Save milkbread/5713643 to your computer and use it in GitHub Desktop.
JavaScript: Simplify_RK
(function() {
d3.simplify = function() {
var projection = d3.geo.mercator();
function simplify(feature) {
if (feature.type !== "MultiPolygon" && feature.type !== "LineString" && feature.type !== "Polygon" && feature.type !== "MultiLineString") throw new Error("not yet supported");
var heap = minHeap(),
maxArea = 0,
triangle;
if (feature.type == "LineString"){
triangles = [];
var points = feature.coordinates
for (var i=1;i<points.length-1;i++){
var point = feature.coordinates[i];
triangle = points.slice(i - 1, i + 2);
if (triangle[1][2] = area(triangle)) {
triangles.push(triangle);
heap.push(triangle);
}
}
feature.coordinates = feature.coordinates.map(function(lineString) {
var points = lineString.map(projection);
for (var i = 1, n = lineString.length - 1; i < n; ++i) {
triangle = points.slice(i - 1, i + 2);
if (triangle[1][2] = area(triangle)) {
triangles.push(triangle);
heap.push(triangle);
}
}
for (var i = 0, n = triangles.length; i < n; ++i) {
triangle = triangles[i];
triangle.previous = triangles[i - 1];
triangle.next = triangles[i + 1];
}
return points;
});
}
else if (feature.type == "Polygon"){
feature.coordinates = feature.coordinates.map(function(lineString) {
var points = lineString.map(projection),
triangles = [];
for (var i = 1, n = lineString.length - 1; i < n; ++i) {
triangle = points.slice(i - 1, i + 2);
if (triangle[1][2] = area(triangle)) {
triangles.push(triangle);
heap.push(triangle);
}
}
for (var i = 0, n = triangles.length; i < n; ++i) {
triangle = triangles[i];
triangle.previous = triangles[i - 1];
triangle.next = triangles[i + 1];
}
return points;
});
}
else if (feature.type == "MultiLineString"){
feature.coordinates = feature.coordinates.map(function(lineString){
// console.log(lineString.length);
var points = lineString.map(projection),
triangles = [];
// console.log(points);
for (var i = 1, n = lineString.length - 1; i < n; ++i) {
triangle = points.slice(i - 1, i + 2);
if (triangle[1][2] = area(triangle)) {
triangles.push(triangle);
heap.push(triangle);
}
}
for (var i = 0, n = triangles.length; i < n; ++i) {
triangle = triangles[i];
triangle.previous = triangles[i - 1];
triangle.next = triangles[i + 1];
}
// console.log(points);
return points;
});
}
else if (feature.type == "MultiPolygon"){
feature.coordinates = feature.coordinates.map(function(polygon) {
return polygon.map(function(lineString) {
var points = lineString.map(projection),
triangles = [];
for (var i = 1, n = lineString.length - 1; i < n; ++i) {
triangle = points.slice(i - 1, i + 2);
if (triangle[1][2] = area(triangle)) {
triangles.push(triangle);
heap.push(triangle);
}
}
for (var i = 0, n = triangles.length; i < n; ++i) {
triangle = triangles[i];
triangle.previous = triangles[i - 1];
triangle.next = triangles[i + 1];
}
return points;
});
});
}
while (triangle = heap.pop()) {
// If the area of the current point is less than that of the previous point
// to be eliminated, use the latter’s area instead. This ensures that the
// current point cannot be eliminated without eliminating previously-
// eliminated points.
if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
else maxArea = triangle[1][2];
if (triangle.previous) {
triangle.previous.next = triangle.next;
triangle.previous[2] = triangle[2];
update(triangle.previous);
} else {
triangle[0][2] = triangle[1][2];
}
if (triangle.next) {
triangle.next.previous = triangle.previous;
triangle.next[0] = triangle[0];
update(triangle.next);
} else {
triangle[2][2] = triangle[1][2];
}
}
function update(triangle) {
heap.remove(triangle);
triangle[1][2] = area(triangle);
heap.push(triangle);
}
return feature;
}
simplify.projection = function(_) {
if (!arguments.length) return projection;
projection = _;
return simplify;
};
return simplify;
};
function compare(a, b) {
return a[1][2] - b[1][2];
}
function area(t) {
return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
}
function minHeap() {
var heap = {},
array = [];
heap.push = function() {
for (var i = 0, n = arguments.length; i < n; ++i) {
var object = arguments[i];
up(object.index = array.push(object) - 1);
}
return array.length;
};
heap.pop = function() {
var removed = array[0],
object = array.pop();
if (array.length) {
array[object.index = 0] = object;
down(0);
}
return removed;
};
heap.remove = function(removed) {
var i = removed.index,
object = array.pop();
if (i !== array.length) {
array[object.index = i] = object;
(compare(object, removed) < 0 ? up : down)(i);
}
return i;
};
function up(i) {
var object = array[i];
while (i > 0) {
var up = ((i + 1) >> 1) - 1,
parent = array[up];
if (compare(object, parent) >= 0) break;
array[parent.index = i] = parent;
array[object.index = i = up] = object;
}
}
function down(i) {
var object = array[i];
while (true) {
var right = (i + 1) << 1,
left = right - 1,
down = i,
child = array[down];
if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
if (down === i) break;
array[child.index = i] = child;
array[object.index = i = down] = object;
}
}
return heap;
}
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment