Name

CG_ApproxConvexPartition — Berechnet die approximale konvexe Partition der Polygongeometrie

Synopsis

geometry CG_ApproxConvexPartition(geometry geom);

Beschreibung

Berechnet die approximale konvexe Partition der Polygongeometrie (unter Verwendung einer Triangulation).

[Note]

Eine Partition eines Polygons P ist eine Menge von Polygonen, bei der sich die Innenräume der Polygone nicht schneiden und die Vereinigung der Polygone gleich dem Innenraum des ursprünglichen Polygons P ist. Die Funktionen CG_ApproxConvexPartition und CG_GreeneApproxConvexPartition erzeugen annähernd optimale konvexe Partitionen. Beide Funktionen erzeugen konvexe Zerlegungen, indem sie das Polygon zunächst in einfachere Polygone zerlegen; CG_ApproxConvexPartition verwendet eine Triangulation und CG_GreeneApproxConvexPartition eine monotone Partition. Diese beiden Funktionen garantieren, dass sie nicht mehr als das Vierfache der optimalen Anzahl konvexer Teile erzeugen, unterscheiden sich aber in ihrer Laufzeitkomplexität. Obwohl der auf Triangulation basierende Approximationsalgorithmus oft zu weniger konvexen Teilen führt, ist dies nicht immer der Fall.

Verfügbarkeit: 3.5.0 - erfordert SFCGAL >= 1.5.0.

Erfordert SFCGAL >= 1.5.0

Diese Methode benötigt ein SFCGAL-Backend.

Beispiele

Approximale konvexe Partition (gleiches Beispiel wie CG_YMonotonePartition, CG_GreeneApproxConvexPartition und CG_OptimalConvexPartition)

SELECT ST_AsText(CG_ApproxConvexPartition('POLYGON((156 150,83 181,89 131,148 120,107 61,32 159,0 45,41 86,45 1,177 2,67 24,109 31,170 60,180 110,156 150))'::geometry));

GEOMETRYCOLLECTION(POLYGON((156 150,83 181,89 131,148 120,156 150)),POLYGON((32 159,0 45,41 86,32 159)),POLYGON((107 61,32 159,41 86,107 61)),POLYGON((45 1,177 2,67 24,45 1)),POLYGON((41 86,45 1,67 24,41 86)),POLYGON((107 61,41 86,67 24,109 31,107 61)),POLYGON((148 120,107 61,109 31,170 60,148 120)),POLYGON((156 150,148 120,170 60,180 110,156 150)))