Package sc.fiji.snt.util

Class TreeUtils

java.lang.Object
sc.fiji.snt.util.TreeUtils
public class TreeUtils extends Object
Static utilities for Trees.
Author:
Tiago Ferreira

  • Method Details

    • rasterize

      public static ij.ImagePlus rasterize(Tree tree)
      Rasterizes a tree into a 3D image using frustum (truncated-cone) geometry with partial-volume supersampling. Each segment is modeled as a frustum whose radii match the SWC node radii, producing a volumetric rendering that respects neurite thickness.
      Parameters:
      tree - the Tree to rasterize
      Returns:
      the rasterized 32-bit image (voxel values in [0, 1])
      See Also:

    • rasterize

      public static ij.ImagePlus rasterize(Tree tree, double lateralRes, double axialRes)
      Rasterizes a tree into a 3D image with the specified voxel sizes.
      Parameters:
      tree - the Tree to rasterize
      lateralRes - lateral (x, y) voxel size in the tree's spatial units
      axialRes - axial (z) voxel size in the tree's spatial units
      Returns:
      the rasterized 32-bit image (voxel values in [0, 1])
      See Also:

    • assignUniqueColors

      public static void assignUniqueColors(Tree tree)
      Assigns distinct colors to paths of a Tree.
      See Also:

    • assignUniqueColors

      public static void assignUniqueColors(Tree tree, String excludedHue)
      Assigns distinct colors to paths of a Tree.
      Parameters:
      excludedHue - an optional string defining a hue to be excluded. Either 'red', 'green', 'blue', or 'dim'.
      See Also:

    • assignUniqueColors

      public static void assignUniqueColors(Collection<Tree> trees)
      Assigns distinct colors to a collection of Trees.
      See Also:

    • assignUniqueColors

      public static void assignUniqueColors(Collection<Tree> trees, String excludedHue)
      Assigns distinct colors to a collection of Trees.
      Parameters:
      excludedHue - an optional string defining a hue to be excluded. Either 'red', 'green', 'blue', or 'dim'.
      See Also:

    • computeUprightAngle

      public static double computeUprightAngle(Tree tree, boolean useCentroid)
      Computes the angle (in degrees) needed to make a tree appear upright in the XY viewing plane. The angle is derived from the extension angle of a reference path (the longest geodesic by default) using compass conventions where North is 0 degrees.
      Parameters:
      tree - the tree to analyze
      useCentroid - if true, the reference path runs from root to the centroid of all tips; if false, the longest geodesic path is used
      Returns:
      the rotation angle in degrees, or Double.NaN if it cannot be computed (e.g., single-node tree)

    • mergeContinuousPaths

      public static int mergeContinuousPaths(Tree tree, double angleThreshold)
      Merges paths that continue along the same trajectory at branch points, reducing fragmentation in auto-traced reconstructions.

      Problem: Auto-tracers like GWDTTracer often create separate paths at every branch point, even when the neurite continues straight through. This may fragment continuous paths into smaller segments.

      Solution: At each junction where a parent path ends and children begin, this method checks if any child's trajectory aligns with the parent's. If the angle between their direction vectors is below the threshold, the most aligned child is merged into the parent, creating a longer continuous path.

      Algorithm:
      1. For each path with children, compute the parent's end tangent vector (direction at its terminal segment)
      2. For each child, compute its start tangent vector
      3. Find the child with the smallest angle to the parent direction
      4. If this angle ≤ threshold: append child's nodes to parent, reparent grandchildren to the extended parent, remove child from tree
      5. Repeat until no more merges are possible
      Criteria for merging: Two paths are merged when:
      • The child starts at the parent's endpoint (branch point)
      • The angle between their direction vectors ≤ angleThreshold
      • The child is the most aligned among all siblings
      Example: A traced axon might be split into 5 paths at 4 branch points: 
       Before: P1 → P2 → P3 → P4 → P5  (with side branches B1, B2, B3, B4)
 After:  P1 (merged trunk) with children B1, B2, B3, B4
      Parameters:
      angleThreshold - maximum angle (in degrees) between parent end tangent and child start tangent for paths to be considered continuous. Suggested values:
      • 15-20°: strict, only nearly straight continuations
      • 30°: moderate (default), allows gentle curves
      • 45°: permissive, may merge actual branches
      Use 0 or negative to disable merging.
      Returns:
      the number of paths that were merged (and removed from the tree)

    • findClosestEndpoints

      public static TreeUtils.EndpointMatch findClosestEndpoints(Path p1, Path p2)
      Finds the closest endpoint pairing between two paths. Checks all four combinations: start-start, start-end, end-start, end-end.
      Parameters:
      p1 - first path
      p2 - second path
      Returns:
      EndpointMatch describing the closest pairing, or null if either path is empty

    • orderByEndpointProximity

      public static List<Path> orderByEndpointProximity(Collection<Path> paths)
      Orders a collection of paths to form a spatially continuous chain based on endpoint proximity. The algorithm greedily connects paths by finding the closest endpoint pairs.

      This method does NOT modify the paths (no reversal). Use orientPathsForMerging(List) on the result to fix orientations.

      Parameters:
      paths - the paths to order (at least 2)
      Returns:
      ordered list forming a chain, or empty list if paths cannot form a continuous chain

    • orientPathsForMerging

      public static void orientPathsForMerging(List<Path> orderedPaths)
      Orients paths in a chain so they can be merged end-to-start. After this operation, each path's end node will be near the next path's start node.

      Paths are reversed in-place as needed.

      Parameters:
      orderedPaths - list of paths previously ordered by orderByEndpointProximity(java.util.Collection<sc.fiji.snt.Path>)

    • canFormContinuousChain

      public static boolean canFormContinuousChain(Collection<Path> paths, double tolerance)
      Checks if a collection of paths can form a spatially continuous chain within a given tolerance.
      Parameters:
      paths - the paths to check
      tolerance - maximum allowed distance between consecutive endpoints
      Returns:
      true if paths can be ordered into a continuous chain within tolerance

    • mergePaths

      public static Path mergePaths(List<Path> orderedPaths, boolean reparentChildren)
      Merges a list of paths into a single path by appending nodes sequentially.

      The paths should be pre-ordered and oriented using orderByEndpointProximity(java.util.Collection<sc.fiji.snt.Path>) and orientPathsForMerging(java.util.List<sc.fiji.snt.Path>).

      This method handles:
      • Appending nodes from each path to the result
      • Optionally reparenting children of merged paths to the result
      • Preserving the first path's parent connection (if any)

      Note: This method does NOT delete the original paths from any manager. The caller is responsible for cleanup.

      Parameters:
      orderedPaths - paths to merge, in order (should be oriented for merging)
      reparentChildren - if true, children of merged paths are reconnected to the result
      Returns:
      the merged path, or null if input is empty

    • analyzeEndpointClusters

      public static TreeUtils.EndpointClusterAnalysis analyzeEndpointClusters(Collection<Path> paths)
      Analyzes a collection of paths to determine which endpoint cluster (starts or ends) is more tightly grouped, suggesting the root location.

      This is useful for auto-orienting paths toward a common root when the user hasn't specified an explicit root location.

      Parameters:
      paths - the paths to analyze (must have at least 2)
      Returns:
      analysis result, or null if paths is null or has fewer than 2 paths

    • findPathsNeedingReversal

      public static List<Path> findPathsNeedingReversal(Collection<Path> paths, PointInImage rootLocation)
      Determines which paths need to be reversed so that their start nodes point toward a given root location.

      A path should be reversed if its end node is closer to the root than its start node.

      Parameters:
      paths - the paths to analyze
      rootLocation - the target root location
      Returns:
      list of paths that should be reversed (subset of input)

    • orientPathsTowardRoot

      public static int orientPathsTowardRoot(Collection<Path> paths, PointInImage rootLocation)
      Orients paths so their start nodes point toward a given root location. Paths are reversed in-place if their end node is closer to the root.

      Note: This method does NOT update child branch points. Callers must handle child branch point updates separately if paths have children.

      Parameters:
      paths - the paths to orient
      rootLocation - the target root location
      Returns:
      the number of paths that were reversed

    • suggestRootLocation

      public static PointInImage suggestRootLocation(Collection<Path> paths, PointInImage referencePoint)
      Analyzes paths and suggests auto-orientation based on:
      1. If a reference point (e.g., ROI centroid) is provided, orient toward it
      2. For 3+ paths: find the tighter endpoint cluster as the root
      3. For 2 paths: find the closest endpoint pair as the root
      Parameters:
      paths - the paths to analyze
      referencePoint - optional reference point (e.g., ROI centroid); can be null
      Returns:
      the suggested root location, or null if it cannot be determined

    • getConnectedTree

      public static Tree getConnectedTree(Path path)
      Gets the connected tree (component) containing the given path. This traverses up to the root and then collects all descendants, ensuring we only get paths that are actually connected via parent-child relationships.

      This is useful when paths may share a tree ID but are not actually connected (e.g., orphaned paths or paths awaiting relationship rebuild).

      Parameters:
      path - a path in the tree
      Returns:
      a Tree containing only the connected component

    • isInSubtree

      public static boolean isInSubtree(Path target, Path root)
      Checks if 'target' is in the subtree rooted at 'root'. This traverses down through all descendants of root.
      Parameters:
      target - the path to search for
      root - the root of the subtree to search in
      Returns:
      true if target is root or any descendant of root

    • isDescendantOf

      public static boolean isDescendantOf(Path potentialDescendant, Path potentialAncestor)
      Checks if 'potentialDescendant' is a descendant of 'potentialAncestor'. This is equivalent to checking if potentialDescendant is in the subtree rooted at potentialAncestor (excluding potentialAncestor itself).
      Parameters:
      potentialDescendant - the path to check if it's a descendant
      potentialAncestor - the path to check if it's an ancestor
      Returns:
      true if potentialDescendant is a descendant of potentialAncestor

    • isAncestorOf

      public static boolean isAncestorOf(Path potentialAncestor, Path potentialDescendant)
      Checks if 'potentialAncestor' is an ancestor of 'potentialDescendant'. This traverses up the parent chain from potentialDescendant.
      Parameters:
      potentialAncestor - the path to check if it's an ancestor
      potentialDescendant - the path to check if it has the ancestor
      Returns:
      true if potentialAncestor is an ancestor of potentialDescendant

    • getMaxOrder

      public static int getMaxOrder(Path path)
      Returns the maximum path order in the connected tree containing the given path. Higher values indicate deeper/more developed trees.
      Parameters:
      path - a path in the tree
      Returns:
      the maximum order value found in the connected tree, or 0 if retrieval fails

    • countDescendants

      public static int countDescendants(Path path)
      Counts all descendants (children, grandchildren, etc.) of a path.

    • collectChildren

      public static void collectChildren(Path path, Collection<Path> children)
      Collects direct children of a path into the provided collection.

    • collectDescendants

      public static void collectDescendants(Path path, Collection<Path> descendants)
      Collects all descendants (children, grandchildren, etc.) of a path into the provided collection.

    • getRootPath

      public static Path getRootPath(Path path)
      Gets the root path of the tree containing the given path.

    • merge

      public static Tree merge(Collection<Tree> trees)
      Combines all trees into a single Tree container.

      Note that no effort is made to make the merge structure topographylically valid. This is simply a convenience method to collect paths in a single contained for operations that do not require an accurate graph structure, e.g., Sholl Analysis.

      Parameters:
      trees -
      Returns:
      the merged tree

    • syncCanvasOffset

      public static void syncCanvasOffset(Path child, Path parent)
      Applies the parent's canvas offset to the child path and all its descendants. This ensures paths are in the same coordinate space after connection. Node coordinates are transformed to maintain the same visual position.

    • splitByPrimaryPaths

      public static List<Tree> splitByPrimaryPaths(Tree tree)
      Splits a tree with multiple primary paths into separate trees, one rooted at each primary path.

    • filterBySize

      public static List<Tree> filterBySize(Collection<Tree> trees, int minPaths, int maxPaths)
      Returns the subset of trees whose path count falls within the specified range.
      Parameters:
      trees - the input collection
      minPaths - minimum number of paths (inclusive), or -1 for no lower bound
      maxPaths - maximum number of paths (inclusive), or -1 for no upper bound
      Returns:
      a new list containing only the trees that satisfy the bounds

    • filterByCableLength

      public static List<Tree> filterByCableLength(Collection<Tree> trees, double minLength, double maxLength)
      Returns the subset of trees whose cable length falls within the specified range.
      Parameters:
      trees - the input collection
      minLength - minimum cable length (inclusive), or Double.NaN for no lower bound
      maxLength - maximum cable length (inclusive), or Double.NaN for no upper bound
      Returns:
      a new list containing only the trees that satisfy the bounds