--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/utils/IndexBuffer.java	Fri Sep 28 12:14:00 2012 +0200
@@ -0,0 +1,177 @@
+/*
+ * Copyright (c) 2010 by Intevation GmbH
+ *
+ * This program is free software under the LGPL (>=v2.1)
+ * Read the file LGPL.txt coming with the software for details
+ * or visit http://www.gnu.org/licenses/ if it does not exist.
+ */
+
+package de.intevation.gnv.utils;
+
+import java.awt.Point;
+
+import java.awt.geom.Point2D;
+
+import java.util.List;
+
+/**
+ * Create buffers around integer pairs (i_1..n), j_1..n).
+ *
+ * @author <a href="mailto:sascha.teichmann@intevation.de">Sascha L. Teichmann</a>
+ */
+public class IndexBuffer
+{
+    public static final double EPSILON = 1e-6d;
+    public static final double OFFSET  = 1.0d;
+
+    public static final String I_COLUMN = "IPOSITION";
+    public static final String J_COLUMN = "JPOSITION";
+
+    public static final class Segment {
+
+        private Segment next;
+
+        private Point2D.Double n;
+        private double         d1;
+        private double         d2;
+
+        private int iMin;
+        private int iMax;
+
+        private int jMin;
+        private int jMax;
+
+        public Segment(Point a, Point b, Segment next) {
+
+            this.next = next;
+
+            iMin = Math.min(a.x, b.x)-1;
+            iMax = Math.max(a.x, b.x)+1;
+
+            jMin = Math.min(a.y, b.y)-1;
+            jMax = Math.max(a.y, b.y)+1;
+
+            if (a.x > b.x) {
+                Point p = a; a = b; b = p;
+            }
+
+            Point2D.Double p1, p2, p3;
+
+            if (a.y < b.y) {
+                p1 = new Point2D.Double(a.x -     OFFSET, a.y + 1 + OFFSET);
+                p2 = new Point2D.Double(b.x -     OFFSET, b.y + 1 + OFFSET);
+                p3 = new Point2D.Double(a.x + 1 + OFFSET, a.y     - OFFSET);
+            }
+            else {
+                p1 = new Point2D.Double(a.x + 1 + OFFSET, a.y + 1 + OFFSET);
+                p2 = new Point2D.Double(b.x + 1 + OFFSET, b.y + 1 + OFFSET);
+                p3 = new Point2D.Double(b.x     - OFFSET, b.y     - OFFSET);
+            }
+
+            n = normalize(orthogonal(sub(p1, p2)));
+
+            d1 = dot(n, p1);
+            d2 = dot(n, p3);
+
+            if (d1 > d2) {
+                double d = d1;
+                d1 = d2;
+                d2 = d;
+            }
+        }
+
+        public boolean check(int i, int j) {
+            if (i < iMin || i > iMax || j < jMin || j > jMax) {
+                return false;
+            }
+            double v = dot(n, i, j);
+            return v >= d1 && v <= d2;
+        }
+
+        public void toWhereClause(StringBuilder sb, String iColumn, String jColumn) {
+            sb.append('(')
+              .append(iColumn).append(" >= ").append(iMin).append(" AND ")
+              .append(iColumn).append(" <= ").append(iMax).append(" AND ")
+              .append(jColumn).append(" >= ").append(jMin).append(" AND ")
+              .append(jColumn).append(" <= ").append(jMax).append(" AND (")
+              .append(n.x).append('*').append(iColumn).append(" + ")
+              .append(n.y).append('*').append(jColumn)
+              .append(") BETWEEN ").append(d1).append(" AND ").append(d2).append(')');
+        }
+    } // class Segment
+
+    protected Segment head;
+
+    protected String iColumn;
+    protected String jColumn;
+
+    public IndexBuffer(List<? extends Point> points) {
+        this(points, I_COLUMN, J_COLUMN);
+    }
+
+    public IndexBuffer(List<? extends Point> points, String iColumn, String jColumn) {
+        this.iColumn = iColumn;
+        this.jColumn = jColumn;
+
+        for (int i = 1, N = points.size(); i < N; ++i) {
+            Point p1 = (Point)points.get(i-1);
+            Point p2 = (Point)points.get(i);
+            head = new Segment(p1, p2, head);
+        }
+    }
+
+    public boolean check(int i, int j) {
+
+        Segment current = head;
+        while (current != null) {
+            if (current.check(i, j)) {
+                return true;
+            }
+            current = current.next;
+        }
+        return false;
+    }
+
+    public String toWhereClause() {
+
+        StringBuilder sb = new StringBuilder();
+
+        Segment current = head;
+
+        while (current != null) {
+            if (current != head) {
+                sb.append(" OR ");
+            }
+            current.toWhereClause(sb, iColumn, jColumn);
+            current = current.next;
+        }
+
+        return sb.toString();
+    }
+
+    public static Point2D.Double sub(Point2D.Double p1, Point2D.Double p2) {
+        return new Point2D.Double(p1.x - p2.x, p1.y - p2.y);
+    }
+
+    public static final double dot(Point2D.Double p1, Point2D.Double p2) {
+        return p1.x*p2.x + p1.y*p2.y;
+    }
+
+    public static final double dot(Point2D.Double p1, double x, double y) {
+        return p1.x*x + p1.y*y;
+    }
+
+    public static final Point2D.Double scale(Point2D.Double p, double s) {
+        return new Point2D.Double(s*p.x, s*p.y);
+    }
+
+    public static final Point2D.Double normalize(Point2D.Double p) {
+        double len2 = Math.sqrt(dot(p, p));
+        return len2 > EPSILON ? scale(p, 1d/len2) : p;
+    }
+
+    public static final Point2D.Double orthogonal(Point2D.Double p) {
+        return new Point2D.Double(p.y, -p.x);
+    }
+}
+// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :