Changeset 14765

Timestamp:

06/24/08 17:59:05 (2 months ago)

Author:

rouault

Message:

Add possibility of defining OGR_ORGANIZE_POLYGONS=SKIP/ONLY_CCW to speed up (or skip) organizePolygons() in case the number of polygons is huge (#2428)

Files:

• branches/1.5/gdal/ogr/ogrgeometryfactory.cpp (modified) (7 diffs)

branches/1.5/gdal/ogr/ogrgeometryfactory.cpp

@@ -733 +733 @@
- * In that case, a slower algorithm that tests exact topological relationships 
- * is used if GEOS is available.)
-
+
+
+
+
+
+
+
- * @param papoPolygons array of geometry pointers - should all be OGRPolygons.
- * Ownership of the geometries is passed, but not of the array itself.
@@ -755 +761 @@
-    OGRPolygon*     poEnclosingPolygon;
-    double          dfArea;
+    int             bIsCW;
-};
-
@@ -781 +788 @@
-}
-
+#define N_CRITICAL_PART_NUMBER   100
-
-OGRGeometry* OGRGeometryFactory::organizePolygons( OGRGeometry **papoPolygons,
@@ -832 +840 @@
-    int bMixedUpGeometries = FALSE;
-    int bNonPolygon = FALSE;
+    int bFoundCCW = FALSE;
+    int bOrganisePolygonSkip = FALSE;
+    int bOrganisePolygonOnlyCCW = FALSE;
+
+    if (nPolygonCount > N_CRITICAL_PART_NUMBER)
+    {
+        bOrganisePolygonSkip = EQUAL(CPLGetConfigOption("OGR_ORGANIZE_POLYGONS", "DEFAULT"), "SKIP");
+        bOrganisePolygonOnlyCCW = EQUAL(CPLGetConfigOption("OGR_ORGANIZE_POLYGONS", "DEFAULT"), "ONLY_CCW");
+        if (bOrganisePolygonSkip)
+        {
+            bMixedUpGeometries = TRUE;
+        }
+    }
+
-
-    for(i=0;i<nPolygonCount;i++)
@@ -846 +868 @@
-            asPolyEx[i].poExteriorRing = asPolyEx[i].poPolygon->getExteriorRing();
-            asPolyEx[i].poExteriorRing->getPoint(0, &asPolyEx[i].poAPoint);
+            asPolyEx[i].bIsCW = asPolyEx[i].poExteriorRing->isClockwise();
+            if (!bFoundCCW)
+                bFoundCCW = ! (asPolyEx[i].bIsCW);
-        }
-        else
@@ -863 +888 @@
-    }
-
+    /* Emits a warning if the number of parts is sufficiently big to anticipate for */
+    /* very long computation time */
+    if (nPolygonCount > N_CRITICAL_PART_NUMBER &&
+        !bOrganisePolygonSkip && !bOrganisePolygonOnlyCCW)
+    {
+        static int firstTime = 1;
+        if (firstTime)
+        {
+            if (bFoundCCW)
+            {
+                CPLError( CE_Warning, CPLE_AppDefined, 
+                     "organizePolygons() received a polygon with more than %d parts. "
+                     "The processing may be really slow.\n"
+                     "You can skip the processing by setting OGR_ORGANIZE_POLYGONS=SKIP, "
+                     "or only make it analyze counter-clock wise parts by setting "
+                     "OGR_ORGANIZE_POLYGONS=ONLY_CCW if you can assume that the "
+                     "outline of holes is counter-clock wise defined", N_CRITICAL_PART_NUMBER);
+            }
+            else
+            {
+                CPLError( CE_Warning, CPLE_AppDefined, 
+                        "organizePolygons() received a polygon with more than %d parts. "
+                        "The processing may be really slow.\n"
+                        "You can skip the processing by setting OGR_ORGANIZE_POLYGONS=SKIP.",
+                        N_CRITICAL_PART_NUMBER);
+            }
+            firstTime = 0;
+        }
+    }
+
-
-    /* This a several steps algorithm :
@@ -913 +968 @@
-    for(i=1; !bMixedUpGeometries && go_on && i<nPolygonCount; i++)
-    {
+        if (bOrganisePolygonOnlyCCW && asPolyEx[i].bIsCW)
+        {
+            nCountTopLevel ++;
+            asPolyEx[i].bIsTopLevel = TRUE;
+            asPolyEx[i].poEnclosingPolygon = NULL;
+            continue;
+        }
+
-        for(j=i-1; go_on && j>=0;j--)
-        {