--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gnv-artifacts/src/main/java/de/intevation/gnv/math/GridCell.java	Fri Sep 28 12:13:49 2012 +0200
@@ -0,0 +1,159 @@
+package de.intevation.gnv.math;
+
+import com.vividsolutions.jts.geom.Coordinate;
+import com.vividsolutions.jts.geom.Envelope;
+import com.vividsolutions.jts.geom.Geometry;
+import com.vividsolutions.jts.geom.GeometryFactory;
+import com.vividsolutions.jts.geom.LinearRing;
+import com.vividsolutions.jts.geom.Point;
+import com.vividsolutions.jts.geom.Polygon;
+
+import com.vividsolutions.jts.index.ItemVisitor;
+
+import java.io.Serializable;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+
+import org.apache.log4j.Logger;
+
+/**
+ *  @author Sascha L. Teichmann (sascha.teichmann@intevation.de)
+ */
+public class GridCell
+implements   Serializable
+{
+    private static Logger log = Logger.getLogger(GridCell.class);
+
+    public static final class CellFinder
+    implements                ItemVisitor
+    {
+        public    GridCell found;
+
+        protected Point    point;
+
+        public CellFinder() {
+        }
+
+        public void prepare(Coordinate center) {
+            found = null;
+            point = GEOMETRY_FACTORY.createPoint(center);
+        }
+
+        public void visitItem(Object item) {
+            if (found == null) {
+                GridCell cell = (GridCell)item;
+                if (cell.contains(point)) {
+                    found = cell;
+                }
+            }
+        }
+    } // class CellFinder
+
+    public Point2d p1;
+    public Point2d p2;
+    public Point2d p3;
+    public Point2d p4;
+
+    protected Polygon polygon;
+
+    public static final GeometryFactory GEOMETRY_FACTORY
+        = new GeometryFactory();
+
+    public GridCell() {
+    }
+
+    public GridCell(Point2d p1, Point2d p2, Point2d p3, Point2d p4) {
+        this.p1 = p1;
+        this.p2 = p2;
+        this.p3 = p3;
+        this.p4 = p4;
+        createPolygon();
+    }
+
+    protected void createPolygon() {
+        LinearRing shell = GEOMETRY_FACTORY
+            .createLinearRing(new Coordinate [] { p1, p2, p3, p4, p1 });
+        polygon = GEOMETRY_FACTORY.createPolygon(shell, null);
+    }
+
+    public Envelope getEnvelope() {
+        return polygon.getEnvelopeInternal();
+    }
+
+    public boolean contains(Geometry coord) {
+        return polygon.contains(coord);
+    }
+
+    public static List<GridCell> pointsToGridCells(
+        List<? extends Point2d> points
+    ) {
+        return pointsToGridCells(points, null);
+    }
+
+    public static List<GridCell> pointsToGridCells(
+        List<? extends Point2d> points,
+        Envelope                relevantArea
+    ) {
+        int minI = Integer.MAX_VALUE;
+        int maxI = Integer.MIN_VALUE;
+        int minJ = Integer.MAX_VALUE;
+        int maxJ = Integer.MIN_VALUE;
+
+        HashMap<Integer, HashMap<Integer, Point2d>> rows =
+            new HashMap<Integer, HashMap<Integer, Point2d>>();
+
+        int culled = 0;
+
+        for (Point2d p: points) {
+
+            if (relevantArea != null && !relevantArea.contains(p.x, p.y)) {
+                ++culled;
+                continue;
+            }
+
+            if (p.i < minI) minI = p.i;
+            if (p.i > maxI) maxI = p.i;
+            if (p.j < minJ) minJ = p.j;
+            if (p.j > maxJ) maxJ = p.j;
+
+            HashMap<Integer, Point2d> row = rows.get(p.i);
+
+            if (row == null) {
+                rows.put(p.i, row = new HashMap<Integer, Point2d>());
+            }
+
+            row.put(p.j, p);
+        }
+
+        ArrayList<GridCell> cells = new ArrayList<GridCell>(points.size());
+
+        for (int i = minI + 1; i <= maxI; ++i) {
+            HashMap<Integer, Point2d> row1 = rows.get(i-1);
+            HashMap<Integer, Point2d> row2 = rows.get(i);
+            if (row1 != null && row2 != null) {
+                for (int j = minJ + 1; j < maxJ; ++j) {
+                    Point2d p1 = row1.get(j-1);
+                    Point2d p2 = row1.get(j);
+                    Point2d p3 = row2.get(j);
+                    Point2d p4 = row2.get(j-1);
+
+                    if (p1 != null && p2 != null &&  p3 != null && p4 != null) {
+                        cells.add(new GridCell(p1, p2, p3, p4));
+                    }
+                } // for all columns in row
+            }
+        } // for all rows
+
+        if (log.isDebugEnabled()) {
+            log.debug("culled points: " + culled);
+            log.debug("min/max i: " + minI + " / " + maxI);
+            log.debug("min/max j: " + minJ + " / " + maxJ);
+            log.debug("cells found: " + cells.size());
+        }
+
+        return cells;
+    }
+}
+// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :