List of the available algorithms in CartAGen

A list, not exhaustive yet, of the generalization algorithms available in CartAGen platform.

Line simplification algorithms

Algorithm name Reference Code Description of the implementation
Douglas & Peucker Douglas & Peucker 1973 JTS implementation basic implementation
Visvalingam-Whyatt Visvalingam & Whyatt 1993 VisvalingamWhyatt topology safe implementation (checks potential intersections when removing a vertex)
Hexagon based Raposo 2013 RaposoSimplification basic implementation of all versions of the algorithm
Li-Openshaw Li & Openshaw 1992 LiOpenshawSimplification Raster implementation of the Li-Openshaw algorithm
Accordion Plazanet 1996 BendSeriesAlgorithm Port from the initial ADA code
Bend schematisation Lecordix et al 1997 BendSeriesAlgorithm Port from the initial ADA code

Building algorithms (for individual buildings and building groups)

Algorithm name Reference Code Description of the implementation
Simplification Ruas 1988 reported in AGENT project from GeOxygene implemented by Julien Gaffuri (code comments mostly in French)
Least squares squaring Lokhat & Touya 2016 SquarePolygonLS non linear least squares optimize the position of the building vertices, rectifying almost 90° angles
Enlarge reported in AGENT project JTS implementation  
Enlarge to rectangle reported in AGENT project uses JTS smallest surrounding rectangle (SSR)  
Rotate reported in AGENT project JTS implementation  
Random displacement never published (@Julien Gaffuri) BuildingDisplacementRandom iteratively, a building is randomly displaced (with very small displacements), until the global legibility is optimized (a gradient descent is used)
displacement in block Ruas 1999 BuildingDisplacementRuas  
Aggregation Regnauld 1998 PolygonAggregation Direct port from Regnauld’s PhD thesis, comments only in French for now
Morphology Amalgamation Damen et al 2008 BuildingsAggregation Direct port from the workshop paper, but the square Minkowski is approximated by the CAP_FLAT buffer from JTS library
Delete overlaping buildings in block never published (@Guillaume Touya) BuildingDeletionOverlap Given a threshold of area overlaping and a couple of overlaping buildings, deletes the smallest one
ELECTRE deletion in block not yet published (@Guillaume Touya) BuildingsDeletionProximityMultiCriterion Uses ELECTRE III multi-criteria to sort buildings from the first to delete to the last, using criteria such as, relative position, congestion or size
PROMETHEE deletion in block not yet published (@Guillaume Touya) BuildingDeletionPromethee Uses PROMETHEE multi-criteria to sort buildings from the first to delete to the last, using criteria such as, relative position, congestion or size
Congestion based deletion in block Ruas 1999 BuildingsDeletionCongestion comments in French for now
Building typification Burghardt & Cecconi 2007 TypifyBurghardtCecconi slightly adapted implementation to better preserve some specific buildings

Network algorithms (for individual network section and for whole networks)

Algorithm name Reference Code Description of the implementation
River network selection Touya 2007 RiverNetworkSelection some of the structures detection algorithms (e.g. irrigation areas) have not been ported from the initial implementation on 1Spatial’s LAMPS2 software (that was used in the paper experiments).
Roundabout detection/collapse Touya 2010 CollapseRoundabout  
Road network selection Touya 2010 RoadNetworkTrafficBasedSelection some of the structures detection algorithms (e.g. highway interchange) have not been ported from the initial implementation on 1Spatial’s LAMPS2 software.
Strokes based road selection Thomson & Richardson 1999 RoadNetworkStrokesBasedSelection Two criteria can be used for Stroke saliency: lenght of course, and the number T-shaped intersections
Collapse parallel railways Touya & Girres 2014 CollapseParallelRailways  
Typify side tracks Savino & Touya 2015 TypifySideTracks  

Other algorithms

Algorithm name Reference Code Description of the implementation
Point cloud reduction   KMeansReduction  
Point cloud covering Galton & Duckham 2006 DelaunayNonConvexHull  
Spinalize Touya & Girres 2014 Spinalize  
Skeletonize Haunert & Sester 2008 Skeletonize  
Airport generalization Touya & Girres 2014 AirportTypification