# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1320002939 0
# Node ID fe7f9264a2edb56311076f27771f501c2e48ad49
# Parent  2ad7ba85a2b3c46cd91f80731156c010b6454a67
Interim checkin for polygon calculation.

flys-artifacts/trunk@3118 c6561f87-3c4e-4783-a992-168aeb5c3f6f

diff -r 2ad7ba85a2b3 -r fe7f9264a2ed flys-artifacts/ChangeLog
--- a/flys-artifacts/ChangeLog	Fri Oct 28 16:59:03 2011 +0000
+++ b/flys-artifacts/ChangeLog	Sun Oct 30 19:28:59 2011 +0000
@@ -1,3 +1,8 @@
+2011-10-30	Sascha L. Teichmann	<sascha.teichmann@intevation.de>
+
+	* src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java:
+	  Interim check in. Work in progress.
+
 2011-10-28	Sascha L. Teichmann	<sascha.teichmann@intevation.de>
 
 	* src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java: New.
diff -r 2ad7ba85a2b3 -r fe7f9264a2ed flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java
--- a/flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java	Fri Oct 28 16:59:03 2011 +0000
+++ b/flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java	Sun Oct 30 19:28:59 2011 +0000
@@ -1,7 +1,5 @@
 package de.intevation.flys.geom;
 
-import gnu.trove.TDoubleArrayList;
-
 import java.io.Serializable;
 
 import java.awt.Shape;
