Label collision resolution (issue #40): a pure, renderer-agnostic
greedy placement over label boxes.
Cytoscape draws every label at its element and never moves one out
of another's way, so a dense graph (the reporter's 59-publication,
223-relation citation network in layered rows) overprints labels in
the same layer until the user zooms in. The host's previous SVG
renderer placed labels greedily by priority and hid or shortened the
losers; this module restores that decision rule as a function of
boxes, so the canvas (or a host's own renderer) can measure, decide,
and apply without the rule knowing anything about Cytoscape.
Contract:
Candidates are visited in DESCENDING priority; ties break node
before edge, then by id, so the output is a pure function of the
input (no Map-iteration or insertion-order dependence).
A candidate whose box overlaps no already-placed box is shown and
its box is placed.
Otherwise, in "shorten" mode, the text is truncated to maxLength
characters (ellipsis included) and the box shrunk proportionally
about its center (both canvas label anchors, a node's bottom-center
label and an edge's midpoint label, are centered on the text); if
the shortened box fits, the decision is "shorten" and the shrunk
box is placed. A text already within maxLength cannot shorten.
Anything that still overlaps is hidden. Hidden labels place no box,
so the next candidate down is judged against what is actually
drawn, never against an invisible label.
Complexity is O(n * placed) with a plain scan; at the sizes the
canvas labels (hundreds to low thousands) that is well under a
frame. A spatial index can replace the scan without changing the
contract if a host measures tens of thousands of labels.
Label collision resolution (issue #40): a pure, renderer-agnostic greedy placement over label boxes.
Cytoscape draws every label at its element and never moves one out of another's way, so a dense graph (the reporter's 59-publication, 223-relation citation network in layered rows) overprints labels in the same layer until the user zooms in. The host's previous SVG renderer placed labels greedily by priority and hid or shortened the losers; this module restores that decision rule as a function of boxes, so the canvas (or a host's own renderer) can measure, decide, and apply without the rule knowing anything about Cytoscape.
Contract:
maxLengthcharacters (ellipsis included) and the box shrunk proportionally about its center (both canvas label anchors, a node's bottom-center label and an edge's midpoint label, are centered on the text); if the shortened box fits, the decision is "shorten" and the shrunk box is placed. A text already withinmaxLengthcannot shorten.Complexity is O(n * placed) with a plain scan; at the sizes the canvas labels (hundreds to low thousands) that is well under a frame. A spatial index can replace the scan without changing the contract if a host measures tens of thousands of labels.