Skip to content

v2.9.1 — Captions placed in near-linear time

Choose a tag to compare

@clintecker clintecker released this 27 Oct 16:49
· 13 commits to main since this release
64c19fb

Charts with many edge captions lay out far faster, with every caption where
it was. Output for every chart is byte-identical to 2.9.0.

Fixed

  • Charts with many edge captions lay out far faster. The caption placer
    scored every candidate position against every node, caption, bend,
    crossing and arrowhead in the chart, so its cost grew about n^2.5 with the
    number of labeled edges: a fan of 320 labeled edges took 18 s (debug
    build). It now reads only what a spatial grid finds near each candidate,
    skips a candidate whose unavoidable penalties already lose to the best one
    so far, counts the bends and crossings in a caption's way without sorting
    them, and tests only route segments that could cross: the same fan takes
    0.3 s, 480 labeled edges 0.5 s, and 160 labeled self-loops 0.07 s instead
    of 4.2 s. The placement is bit for bit what it was: every skipped term was
    exactly zero and every skipped candidate could not have won, and a test
    holds the new placer to the old one over real layouts and 300 seeded random
    ones. (#97, #99, #101)