@@ -18,10 +16,20 @@
 public class Polygon2D
 implements   Serializable
 {
+    public static final double EPSILON = 1e-4;
+
+    private static final double X(Point2D p) {
+        return p.getX();
+    }
+
+    private static final double Y(Point2D p) {
+        return p.getY();
+    }
+
     public static final Comparator<Point2D> POINT_X_CMP =
         new Comparator<Point2D>() {
             public int compare(Point2D a, Point2D b) {
-                double d = a.getX() - b.getX();
+                double d = X(a) - X(b);
                 if (d < 0d) return -1;
                 return d > 0d ? + 1 : 0;
             }
@@ -32,32 +40,120 @@
             public int compare(Point2D [] a, Point2D [] b) {
                 if (a.length == 0) return -1; // should not happen.
                 if (b.length == 0) return +1; // should not happen.
-                double d = a[0].getX() - b[0].getX();
+                double d = X(a[0]) - Y(b[0]);
                 if (d < 0d) return -1;
                 return d > 0d ? + 1 : 0;
             }
         };
 
-    protected TDoubleArrayList xs;
-    protected TDoubleArrayList ys;
+    protected List<Point2D> points;
 
     public Polygon2D() {
-        xs = new TDoubleArrayList();
-        ys = new TDoubleArrayList();
+        points = new ArrayList<Point2D>();
+    }
+
+    public static boolean epsilonEquals(Point2D a, Point2D b) {
+        return Math.abs(X(a)-X(b)) < EPSILON 
+            && Math.abs(Y(a)-Y(b)) < EPSILON;
     }
 
     public void add(double x, double y) {
-        xs.add(x);
-        ys.add(y);
+        points.add(new Point2D.Double(x, y));
+    }
+
+    public boolean addCheck(Point2D p) {
+        switch (points.size()) {
+            case 0:
+                points.add(p);
+                return true;
+            case 1:
+                if (epsilonEquals(points.get(0), p)) {
+                    return false;
+                }
+                points.add(p);
+                return true;
+            default:
+                int L = points.size()-1;
+                Point2D last = points.get(L);
+                if (epsilonEquals(last, p)) {
+                    return false;
+                }
+                Point2D before = points.get(L-1);
+                if (collinear(before, last, p)) {
+                    points.set(L, p);
+                }
+                else {
+                    points.add(p);
+                }
+                return true;
+        }
+    }
+
+    public void addReversed(List<Point2D> other) {
+        for (int i = other.size()-1; i >= 0; --i) {
+            addCheck(other.get(i));
+        }
+    }
+
+    private static final double L1(Point2D a, Point2D b) {
+        return Math.abs(X(a)-X(b)) + Math.abs(Y(a)-Y(b));
+    }
+
+    public static boolean collinear(Point2D a, Point2D b, Point2D c) {
+        double dab = L1(a, b);
+        double dac = L1(a, c);
+        double dbc = L1(b, c);
+
+        Point2D p1, p2, p3;
+
+        if (dab > dac) {
+            if (dab > dbc) {
+                p1 = a;
+                p2 = b;
+                p3 = c;
+            }
+            else { // dbc >= dab
+                p1 = b;
+                p2 = c;
+                p3 = a;
+            }
+        }
+        else { // dac >= dab
+            if (dac > dbc) {
+                p1 = a;
+                p2 = c;
+                p3 = b;
+            }
+            else { // dbc >= dac
+                p1 = b;
+                p2 = c;
+                p3 = a;
+            }
+        }
+
+        // TODO: Continue here.
+
+
+        return true;
+    }
+
+    public static Point2D sub(Point2D a, Point2D b) {
+        return new Point2D.Double(X(a)-X(b), Y(a)-Y(b));
+    }
+
+    public static Point2D scale(Point2D a, double s) {
+        return new Point2D.Double(s*X(a), s*Y(a));
     }
 
     public double area() {
         double area = 0d;
 
-		for (int i = 0, N = xs.size(); i < N; ++i) {
+		for (int i = 0, N = points.size(); i < N; ++i) {
 			int j = (i + 1) % N;
-			area += xs.getQuick(i)*ys.getQuick(j);
-			area -= xs.getQuick(j)*ys.getQuick(i);
+            Point2D pi = points.get(i);
+            Point2D pj = points.get(j);
+			area += X(pi)*Y(pj);
+			area -= X(pj)*Y(pi);
 		}
 
         return 0.5d*area;
@@ -66,12 +162,14 @@
     public Shape toShape() {
         Path2D.Double path = new Path2D.Double();
 
-        int N = xs.size();
+        int N = points.size();
 
         if (N > 0) {
-            path.moveTo(xs.getQuick(0), ys.getQuick(0));
+            Point2D p = points.get(0);
+            path.moveTo(X(p), Y(p));
             for (int i = 1; i < N; ++i) {
-                path.lineTo(xs.getQuick(i), ys.getQuick(i));
+                p = points.get(i);
+                path.lineTo(X(p), Y(p));
             }
             path.closePath();
         }
@@ -111,6 +209,40 @@
         return parts;
     }
 
+    protected static boolean removeNoneIntersecting(
+        List<Point2D []> As,
+        List<Point2D []> Bs
+    ) {
+        OUTER: for (int i = 0; i < As.size();) {
+            Point2D [] a = As.get(i);
+            int lo = 0, hi = Bs.size()-1;
+            while (lo <= hi) {
+                int mid = (lo + hi) >> 1;
+                Point2D [] b = Bs.get(mid);
+                     if (X(a[0]) > X(b[b.length-1])) lo = mid+1;
+                else if (X(a[a.length-1]) < X(b[0])) hi = mid-1;
+                else {
+                    // found: keep
+                    ++i;
+                    continue OUTER;
+                }
+            }
+            // not found: remove
+            As.remove(i);
+        }
+
+        return As.isEmpty();
+    }
+
+    protected static void buildPolygons(
+        Point2D []      as,
+        Point2D []      bs,
+        Point2D [][]    rest,
+        List<Polygon2D> positives,
+        List<Polygon2D> negatives
+    ) {
+    }
+
     public static void createPolygons(
         double [] xAs, double [] yAs,
         double [] xBs, double [] yBs,
@@ -150,21 +282,19 @@
         Point2D [] p1 = splAs.get(0);
         Point2D [] p2 = splBs.get(splBs.size()-1);
 
-        // First of As greater than last of Bs.
-        if (POINT_X_CMP.compare(p1[0], p2[p2.length-1]) > 0) {
-            return;
-        }
-
-        p2 = splAs.get(splAs.size()-1);
-        p1 = splBs.get(0);
-
-        //  First of Bs greater than last of As.
-        if (POINT_X_CMP.compare(p1[0], p2[p2.length-1]) > 0) {
+        // Sort out the ranges that are not intersecting
+        // the ranges in the other series.
+        // We are going to merge them anyway
+        // so this is not strictly required. 
+        // Keep it to recude cases.
+        if (removeNoneIntersecting(splAs, splBs)
+        ||  removeNoneIntersecting(splBs, splAs)
+        ) {
+            // They do not intersect at all.
             return;
         }
 
         // TODO: Intersect/split the two series parts.
-
     }
 }
 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :