| 1 |
export default function(topology, arcs) { |
| 2 |
var stitchedArcs = {}, |
| 3 |
fragmentByStart = {}, |
| 4 |
fragmentByEnd = {}, |
| 5 |
fragments = [], |
| 6 |
emptyIndex = -1; |
| 7 |
|
| 8 |
// Stitch empty arcs first, since they may be subsumed by other arcs. |
| 9 |
arcs.forEach(function(i, j) { |
| 10 |
var arc = topology.arcs[i < 0 ? ~i : i], t; |
| 11 |
if (arc.length < 3 && !arc[1][0] && !arc[1][1]) { |
| 12 |
t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t; |
| 13 |
} |
| 14 |
}); |
| 15 |
|
| 16 |
arcs.forEach(function(i) { |
| 17 |
var e = ends(i), |
| 18 |
start = e[0], |
| 19 |
end = e[1], |
| 20 |
f, g; |
| 21 |
|
| 22 |
if (f = fragmentByEnd[start]) { |
| 23 |
delete fragmentByEnd[f.end]; |
| 24 |
f.push(i); |
| 25 |
f.end = end; |
| 26 |
if (g = fragmentByStart[end]) { |
| 27 |
delete fragmentByStart[g.start]; |
| 28 |
var fg = g === f ? f : f.concat(g); |
| 29 |
fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg; |
| 30 |
} else { |
| 31 |
fragmentByStart[f.start] = fragmentByEnd[f.end] = f; |
| 32 |
} |
| 33 |
} else if (f = fragmentByStart[end]) { |
| 34 |
delete fragmentByStart[f.start]; |
| 35 |
f.unshift(i); |
| 36 |
f.start = start; |
| 37 |
if (g = fragmentByEnd[start]) { |
| 38 |
delete fragmentByEnd[g.end]; |
| 39 |
var gf = g === f ? f : g.concat(f); |
| 40 |
fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf; |
| 41 |
} else { |
| 42 |
fragmentByStart[f.start] = fragmentByEnd[f.end] = f; |
| 43 |
} |
| 44 |
} else { |
| 45 |
f = [i]; |
| 46 |
fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f; |
| 47 |
} |
| 48 |
}); |
| 49 |
|
| 50 |
function ends(i) { |
| 51 |
var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1; |
| 52 |
if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; }); |
| 53 |
else p1 = arc[arc.length - 1]; |
| 54 |
return i < 0 ? [p1, p0] : [p0, p1]; |
| 55 |
} |
| 56 |
|
| 57 |
function flush(fragmentByEnd, fragmentByStart) { |
| 58 |
for (var k in fragmentByEnd) { |
| 59 |
var f = fragmentByEnd[k]; |
| 60 |
delete fragmentByStart[f.start]; |
| 61 |
delete f.start; |
| 62 |
delete f.end; |
| 63 |
f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; }); |
| 64 |
fragments.push(f); |
| 65 |
} |
| 66 |
} |
| 67 |
|
| 68 |
flush(fragmentByEnd, fragmentByStart); |
| 69 |
flush(fragmentByStart, fragmentByEnd); |
| 70 |
arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); }); |
| 71 |
|
| 72 |
return fragments; |
| 73 |
} |