Package micycle.pgs.commons

Class DiscreteCurveEvolution

java.lang.Object

micycle.pgs.commons.DiscreteCurveEvolution

public class DiscreteCurveEvolution
extends Object

This class simplifies curves while maintaining perceptual appearance. It does this through the iterative removal of the least shape-relevant "kinks", which are where consecutive line segments meet (at a vertex).

The shape relevance of a kink is calculated based on its turn angle and the lengths of the line segments it comprises. Kinks with larger turn angles and longer segments contribute more to the overall shape of the curve and are thus more likely to be preserved during the simplification process.

This class uses an efficient implementation that reduces the time complexity from a naive O(n²) to O(n log n), making it suitable for processing large datasets. It handles both closed and open curves. The algorithm is not guaranteed to be topology-preserving.

Author:

Michael Carleton

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	DiscreteCurveEvolution.DCETerminationCallback	The callback interface for determining the termination condition of the Discrete Curve Evolution (DCE) process.

Constructor Summary

Constructors

Constructor	Description
DiscreteCurveEvolution()

Method Summary

Modifier and Type	Method	Description
static org.locationtech.jts.geom.Coordinate[]	process(org.locationtech.jts.geom.LineString lineString, DiscreteCurveEvolution.DCETerminationCallback terminationCallback)	Applies the Discrete Curve Evolution (DCE) algorithm to a given polygonal curve defined by a LineString.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

DiscreteCurveEvolution

public DiscreteCurveEvolution()

Method Details

process

public static org.locationtech.jts.geom.Coordinate[] process(org.locationtech.jts.geom.LineString lineString,
 DiscreteCurveEvolution.DCETerminationCallback terminationCallback)

Applies the Discrete Curve Evolution (DCE) algorithm to a given polygonal curve defined by a LineString. This algorithm simplifies the curve by selectively removing vertices with the least shape-relevance while attempting to preserve the overall perceptual appearance of the shape. The algorithm uses a provided DiscreteCurveEvolution.DCETerminationCallback to determine the termination condition for the simplification process.

If the input shape is closed (i.e., a polygon's LinearRing), the algorithm ensures that the resulting simplified shape remains closed. Vertices with the smallest turn angles and neighboring line segments are considered the least relevant and are candidates for removal.

The process continues iteratively, removing the least relevant vertex and recalculating the relevance of affected neighboring vertices, until the termination callback indicates that the process should stop.

Parameters:

lineString - The LineString representing the original coordinates of the shape to be simplified.

terminationCallback - The callback used to determine when the simplification process should terminate.

Returns:

An array of coordinates representing the simplified shape, with a potentially reduced number of vertices that maintains the perceptual appearance of the original curve.