Package micycle.medialAxis

Class MedialAxis

  • public class MedialAxis
extends Object
    Based on ideas from https://www.cs.ubc.ca/labs/imager/th/2003/Tam2004/Tam2004.pdf and Voronoi Ball/Disk Models for Computational Shape Applications

    Produces a directed acyclic graph of the MD / more specifically rooted tree

    Medial Axis library models medial axes of shapes as a (rooted) tree of medial disks. Medial disks reference a parent and have upto 3 children (the medial axis bifurcates/forks at disks with 2 children). The root is the disk with the largest circumcirle, also the single disk that trifurcates. All disks have an indegree of 1.

    Medial axes are...

    For geometries of genus zero, the graph is naturally a tree. For objects with holes, we break each cycle by imposing an appropriate breakpoint in the loop. This is only for the purposes of traversing the graph without running into infinite loops. In order to preserve the topology of the original object, cycles are never pruned

    Decompose the disk coordinates into curves.

    If angle of successive line branches is the same, merge them

    * One way to get a smoother initial axis (i.e. without pruning) is to apply on a smoothed version of the shape.

    Author:
    Michael Carleton

    • Constructor Detail

      • MedialAxis

        public MedialAxis​(org.locationtech.jts.geom.Coordinate[] coordinates)

      • MedialAxis

        public MedialAxis​(org.locationtech.jts.geom.Geometry g)
        The medial axis is computed for the geometry during construction.
        Parameters:
        g - Geometry whose medial axis to compute. Can contain holes. Must not be a multigeometry. Must be fairly dense.

    • Method Detail

      • getRoot

        public MedialAxis.MedialDisk getRoot()
        Returns the root disk -- the disk with largest radius and 3 children.
        Returns:

      • nearestDisk

        public MedialAxis.MedialDisk nearestDisk​(org.locationtech.jts.geom.Coordinate coordinate)

      • getDescendants

        public List<MedialAxis.MedialDisk> getDescendants​(MedialAxis.MedialDisk parent)
        Returns the children of a disk into a linear array
        Parameters:
        parent - contains chil out: contains children and the parent (at position 0)
        Returns:

      • getAncestors

        public List<MedialAxis.MedialDisk> getAncestors​(MedialAxis.MedialDisk child)
        The ancestors of a node d are the nodes on the path from d to the root. This includes node d.

        TODO another method that returns paths from fork VDs in the ancestors (Except rootnode)

        Parameters:
        child -
        Returns:

      • getDissolvedGeometry

        public org.locationtech.jts.geom.Geometry getDissolvedGeometry()
        Returns a JTS geometry where medial axis edges are dissolved into a set of maximal-length Linestrings. The output can be further simplfied with DouglasPeuckerSimplifier for example. * Returns a simplified medial axis graph leaving only maximal-length lines in which every unique segment appears once only. The output lines run between node vertices of the input, which are vertices which have either degree 1, or degree 3 or greater.
        Returns:

      • getLineMergeGraph

        public org.locationtech.jts.operation.linemerge.LineMergeGraph getLineMergeGraph()
        Get the medial axis in the form of an undirected planar graph. The graph is based on the dissolved geometry.
        Returns:

      • getBifurcations

        public List<MedialAxis.MedialDisk> getBifurcations()
        Nodes/medial disks with two descendent lineages (two children disks). Note the root node (a trifurcating node) is not included in the output.
        Returns:

      • getEdges

        public Collection<MedialAxis.Edge> getEdges()
        Returns:
        list of edges (in breadth-first order from the root node) connecting medial disks.

      • getEdgesToRoot

        public List<MedialAxis.Edge> getEdgesToRoot​(MedialAxis.MedialDisk d)
        Returns the edges comprising the path from the given disk to the root of the medial axis.
        Parameters:
        d -
        Returns:

      • getBranches

        public List<MedialAxis.Branch> getBranches()
        Aka features, aka branches Segment is a linear portion of medial disks.
        Returns:
        List of branches

      • getPrunedEdges

        public List<MedialAxis.Edge> getPrunedEdges​(double threshold)
        Returns a subset of the axis' edges; in this method edges are pruned by their axial gradient value. Edges with negative axial gradient values indicate a narrowing of the shape along that edge, and are more likely to be noise. The threshold takes into account this shape's minimum and maximum axial values when filtering.

        Presently this method prunes based on global min and max axial values (rather than per branch).

        Parameters:
        threshold - between 0...1, where 0 is no pruning and 1 is maximal pruning. the shape may be fully pruned before threshold = 1
        Returns:

      • getPrunedEdges

        public List<MedialAxis.Edge> getPrunedEdges​(double axialThreshold,
                                            double distanceThreshold)
        Returns a subset of the axis' edges; in this method edges are pruned by their axial gradient value and axis distance from the root node.
        Parameters:
        axialThreshold - between 0...1, where 0 is no pruning and 1 is maximal pruning
        distanceThreshold - between 0...1, where 0 is no pruning and 1 is maximal pruning
        Returns:

      • getPrunedEdges

        public List<MedialAxis.Edge> getPrunedEdges​(double axialThreshold,
                                            double distanceThreshold,
                                            double areaThreshold)
        Parameters:
        axialThreshold -
        distanceThreshold -
        areaThreshold - between 0...1, where 0 is no pruning and 1 is maximal pruning for this feature
        Returns:

      • iteratorBF

        public void iteratorBF​(Consumer<MedialAxis.MedialDisk> consumer)
        Will call consumer with the next disk in a BF manner, starting at the root node.
        Parameters:
        consumer -

      • calcFeatureArea

        public void calcFeatureArea()

      • drawVDM

        public void drawVDM​(processing.core.PApplet p)

      • drawVDM

        public void drawVDM​(processing.core.PApplet p,
                    int maxDepth)
        Parameters:
        p -
        maxDepth - inclusive

      • drawVDM

        public void drawVDM​(processing.core.PApplet p,
                    double fraction)
        Parameters:
        p -
        fraction - 0...1

      • drawVDMPrune

        public void drawVDMPrune​(processing.core.PApplet p,
                         double threshold)
        Prune disks with feature area that is smaller in area than the given significance threshold. The significance value of a feature can be determined by summing the areas of all triangles in the subtree associated with that feature. Any subtree that has a value below the threshold is pruned. Each feature can be seen as being supported by the branches of the subtree, so when the subtree is pruned, the feature is eliminated.
        Parameters:
        p -
        threshold - percentage of the total area of the object 0...1 (where 0 includes everything and 1 root node only)