--- a/gnv-artifacts/src/main/java/de/intevation/gnv/math/Interpolation2D.java	Mon Jan 25 17:06:01 2010 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/math/Interpolation2D.java	Mon Jan 25 18:25:19 2010 +0000
@@ -28,9 +28,88 @@
     private Interpolation2D() {
     }
 
-    public static Envelope pathBoundingBox(
+    public static final Envelope relevantArea(
         List<? extends Coordinate> path,
-        double extra
+        List<? extends Coordinate> points
+    ) {
+        return relevantArea(path, points, CULL_POINT_THRESHOLD);
+    }
+
+    public static final Envelope relevantArea(
+        Envelope                   pathBBox,
+        List<? extends Coordinate> points
+    ) {
+        return relevantArea(pathBBox, points, CULL_POINT_THRESHOLD);
+    }
+
+    public static final Envelope relevantArea(
+        Envelope                   pathBBox,
+        List<? extends Coordinate> points,
+        int                        threshold
+    ) {
+        return points.size() < threshold
+            ? null
+            : relevantArea(
+                pathBBox,
+                pointsBoundingBox(points));
+    }
+
+    public static final Envelope relevantArea(
+        List<? extends Coordinate> path,
+        List<? extends Coordinate> points,
+        int                        threshold
+    ) {
+        return points.size() < threshold || path.isEmpty()
+            ? null
+            : relevantArea(
+                pointsBoundingBox(path),
+                pointsBoundingBox(points));
+    }
+
+    public static final Envelope relevantArea(
+        Envelope pathBBox,
+        Envelope pointsBBox
+    ) {
+        double pathArea   = pathBBox.getWidth()*pathBBox.getHeight();
+        double pointsArea = pointsBBox.getWidth()*pointsBBox.getHeight();
+
+        if (pathArea > 0.8d*pointsArea) { return null; }
+
+        double nArea = 1.44d * pathArea;
+        if (nArea < 0.1d*pointsArea) nArea = 0.1d*pointsArea;
+        double w = pathBBox.getWidth();
+        double h = pathBBox.getHeight();
+        double [] d = solveQuadratic(1d, w+h, pathArea - nArea);
+
+        if (d == null) { return null; }
+
+        double extra = pos(d);
+
+        pathBBox.expandBy(extra);
+
+        return pathBBox;
+    }
+
+    public static final double [] solveQuadratic(
+        double a, double b, double c
+    ) {
+        double d = b*b - 4d*a*c;
+        if (d < 0d) { return null; }
+
+        d = Math.sqrt(d);
+        a = 1d/(2d*a);
+        b = -b;
+
+        return new double [] { a*(b + d), a*(b - d) };
+    }
+
+    public static final double pos(double [] x) {
+        return x[0] >= 0 ? x[0] : x[1];
+    }
+
+
+    public static Envelope pointsBoundingBox(
+        List<? extends Coordinate> path
     ) {
         int N = path.size();
         Envelope area = new Envelope(path.get(N-1));
@@ -39,10 +118,6 @@
             area.expandToInclude(path.get(i));
         }
 
-        area.expandBy(
-            extra*area.getWidth(),
-            extra*area.getHeight());
-
         return area;
     }
 
@@ -69,12 +144,8 @@
             return;
         }
 
-        Envelope relevantArea = M > CULL_POINT_THRESHOLD
-			? pathBoundingBox(path, 0.05d)
-			: null;
-        
         List<GridCell> cells = GridCell.pointsToGridCells(
-            points, relevantArea);
+            points, relevantArea(path, points));
 
         if (cells.isEmpty()) {
             log.warn("no cells found");