[OGR] new line generalize switch for OGR2OGR utility

[jmckenna@…]

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...
*****