Namn
CG_GreeneApproxConvexPartition — Beräknar approximal konvex partition av polygongeometrin
Synopsis
geometry CG_GreeneApproxConvexPartition(geometry geom);
Beskrivning
Beräknar approximal monoton konvex partition av polygongeometrin.
![[Notera]](../images/note.png)
|
|
|
En partition av en polygon P är en uppsättning polygoner som är sådana att polygonernas inre inte skär varandra och att polygonernas förening är lika med den ursprungliga polygonen P:s inre. Funktionerna CG_ApproxConvexPartition och CG_GreeneApproxConvexPartition producerar ungefärligt optimala konvexa partitioner. Båda dessa funktioner producerar konvexa uppdelningar genom att först dela upp polygonen i enklare polygoner; CG_ApproxConvexPartition använder en triangulering och CG_GreeneApproxConvexPartition en monoton uppdelning. Dessa två funktioner garanterar båda att de inte kommer att producera mer än fyra gånger det optimala antalet konvexa bitar, men de skiljer sig åt i deras körtidskomplexitet. Även om den trianguleringsbaserade approximationsalgoritmen ofta resulterar i färre konvexa bitar är detta inte alltid fallet. |
Tillgänglighet: 3.5.0 - kräver SFCGAL >= 1.5.0.
Kräver SFCGAL >= 1.5.0
Denna metod behöver SFCGAL-backend.
Exempel
Greene's monotone-based approximation uses the same polygon and stays directly comparable in one panel.
WITH data AS (
SELECT '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 AS input_polygon
)
SELECT input_polygon AS input_polygon,
CG_GreeneApproxConvexPartition(input_polygon) AS partition
FROM data;
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)) | GEOMETRYCOLLECTION(POLYGON((32 159,0 45,41 86,32 159)), POLYGON((45 1,177 2,67 24,45 1)), POLYGON((67 24,109 31,170 60,107 61,67 24)), POLYGON((41 86,45 1,67 24,41 86)), POLYGON((107 61,32 159,41 86,67 24,107 61)), POLYGON((148 120,107 61,170 60,148 120)), POLYGON((148 120,170 60,180 110,156 150,148 120)), POLYGON((156 150,83 181,89 131,148 120,156 150)))