--- a/gnv-artifacts/src/main/java/de/intevation/gnv/math/Interpolation2D.java	Wed Dec 16 11:58:44 2009 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/math/Interpolation2D.java	Wed Dec 16 19:29:05 2009 +0000
@@ -1,6 +1,8 @@
 package de.intevation.gnv.math;
 
+import java.util.ArrayList;
 import java.util.List;
+import java.util.HashMap;
 import java.util.Collections;
 
 import com.vividsolutions.jts.geom.Coordinate;
@@ -8,11 +10,15 @@
 
 import com.vividsolutions.jts.index.quadtree.Quadtree;
 
+import org.apache.log4j.Logger;
+
 /**
  *  @author Sascha L. Teichmann
  */
 public final class Interpolation2D
 {
+    private static Logger log = Logger.getLogger(Interpolation2D.class);
+
     public interface Consumer {
         void interpolated(Coordinate point);
     } // interface Consumer
@@ -32,32 +38,70 @@
         int N = path.size();
         int M = points.size();
 
+        log.debug("Size of path: " + N);
+        log.debug("Size of points: " + M);
+
         if (M < 1 || N < 2) { // nothing to do
             return;
         }
-        // figure out max delta(p[i].x, p[i-1].x) 
-        Collections.sort(points, Point2d.X_COMPARATOR);
+
+        HashMap<Integer, ArrayList<Point2d>> map = new HashMap<Integer, ArrayList<Point2d>>();
+
+        for (int k = M-1; k >= 0; --k) {
+            Point2d p = points.get(k);
+
+            ArrayList<Point2d> list = map.get(p.j);
+
+            if (list == null) {
+                map.put(p.j, list = new ArrayList<Point2d>());
+            }
+            list.add(p);
+        }
+
         double dxMax = -Double.MAX_VALUE;
-        for (int i = 1; i < M; ++i) {
-            double dx = Math.abs(path.get(i).x - path.get(i-1).x);
-            if (dx > dxMax) {
-                dxMax = dx;
+
+        for (ArrayList<Point2d> v: map.values()) {
+            Collections.sort(v, Point2d.X_COMPARATOR);
+            for (int i = 1, L = v.size(); i < L; ++i) {
+                double dx = Math.abs(v.get(i).x - v.get(i-1).x);
+                if (dx > dxMax) {
+                    dxMax = dx;
+                }
             }
         }
 
-        dxMax = dxMax*0.5d + 1e-5d;
+        dxMax = dxMax + 1e-5d;
 
-        // figure out max delta(p[i].y, p[i-1].y) 
-        Collections.sort(path, Point2d.X_COMPARATOR);
+        map.clear();
+
+        for (int k = M-1; k >= 0; --k) {
+            Point2d p = points.get(k);
+
+            ArrayList<Point2d> list = map.get(p.i);
+
+            if (list == null) {
+                map.put(p.i, list = new ArrayList<Point2d>());
+            }
+            list.add(p);
+        }
+
         double dyMax = -Double.MAX_VALUE;
-        for (int i = 1; i < M; ++i) {
-            double dy = Math.abs(path.get(i).y - path.get(i-1).y);
-            if (dy > dyMax) {
-                dyMax = dy;
+
+        for (ArrayList<Point2d> v: map.values()) {
+            Collections.sort(v, Point2d.Y_COMPARATOR);
+            for (int i = 1, L = v.size(); i < L; ++i) {
+                double dy = Math.abs(v.get(i).y - v.get(i-1).y);
+                if (dy > dyMax) {
+                    dyMax = dy;
+                }
             }
         }
 
-        dyMax = dyMax*0.5d + 1e-5d;
+        dyMax = dyMax + 1e-5d;
+
+        map = null;
+
+        log.debug("buffer size: " + dxMax + " / " + dyMax);
 
         // put into spatial index to speed up finding neighbors.
         Quadtree spatialIndex = new Quadtree();
@@ -78,7 +122,10 @@
 
         Point2d [] neighbors = new Point2d[4];
 
-        for (double p = to; p <= from; p += dP) {
+        int missedInterpolations = 0;
+        int interpolations = 0;
+
+        for (double p = from; p <= to; p += dP) {
             if (!linearToMap.locate(p, center)) {
                 continue;
             }
@@ -141,8 +188,14 @@
                     y2, z2,
                     center.y);
                 consumer.interpolated(center);
+                ++interpolations;
+            }
+            else {
+                ++missedInterpolations;
             }
         }
+
+        log.debug("interpolations: " + interpolations + " / " + missedInterpolations);
     }
 
     public static final double interpolate(