impl/python/avoid_collisions.py

from typing import List, Sequence

from .charts_layout_types import LabelBox


def avoid_collisions(boxes: Sequence[LabelBox], padding: float) -> List[bool]:
    """Which labels to show so none overlap: greedily, highest priority first
    (then input order), keeping a label only if it clears every kept label by
    at least padding. Touching is not overlapping. Result in input order."""
    if not padding >= 0:
        raise ValueError("padding must not be negative, received %r" % (padding,))
    for b in boxes:
        if not (b.width >= 0 and b.height >= 0):
            raise ValueError("label boxes must not have negative size")
    order = sorted(range(len(boxes)), key=lambda i: (-boxes[i].priority, i))
    shown = [False] * len(boxes)
    kept: List[LabelBox] = []
    for i in order:
        a = boxes[i]
        clash = any(
            a.x < k.x + k.width + padding
            and k.x < a.x + a.width + padding
            and a.y < k.y + k.height + padding
            and k.y < a.y + a.height + padding
            for k in kept
        )
        if not clash:
            kept.append(a)
            shown[i] = True
    return shown