import {triangle as cartesianTriangleArea} from "./area"; import {absolute as transformAbsolute, relative as transformRelative} from "./transform"; import minAreaHeap from "./minAreaHeap"; export default function(topology, triangleArea) { var absolute = transformAbsolute(topology.transform), relative = transformRelative(topology.transform), heap = minAreaHeap(); if (!triangleArea) triangleArea = cartesianTriangleArea; topology.arcs.forEach(function(arc) { var triangles = [], maxArea = 0, triangle, i, n, p; // To store each point’s effective area, we create a new array rather than // extending the passed-in point to workaround a Chrome/V8 bug (getting // stuck in smi mode). For midpoints, the initial effective area of // Infinity will be computed in the next step. for (i = 0, n = arc.length; i < n; ++i) { p = arc[i]; absolute(arc[i] = [p[0], p[1], Infinity], i); } for (i = 1, n = arc.length - 1; i < n; ++i) { triangle = arc.slice(i - 1, i + 2); triangle[1][2] = triangleArea(triangle); triangles.push(triangle); heap.push(triangle); } for (i = 0, n = triangles.length; i < n; ++i) { triangle = triangles[i]; triangle.previous = triangles[i - 1]; triangle.next = triangles[i + 1]; } while (triangle = heap.pop()) { var previous = triangle.previous, next = triangle.next; // 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 (previous) { previous.next = next; previous[2] = triangle[2]; update(previous); } if (next) { next.previous = previous; next[0] = triangle[0]; update(next); } } arc.forEach(relative); }); function update(triangle) { heap.remove(triangle); triangle[1][2] = triangleArea(triangle); heap.push(triangle); } return topology; }