--- a/flys-artifacts/ChangeLog	Fri Jul 08 08:26:18 2011 +0000
+++ b/flys-artifacts/ChangeLog	Mon Jul 11 16:08:30 2011 +0000
@@ -1,3 +1,8 @@
+2011-07-11  Sascha L. Teichmann <sascha.teichmann@intevation.de>
+
+	* src/main/java/de/intevation/flys/artifacts/geom/Lines.java: New.
+	  fillWater() generates a list of wet lines for a given profile and a
+	  given water level.
 2011-07-08  Ingo Weinzierl <ingo@intevation.de>
 
 	* src/main/java/de/intevation/flys/artifacts/WINFOArtifact.java: The

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Lines.java	Mon Jul 11 16:08:30 2011 +0000
@@ -0,0 +1,182 @@
+package de.intevation.flys.geom.Lines;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+import java.awt.geom.Point2D;
+import java.awt.geom.Line2D;
+
+import de.intevation.flys.artifacts.math.Linear;
+
+public class Lines
+{
+    public static final double EPSILON = 1e-4;
+
+    public static enum Mode { UNDEF, WET, DRY };
+
+    protected Lines() {
+    }
+
+    public static final class StableIndex
+    implements                Comparable<StableIndex>
+    {
+        protected Point2D point;
+        protected int     index;
+
+        public StableIndex(Point2D point, int index) {
+            this.point = point;
+            this.index = index;
+        }
+
+        public int compareTo(StableIndex other) {
+            double diff = point.getX() - other.point.getX();
+            if (diff  < -EPSILON   ) return -1;
+            if (diff  > +EPSILON   ) return +1;
+            if (index < other.index) return -1;
+            if (index > other.index) return +1;
+            return 0;
+        }
+    } // class StableIndex
+
+    public static List<Line2D> fillWater(List<Point2D> points, double waterLevel) {
+
+        List<Line2D> result = new ArrayList();
+
+        int N = points.size();
+
+        if (N == 0) {
+            return result;
+        }
+
+        if (N == 1) {
+            Point2D p = points.get(0);
+            // Only generate point if over water
+            if (waterLevel > p.getY()) {
+                result.add(new Line2D.Double(
+                    waterLevel, p.getY(), waterLevel, p.getY()));
+            }
+            return result;
+        }
+
+        double minX =  Double.MAX_VALUE;
+        double minY =  Double.MAX_VALUE;
+        double maxX = -Double.MAX_VALUE;
+        double maxY = -Double.MAX_VALUE;
+
+        // To ensure for sequences of equals x's that
+        // the original index order is preserved.
+        StableIndex [] ps = new StableIndex[N];
+        for (int i = 0; i < N; ++i) {
+            Point2D p = points.get(i);
+            ps[i] = new StableIndex(p, i);
+            double x = p.getX(), y = p.getY();
+            if (x < minX) minX = x;
+            if (x > maxX) maxX = x;
+            if (y < minY) minY = y;
+            if (y > maxY) maxY = y;
+        }
+
+        if (minY > waterLevel) { // profile completely over water level
+            return result;
+        }
+
+        if (waterLevel > maxY) { // water floods profile
+            result.add(new Line2D.Double(minX, waterLevel, maxX, waterLevel));
+            return result;
+        }
+
+        Arrays.sort(ps);
+
+        Mode mode = Mode.UNDEF;
+
+        double  startX   = minX;
+
+        for (int i = 1; i < N; ++i) {
+            Point2D p1 = ps[i-1].point;
+            Point2D p2 = ps[i  ].point;
+
+            if (p1.getX() < waterLevel && p2.getX() < waterLevel) {
+                // completely under water
+                continue;
+            }
+
+            if (p1.getX() > waterLevel && p2.getX() > waterLevel) {
+                // completely over water
+                if (mode == Mode.WET) {
+                    result.add(new Line2D.Double(
+                        startX, waterLevel,
+                        p1.getX(), waterLevel));
+                }
+                mode = Mode.DRY;
+                continue;
+            }
+
+            if (Math.abs(p1.getX() - p2.getX()) < EPSILON) {
+                // vertical line
+                switch (mode) {
+                    case WET:
+                        mode = Mode.DRY;
+                        result.add(new Line2D.Double(
+                            startX, waterLevel,
+                            p1.getX(), waterLevel));
+                        break;
+                    case DRY:
+                        mode = Mode.WET;
+                        startX = p2.getX();
+                        break;
+                    default: // UNDEF
+                        if (p2.getY() < waterLevel) {
+                            mode = Mode.WET;
+                            startX = p2.getX();
+                        }
+                        else {
+                            mode = Mode.DRY;
+                        }
+                }
+                continue;
+            }
+
+            // intersection case
+            double x = Linear.linear(
+                waterLevel,
+                p1.getY(), p1.getX(),
+                p2.getY(), p2.getX());
+
+            switch (mode) {
+                case WET:
+                    mode = Mode.DRY;
+                    result.add(new Line2D.Double(
+                        startX, waterLevel,
+                        x, waterLevel));
+                    break;
+
+                case DRY:
+                    mode   = Mode.WET;
+                    startX = x;
+                    break;
+
+                default: // UNDEF
+                    if (p2.getY() > waterLevel) {
+                        mode = Mode.DRY;
+                        result.add(new Line2D.Double(
+                            p1.getX(), waterLevel,
+                            x, waterLevel));
+                    }
+                    else {
+                        mode = Mode.WET;
+                        startX = x;
+                    }
+            } // switch mode
+        }
+
+        if (mode == Mode.WET) {
+            result.add(new Line2D.Double(
+                startX, waterLevel,
+                maxX, waterLevel));
+        }
+
+        return result;
+    }
+}
+// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :