Debian Codegraph @

topojson/src/presimplify.js

raw
1 import {triangle as cartesianTriangleArea} from "./area";
2 import {absolute as transformAbsolute, relative as transformRelative} from "./transform";
3 import minAreaHeap from "./minAreaHeap";
4
5 export default function(topology, triangleArea) {
6 var absolute = transformAbsolute(topology.transform),
7 relative = transformRelative(topology.transform),
8 heap = minAreaHeap();
9
10 if (!triangleArea) triangleArea = cartesianTriangleArea;
11
12 topology.arcs.forEach(function(arc) {
13 var triangles = [],
14 maxArea = 0,
15 triangle,
16 i,
17 n,
18 p;
19
20 // To store each point’s effective area, we create a new array rather than
21 // extending the passed-in point to workaround a Chrome/V8 bug (getting
22 // stuck in smi mode). For midpoints, the initial effective area of
23 // Infinity will be computed in the next step.
24 for (i = 0, n = arc.length; i < n; ++i) {
25 p = arc[i];
26 absolute(arc[i] = [p[0], p[1], Infinity], i);
27 }
28
29 for (i = 1, n = arc.length - 1; i < n; ++i) {
30 triangle = arc.slice(i - 1, i + 2);
31 triangle[1][2] = triangleArea(triangle);
32 triangles.push(triangle);
33 heap.push(triangle);
34 }
35
36 for (i = 0, n = triangles.length; i < n; ++i) {
37 triangle = triangles[i];
38 triangle.previous = triangles[i - 1];
39 triangle.next = triangles[i + 1];
40 }
41
42 while (triangle = heap.pop()) {
43 var previous = triangle.previous,
44 next = triangle.next;
45
46 // If the area of the current point is less than that of the previous point
47 // to be eliminated, use the latter's area instead. This ensures that the
48 // current point cannot be eliminated without eliminating previously-
49 // eliminated points.
50 if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
51 else maxArea = triangle[1][2];
52
53 if (previous) {
54 previous.next = next;
55 previous[2] = triangle[2];
56 update(previous);
57 }
58
59 if (next) {
60 next.previous = previous;
61 next[0] = triangle[0];
62 update(next);
63 }
64 }
65
66 arc.forEach(relative);
67 });
68
69 function update(triangle) {
70 heap.remove(triangle);
71 triangle[1][2] = triangleArea(triangle);
72 heap.push(triangle);
73 }
74
75 return topology;
76 }