ordering

`sleap.qc.features.ordering` ¶

Keypoint ordering features: turning angles along chains.

Detects nodes that are labeled out of order along an ordered chain (e.g. a tail TTI -> Tail_0 -> Tail_1 -> Tail_2 -> TailTip).

The core idea (maintainer's design): treat consecutive chain segments as vectors v_i = node_i - node_{i-1} and look at the turning angle between consecutive segments at each interior node (the angle between v_i and v_{i+1}). A correctly ordered chain -- even one that is naturally curled -- has gentle turning angles. A mislabel (e.g. an adjacent swap) produces a sharp direction reversal, which shows up as one or two large turning angles. An out-of-order pair that is not adjacent (e.g. Tail_1 swapped with Tail_3) additionally makes two non-adjacent segments geometrically cross, which is a strong, unambiguous signal.

The turning angle is invariant to translation, rotation, and uniform scale, so these features do not need any learned per-dataset statistics.

Functions:

Name	Description
`compute_chain_ordering`	Detect wrong keypoint order along ordered chains via turning angles.
`resolve_chains`	Resolve ordered chains to node-index sequences.

`compute_chain_ordering(points, chains, max_turn_angle=DEFAULT_MAX_TURN_ANGLE)` ¶

Detect wrong keypoint order along ordered chains via turning angles.

For each chain, the turning angle is computed at every interior node from the two adjacent segment vectors. The order_inversion_rate is the fraction of interior nodes whose turning angle exceeds max_turn_angle (a sharp reversal). The chain_intersection_count is the number of non-adjacent segment pairs that geometrically cross -- a strong signal of a non-local swap (e.g. Tail_1 <-> Tail_3). Results are aggregated as the maximum over all chains, and the worst chain/node are recorded for use in an explanation.

All metrics are invariant to translation, rotation, and uniform scale, and NaN (invisible/missing) nodes are skipped without leaking into results.

Parameters:

Name	Type	Description	Default
`points`	`ndarray`	`(N_nodes, 2)` array of node coordinates; NaN marks invisible/missing nodes.	required
`chains`	`list[list[int]]`	List of chains, each an ordered list of node indices. Use :func:`resolve_chains` to obtain these from user-defined names or auto-detected chains.	required
`max_turn_angle`	`float`	Per-interior-node turning-angle threshold in radians above which a node is counted as an inversion. Default ~60 degrees.	`DEFAULT_MAX_TURN_ANGLE`

Returns:

Type Description

dict

Dictionary with: - order_inversion_rate: float in [0, 1], max over chains of the fraction of interior nodes whose turning angle exceeds the threshold. - chain_intersection_count: int, max over chains of the number of crossing non-adjacent segment pairs. - max_turn_angle: float (radians), largest turning angle seen at any interior node across all chains. - worst_chain: tuple of node indices for the chain with the largest turning angle (empty tuple if none evaluable). - worst_node: int, the interior node index (into points) with the largest turning angle, or -1 if none evaluable.

Source code in sleap/qc/features/ordering.py

def compute_chain_ordering(
    points: np.ndarray,
    chains: list[list[int]],
    max_turn_angle: float = DEFAULT_MAX_TURN_ANGLE,
) -> dict:
    """Detect wrong keypoint order along ordered chains via turning angles.

    For each chain, the turning angle is computed at every interior node from
    the two adjacent segment vectors. The ``order_inversion_rate`` is the
    fraction of interior nodes whose turning angle exceeds ``max_turn_angle``
    (a sharp reversal). The ``chain_intersection_count`` is the number of
    non-adjacent segment pairs that geometrically cross -- a strong signal of a
    non-local swap (e.g. ``Tail_1`` <-> ``Tail_3``). Results are aggregated as
    the maximum over all chains, and the worst chain/node are recorded for use
    in an explanation.

    All metrics are invariant to translation, rotation, and uniform scale, and
    NaN (invisible/missing) nodes are skipped without leaking into results.

    Args:
        points: ``(N_nodes, 2)`` array of node coordinates; NaN marks
            invisible/missing nodes.
        chains: List of chains, each an ordered list of node indices. Use
            :func:`resolve_chains` to obtain these from user-defined names or
            auto-detected chains.
        max_turn_angle: Per-interior-node turning-angle threshold in radians
            above which a node is counted as an inversion. Default ~60 degrees.

    Returns:
        Dictionary with:
        - ``order_inversion_rate``: float in ``[0, 1]``, max over chains of the
          fraction of interior nodes whose turning angle exceeds the threshold.
        - ``chain_intersection_count``: int, max over chains of the number of
          crossing non-adjacent segment pairs.
        - ``max_turn_angle``: float (radians), largest turning angle seen at any
          interior node across all chains.
        - ``worst_chain``: tuple of node indices for the chain with the largest
          turning angle (empty tuple if none evaluable).
        - ``worst_node``: int, the interior node index (into ``points``) with
          the largest turning angle, or ``-1`` if none evaluable.
    """
    default = {
        "order_inversion_rate": 0.0,
        "chain_intersection_count": 0,
        "max_turn_angle": 0.0,
        "worst_chain": (),
        "worst_node": -1,
    }

    if not chains:
        return default

    points = np.asarray(points, dtype=float)

    best_inversion_rate = 0.0
    best_intersection_count = 0
    overall_max_angle = 0.0
    worst_chain: tuple[int, ...] = ()
    worst_node = -1

    for chain in chains:
        if len(chain) < 3:
            continue

        # --- Turning angles at interior nodes ---
        n_interior = 0
        n_inversions = 0
        for i in range(1, len(chain) - 1):
            prev_idx, curr_idx, next_idx = chain[i - 1], chain[i], chain[i + 1]
            p_prev = points[prev_idx]
            p_curr = points[curr_idx]
            p_next = points[next_idx]

            # Skip interior node if any of the three involved nodes is missing.
            if (
                np.isnan(p_prev).any()
                or np.isnan(p_curr).any()
                or np.isnan(p_next).any()
            ):
                continue

            v1 = p_curr - p_prev  # incoming segment direction
            v2 = p_next - p_curr  # outgoing segment direction
            theta = _turning_angle(v1, v2)
            if np.isnan(theta):
                # Degenerate (coincident nodes); not an evaluable turn.
                continue

            n_interior += 1
            if theta > max_turn_angle:
                n_inversions += 1

            if theta > overall_max_angle:
                overall_max_angle = theta
                worst_chain = tuple(chain)
                worst_node = int(curr_idx)

        inversion_rate = (n_inversions / n_interior) if n_interior > 0 else 0.0
        if inversion_rate > best_inversion_rate:
            best_inversion_rate = inversion_rate

        # --- Non-adjacent segment crossings ---
        # Build the list of visible segments (consecutive node pairs in chain).
        segments: list[tuple[int, np.ndarray, np.ndarray]] = []
        for i in range(len(chain) - 1):
            a_idx, b_idx = chain[i], chain[i + 1]
            pa, pb = points[a_idx], points[b_idx]
            if np.isnan(pa).any() or np.isnan(pb).any():
                continue
            segments.append((i, pa, pb))

        intersection_count = 0
        for si in range(len(segments)):
            i_pos, pa, pb = segments[si]
            for sj in range(si + 1, len(segments)):
                j_pos, pc, pd = segments[sj]
                # Only non-adjacent segments: adjacent segments share an
                # endpoint by construction and would always "touch".
                if abs(i_pos - j_pos) <= 1:
                    continue
                if _segments_intersect(pa, pb, pc, pd):
                    intersection_count += 1

        if intersection_count > best_intersection_count:
            best_intersection_count = intersection_count

    return {
        "order_inversion_rate": float(best_inversion_rate),
        "chain_intersection_count": int(best_intersection_count),
        "max_turn_angle": float(overall_max_angle),
        "worst_chain": worst_chain,
        "worst_node": worst_node,
    }

`resolve_chains(skeleton_node_names, ordered_chains_by_name, auto_chains)` ¶

Resolve ordered chains to node-index sequences.

A user-declared ordering is treated as ground truth: when ordered_chains_by_name is provided, those chains (given as lists of node names) are resolved to node indices and used directly. This makes the turning-angle rule deterministic, since the intended order is known.

When no user-defined chains are given, falls back to auto_chains (chain index sequences inferred from the skeleton graph, e.g. from SkeletonAnalyzer.get_curvature_chains()).