mbostock/topojson — pull request #182 by jasondavies (2014-06-29 16:03:37+00:00)
Title: Simplify each arc separately.

Rather than build one large heap for all arcs, we build a heap for each
arc separately and simplify one arc at a time. A quick benchmark using
Natural Earth’s 10m admin-0 data simplified at 1e-5 results in a 2x
speedup with this change. This is due to reduced peak memory usage and
faster heap operations on the smaller heaps.

Note that this does modify the output slightly, because Visvalingam’s
algorithm ensures the effective areas of points are always greater or
equal to the previously-eliminated points, and this modification changes
the previously-eliminated points, due to operating the points from each
arc separately.

However, this aspect is only really important on a per-arc basis, since
it prevents initially important points from being considered unimportant
later on, i.e. if eliminated points result in a smaller effective area.