Split triangulation differently to produce more regular triangles

[kforeman]

I'm trying to do some transitions on the topojson/world-atlas 110m map and finding that some of the more complicated geographies break a lot of the time when calling flubber.combine.

I've got a reproducible block up here [gist].

If you add e.g. the United States back in (by no longer filtering out id=840 in line 46) it'll break, saying Uncaught RangeError: Can't collapse topology into 10 pieces.. Changing maxSegmentLength can make things better or worse, causing more or fewer countries to break (but I've yet to find a value that works for all of them).

Also, thanks for the awesome library! I've been eagerly watching your bl.ocks for a while and wanting to give these transitions a try, and this makes it so easy to do.

[kforeman]

My fallback for now is to return d3.interpolateString() instead if flubber.combine() fails.

If you'd like me to integrate that directly into flubber and submit a PR let me know. I just figured it's probably best to avoid silent errors and instead have users handle them explicitly.

[veltman]

Thanks for the detailed post! This is actually on my todo list - basically if you have a multishape with n shapes, your single shape currently needs at least n+2 vertices in order to get triangulated into enough pieces. So in your case, using the default maxSegmentLength for those circles looks like it gives you a nonagon, so any feature with 8 or more parts would fail.

This fix has been delayed a little because rather than add colinear points on the original shape, which can result in weird slivers, I think the right approach is to still triangulate normally first, but then to split those triangles in half if needed, and that's a bit more involved to implement. But hopefully I should have it in there in the next few days.

In the meantime, as you mention you could decrease maxSegmentLength, or you could limit the shapes to the eight largest polygons, or simplify the geometry until none of the features have that many.

[kforeman]

Nice, I was thinking something along the same lines (recursively splitting up the triangles until there are enough pieces) but don't know my way around the code quite well enough yet to know the best place to implement.

[veltman]

I pushed v0.2.5 which should fix this error - I'll look into other splitting strategies later this week to see whether the results are any better.

[veltman]

Thought about this a bit more and I think the way to go is probably to split any triangle that's more than x% of the total area from the midpoint of its longest side to the opposite vertex before the merge step. That ought to result in fewer sliver triangles that span the whole width/height of the shape, and it would never result in more than a handful of extra ops.