Opened 18 years ago

Closed 10 years ago

#966 closed defect (wontfix)

[OGR] new line generalize switch for OGR2OGR utility

Reported by: jmckenna@… Owned by: warmerdam
Priority: high Milestone:
Component: OGR_SF Version: unspecified
Severity: normal Keywords: generalize
Cc: Markus Neteler, Daniel Morissette, aboudreault, Jeff McKenna, bfraser

Description (last modified by Daniel Morissette)

Daniel Morissette has made an interesting patch for OGR2OGR to allow LineString generalization (the new function is included below), using a new '-gen_tol' switch. It is a simple algorithm (see full description below), and although there are more detailed generalization algorithms out there, it would be nice to have this one in ogr2ogr (others can be added if/when required).

I have tested this (against FME generalize algorithms) and it is comparable (to FME's 'ThinNoPoint' algorithm). If you decide that this should be added, Daniel will commit these changes in CVS. I have included a short description of FME's line generalization algorithms below, just for reference.

*Note* that the current -gen_tol patch does not include the "gen_tol" switch in the usage, and this will have to be added before committing.

Here is a full description for the ogr2ogr.html page:

"When the -gen_tol switch is used, vertices that are less than the tolerance distance away from an adjacent vertex within a feature are removed. The begin and end points are never moved, even if the end point is less than the tolerance apart from the previous point. The -gen_tol switch is currently implemented only for LineStrings. Any other geometry types are left untouched.

The tolerance corresponds to 1x or 2x the pixel size at the largest scale that this shapefile will be used at."

new function:

+OGRGeometry *GeneralizeGeometry(OGRGeometry *poGeom, double dGenTol)
+{
+    double dSqTol = dGenTol*dGenTol;
+
+    if (poGeom == NULL)
+        return NULL;
+
+    if (wkbFlatten(poGeom->getGeometryType()) == wkbLineString)
+    {
+        OGRLineString *poLineString = (OGRLineString *)poGeom;
+        double dX0=0, dY0=0, dX1, dY1;
+
+        int numInPoints = poLineString->getNumPoints();
+        int numOutPoints = 0;
+
+        if (numInPoints > 0)
+        {
+            dX0 = poLineString->getX(0);
+            dY0 = poLineString->getY(0);
+            numOutPoints = 1;
+        }
+
+        double dX, dY, dSqDist;
+        for(int i=1; i<numInPoints; i++)
+        {
+            dX1 = poLineString->getX(i);
+            dY1 = poLineString->getY(i);
+
+            dX = dX1-dX0;
+            dY = dY1-dY0;
+            dSqDist = dX*dX + dY*dY;
+            if (i == numInPoints-1 || dSqDist >= dSqTol)
+            {
+                /* Keep this point (always keep the last point) */
+                poLineString->setPoint(numOutPoints++, dX1, dY1);
+                dX0 = dX1;
+                dY0 = dY1;
+            }
+        }
+
+        poLineString->setNumPoints(numOutPoints);
+    }
+    else
+    {
+        /* This geometry type not supported */
+        return poGeom;
+    }
+
+
+    return poGeom;
+}

FME generalization algorithms:

1) When the *ThinNoPoint* algorithm is used, vertices that are less than the tolerance distance away from an adjacent vertex within a feature are removed. The begin and end points are never moved, even when the entire length of the feature being thinned is less than the tolerance, in which case the feature is replaced by a linear feature connecting the first point to the last point.

2) When the *Douglas* algorithm is used, vertices which cause a deviation of less than the tolerance the surrounding line segment are removed, but the location of the remaining vertices is not altered.

3) When the *Thin* algorithm is used, vertices that are less than the tolerance distance away from an adjacent vertex within a feature are removed. The begin and end points are never moved, unless the entire length of the feature being thinned is less than the tolerance, in which case the feature is replaced by a point feature holding the final coordinate.

4) The *Deveau* algorithm removes vertices which contribute less to the overall shape of the feature, and may introduce new vertices at positions not originally in the feature as it works. The inherent behavior of the algorithm is such that it invalidates the z coordinate of the vertices. Therefore the output features will always be 2D. It requires two additional parameters to be specified... *

Attachments (3)

ticket966-gen_tol.patch (7.0 KB ) - added by Daniel Morissette 15 years ago.
New patch against trunk r16725 that supports any geometry type
ticket966-gen_tol-1.7.2.patch (6.9 KB ) - added by Daniel Morissette 14 years ago.
'ogr2ogr -gen_tol' patch updated for GDAL 1.7.2
ticket966-gen_tol-1.8.0.patch (6.9 KB ) - added by aboudreault 13 years ago.
gentol patch for 1.8.0

Download all attachments as: .zip

Change History (14)

comment:1 by warmerdam, 18 years ago

Jeff / Daniel, 

I think I would prefer to push this down into OGR proper as a method
on the OGRGeometry and to include at least an "algorithm" selector
even if for now it only includes the simple algorithm Daniel has
implemented. 

If you guys would like to take that on, then by all means go ahead
and let me know when it is in for review.  Otherwise, I'll try and
follow up on this as time permits. 

comment:2 by Daniel Morissette, 15 years ago

Cc: Daniel Morissette added
Description: modified (diff)

by Daniel Morissette, 15 years ago

Attachment: ticket966-gen_tol.patch added

New patch against trunk r16725 that supports any geometry type

comment:3 by Daniel Morissette, 15 years ago

Arghh... attaching patches don't generate an email notification... for anyone interested, I attached a new patch yesterday against trunk that supports any geometry type.

Frank, what would you think of including this in the trunk version of ogr2ogr?

comment:4 by Daniel Morissette, 15 years ago

Cc: aboudreault added

by Daniel Morissette, 14 years ago

'ogr2ogr -gen_tol' patch updated for GDAL 1.7.2

comment:5 by Jeff McKenna, 14 years ago

Thanks for updating the patch Daniel. Frank can we add this to ogr2ogr trunk?

comment:6 by Jeff McKenna, 14 years ago

Cc: Jeff McKenna added

in reply to:  5 comment:7 by capooti, 13 years ago

Replying to jmckenna:

Thanks for updating the patch Daniel. Frank can we add this to ogr2ogr trunk?

I have seen that the patch has still not be applied on trunk: any plan for doing that? I think that, even if for now there is only the simple algorithm, it is a nice feature to have

by aboudreault, 13 years ago

gentol patch for 1.8.0

comment:8 by bfraser, 12 years ago

Cc: bfraser added

comment:9 by warmerdam, 12 years ago

Keywords: generalize added
Status: newassigned

I have added myself a TODO item to address this ticket in the next few days.

comment:10 by Jukka Rahkonen, 10 years ago

Is this something different of better than -simplify tolerance:

(starting with GDAL 1.9.0) distance tolerance for simplification. Note: the algorithm used preserves topology per feature, in particular for polygon geometries, but not for a whole layer.

If not, close the ticket, or?

comment:11 by Daniel Morissette, 10 years ago

Resolution: wontfix
Status: assignedclosed

No it's not exactly the same as -simplify (which uses GEOSSimplify which is the Douglas-Peucker algorithm), but now that we have -simplify available we don't need this any more and can close as WONTFIX.

Note: See TracTickets for help on using tickets.