| gvSIG desktop 1

/*

 * Created on 12-sep-2006 by azabala

 *

 */

package com.iver.cit.gvsig.fmap.topology;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import com.iver.cit.gvsig.fmap.topology.geomgraph.SnappingPlanarGraph;

import com.vividsolutions.jts.algorithm.LineIntersector;

import com.vividsolutions.jts.algorithm.PointLocator;

import com.vividsolutions.jts.algorithm.RobustLineIntersector;

import com.vividsolutions.jts.geom.Coordinate;

import com.vividsolutions.jts.geom.Geometry;

import com.vividsolutions.jts.geom.GeometryFactory;

import com.vividsolutions.jts.geom.Location;

import com.vividsolutions.jts.geomgraph.Depth;

import com.vividsolutions.jts.geomgraph.DirectedEdge;

import com.vividsolutions.jts.geomgraph.DirectedEdgeStar;

import com.vividsolutions.jts.geomgraph.Edge;

import com.vividsolutions.jts.geomgraph.EdgeList;

import com.vividsolutions.jts.geomgraph.Label;

import com.vividsolutions.jts.geomgraph.Node;

import com.vividsolutions.jts.geomgraph.PlanarGraph;

import com.vividsolutions.jts.geomgraph.Position;

import com.vividsolutions.jts.geomgraph.SnappingGeometryGraph;

import com.vividsolutions.jts.io.ParseException;

import com.vividsolutions.jts.operation.overlay.LineBuilder;

import com.vividsolutions.jts.operation.overlay.OverlayNodeFactory;

import com.vividsolutions.jts.operation.overlay.OverlayOp;

import com.vividsolutions.jts.operation.overlay.PointBuilder;

import com.vividsolutions.jts.operation.overlay.PolygonBuilder;

import com.vividsolutions.jts.util.Assert;

/**

 */

public class SnappingOverlayOperation extends OverlayOp {

        private final PointLocator ptLocator = new PointLocator();

        private GeometryFactory geomFact;

        private Geometry resultGeom;

        protected final LineIntersector li;

        /*Planar graph of the overlay operation*/

        private SnappingPlanarGraph graph;

        /*Geometry graph of each individual geometry*/

        private SnappingGeometryGraph[] arg;

        /*It saves all the new edges resulting from intersections of

         * edges of geometries A and B. It is a temporal repository, before

         * to save them in SnappingPlanarGraph*/

        private EdgeList edgeList = new EdgeList();

/*

 * El resultado de una operacion de overlay puede contener

 * puntos, lineas y poligonos.

 * */        

        private List resultPolyList = new ArrayList();

        private List resultLineList = new ArrayList();

        private List resultPointList = new ArrayList();

        public static Geometry overlayOp(Geometry geom0, Geometry geom1,

                        int opCode, double tolerance) {

                SnappingOverlayOperation gov = new SnappingOverlayOperation(geom0,

                                geom1, tolerance);

                Geometry geomOv = gov.getResultGeometry(opCode);

                return geomOv;

        }

        public SnappingOverlayOperation(Geometry g0, Geometry g1, double tolerance) {

                super(g0, g1);

                graph = new SnappingPlanarGraph(new OverlayNodeFactory(), tolerance);

                arg = new SnappingGeometryGraph[2];

                arg[0] = new SnappingGeometryGraph(tolerance, 0, g0);

                arg[1] = new SnappingGeometryGraph(tolerance, 1, g1);

                geomFact = g0.getFactory();

                li = new SnapLineIntersector(tolerance);

        }

        public Geometry getResultGeometry(int funcCode) {

                computeOverlay(funcCode);

                return resultGeom;

        }

        public PlanarGraph getGraph() {

                return graph;

        }

        /*

         * ************************************************************

         * METODO PRINCIPAL

         * ************************************************************

         * */

        private void computeOverlay(int opCode) {

                /*

                 * Se copian los NODOS de las dos geometrias. 

                 * ESTO ES IMPORTANTE, PUES:

                 * a) un punto origina un nodo.

                 * b) una linea origina dos nodos

                 * c) un poligono origina un nodo.

                 * 

                 * */

                copyPoints(0);

                copyPoints(1);

                graph.dumpNodes();

                /*

                 * Empieza a ver las intersecciones que existen entre los 

                 * Edges de las geometrias de entrada (por ejemplo, en una

                 * multigeometria, entre sus elementos)

                 * 

                 * TODO Cambiar Edge, EdgeIntersectionList para que aplique

                 * snapping

                 * 

                 * */

                arg[0].computeSelfNodes(li, false);

                arg[1].computeSelfNodes(li, false);

                /*

                 * Calcula las intersecciones.

                 * Se supone que daran lugar a Nodes, ?NO?

                 * Como resultado, cada Edge guardar? en sus EdgeIntersectionList

                 * las intersecciones que hay en sus segmentos (EdgeIntersection).

                 * 

                 * Estas intersecciones se representan por:

                 * -segmento del edge en que ocurren.

                 * -coordenada

                 * -distancia al primer vertice del segmento

                 * 

                 * ?OJO? COMO RESULTADO DE ESTO NO SE GENERAN EJES NUEVOS.

                 * PARA HACER SNAP EN LAS INTERSECCIONES TENDRIAMOS QUE RETOCAR LA 

                 * CLASE EDGEINTERSECTIONLIST

                 * 

                 * */

                arg[0].computeEdgeIntersections(arg[1], li, true);

                /*

                 * Ahora lo que se hace es: para cada Edge del grafo,

                 * se parte (en funci?n de sus intersecciones) y se a?aden

                 * los Edges fragmentados a la colecci?n baseSplitEdges

                 * 

                 * */

                List baseSplitEdges = new ArrayList();

                arg[0].computeSplitEdges(baseSplitEdges);

                arg[1].computeSplitEdges(baseSplitEdges);

                /*

                 * Edges resulting of A intersection B, that are in baseSplitEdges 

                 * Collection, are saved in EdgeList.

                 * ?OJO? Si aparecen ejes repetidos, no se duplican (pero si 

                 * que se cambia su etiqueta)

                 * */

                //Se copian los nuevos Edges generados en EdgeList

                insertUniqueEdges(baseSplitEdges);

                /*Se etiquetan*/

                computeLabelsFromDepths();

                /*

                 * Quita los Edges que hayan sufrido colapso dimensional

                 * (en la documentac?on de JTS viene algo de esto)

                 * */

                replaceCollapsedEdges();

        /*

         * Finalmente, se a?ade al SnappingPlanarGraph resultado los Edges

         * calculados como fruto de las intersecciones (contenidos en EdgeList).

         * 

         * Aqu? se hace algo muy importante tambi?n: se a?aden nuevos nodos

         * al grafo (correspondientes con los extremos de los nuevos Edge

         * que no estuvieran ya en el grafo)

         * 

         * */

                graph.addEdges(edgeList.getEdges());

                computeLabelling();

                labelIncompleteNodes();

                /**

                 * The ordering of building the result Geometries is important. Areas

                 * must be built before lines, which must be built before points. This

                 * is so that lines which are covered by areas are not included

                 * explicitly, and similarly for points.

                 */

                findResultAreaEdges(opCode);

                cancelDuplicateResultEdges();

                PolygonBuilder polyBuilder = new PolygonBuilder(geomFact, cga);

                polyBuilder.add(graph);

                resultPolyList = polyBuilder.getPolygons();

                LineBuilder lineBuilder = new LineBuilder(this, geomFact, ptLocator);

                resultLineList = lineBuilder.build(opCode);

                PointBuilder pointBuilder = new PointBuilder(this, geomFact, ptLocator);

                resultPointList = pointBuilder.build(opCode);

                // gather the results from all calculations into a single Geometry for

                // the result set

                resultGeom = computeGeometry(resultPointList, resultLineList,

                                resultPolyList);

        }

        private void insertUniqueEdges(List edges) {

                for (Iterator i = edges.iterator(); i.hasNext();) {

                        Edge e = (Edge) i.next();

                        insertUniqueEdge(e);

                }

        }

        /**

         * Insert an edge from one of the noded input graphs. Checks edges that are

         * inserted to see if an identical edge already exists. If so, the edge is

         * not inserted, but its label is merged with the existing edge.

         */

        protected void insertUniqueEdge(Edge e) {

                //TODO Crear una clase SnapEdge y SnapEdgeList puede ser necesario???

                //creo que si pq SnapEdgeList mantiene una cache que no considera snap

                Edge existingEdge = edgeList.findEqualEdge(e);

                // If an identical edge already exists, simply update its label

                if (existingEdge != null) {

                        Label existingLabel = existingEdge.getLabel();

                        Label labelToMerge = e.getLabel();

                        // check if new edge is in reverse direction to existing edge

                        // if so, must flip the label before merging it

                        if (!existingEdge.isPointwiseEqual(e)) {

                                labelToMerge = new Label(e.getLabel());

                                labelToMerge.flip();

                        }

                        Depth depth = existingEdge.getDepth();

                        // if this is the first duplicate found for this edge, initialize

                        // the depths

                        if (depth.isNull()) {

                                depth.add(existingLabel);

                        }

                        depth.add(labelToMerge);

                        existingLabel.merge(labelToMerge);

                } else { // no matching existing edge was found

                        // add this new edge to the list of edges in this graph

                        edgeList.add(e);

                }

        }

        /**

         * Update the labels for edges according to their depths. For each edge, the

         * depths are first normalized. Then, if the depths for the edge are equal,

         * this edge must have collapsed into a line edge. If the depths are not

         * equal, update the label with the locations corresponding to the depths

         * (i.e. a depth of 0 corresponds to a Location of EXTERIOR, a depth of 1

         * corresponds to INTERIOR)

         */

        private void computeLabelsFromDepths() {

                for (Iterator it = edgeList.iterator(); it.hasNext();) {

                        Edge e = (Edge) it.next();

                        Label lbl = e.getLabel();

                        Depth depth = e.getDepth();

                        /*

                         * Only check edges for which there were duplicates, since these are

                         * the only ones which might be the result of dimensional collapses.

                         */

                        if (!depth.isNull()) {

                                depth.normalize();

                                for (int i = 0; i < 2; i++) {

                                        if (!lbl.isNull(i) && lbl.isArea() && !depth.isNull(i)) {

                                                /**

                                                 * if the depths are equal, this edge is the result of

                                                 * the dimensional collapse of two or more edges. It has

                                                 * the same location on both sides of the edge, so it

                                                 * has collapsed to a line.

                                                 */

                                                if (depth.getDelta(i) == 0) {

                                                        lbl.toLine(i);

                                                } else {

                                                        /**

                                                         * This edge may be the result of a dimensional

                                                         * collapse, but it still has different locations on

                                                         * both sides. The label of the edge must be updated

                                                         * to reflect the resultant side locations indicated

                                                         * by the depth values.

                                                         */

                                                        Assert

                                                                        .isTrue(!depth.isNull(i, Position.LEFT),

                                                                                        "depth of LEFT side has not been initialized");

                                                        lbl.setLocation(i, Position.LEFT, depth

                                                                        .getLocation(i, Position.LEFT));

                                                        Assert

                                                                        .isTrue(!depth.isNull(i, Position.RIGHT),

                                                                                        "depth of RIGHT side has not been initialized");

                                                        lbl.setLocation(i, Position.RIGHT, depth

                                                                        .getLocation(i, Position.RIGHT));

                                                }

                                        }

                                }

                        }

                }

        }

        /**

         * If edges which have undergone dimensional collapse are found, replace

         * them with a new edge which is a L edge

         */

        private void replaceCollapsedEdges() {

                List newEdges = new ArrayList();

                for (Iterator it = edgeList.iterator(); it.hasNext();) {

                        Edge e = (Edge) it.next();

                        if (e.isCollapsed()) {

                                //        Debug.print(e);

                                it.remove();

                                newEdges.add(e.getCollapsedEdge());

                        }

                }

                edgeList.addAll(newEdges);

        }

        /**

         * Copy all nodes from an arg geometry into this graph. The node label in

         * the arg geometry overrides any previously computed label for that

         * argIndex. (E.g. a node may be an intersection node with a previously

         * computed label of BOUNDARY, but in the original arg Geometry it is

         * actually in the interior due to the Boundary Determination Rule)

         */

        private void copyPoints(int argIndex) {

                for (Iterator i = arg[argIndex].getNodeIterator(); i.hasNext();) {

                        Node graphNode = (Node) i.next();

                        Node newNode = graph.addNode(graphNode.getCoordinate());

                        newNode.setLabel(argIndex, graphNode.getLabel().getLocation(

                                        argIndex));

                }

        }

        /**

         * Compute initial labelling for all DirectedEdges at each node. In this

         * step, DirectedEdges will acquire a complete labelling (i.e. one with

         * labels for both Geometries) only if they are incident on a node which has

         * edges for both Geometries

         */

        private void computeLabelling() {

                for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) {

                        Node node = (Node) nodeit.next();

                        node.getEdges().computeLabelling(arg);

                }

                mergeSymLabels();

                updateNodeLabelling();

        }

        /**

         * For nodes which have edges from only one Geometry incident on them, the

         * previous step will have left their dirEdges with no labelling for the

         * other Geometry. However, the sym dirEdge may have a labelling for the

         * other Geometry, so merge the two labels.

         */

        private void mergeSymLabels() {

                for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) {

                        Node node = (Node) nodeit.next();

                        ((DirectedEdgeStar) node.getEdges()).mergeSymLabels();

                        //        node.print(System.out);

                }

        }

        private void updateNodeLabelling() {

                // update the labels for nodes

                // The label for a node is updated from the edges incident on it

                // (Note that a node may have already been labelled

                // because it is a point in one of the input geometries)

                for (Iterator nodeit = graph.getNodes().iterator(); nodeit.hasNext();) {

                        Node node = (Node) nodeit.next();

                        Label lbl = ((DirectedEdgeStar) node.getEdges()).getLabel();

                        node.getLabel().merge(lbl);

                }

        }

        /**

         * Incomplete nodes are nodes whose labels are incomplete. (e.g. the

         * location for one Geometry is null). These are either isolated nodes, or

         * nodes which have edges from only a single Geometry incident on them.

         * 

         * Isolated nodes are found because nodes in one graph which don't intersect

         * nodes in the other are not completely labelled by the initial process of

         * adding nodes to the nodeList. To complete the labelling we need to check

         * for nodes that lie in the interior of edges, and in the interior of

         * areas.

         * <p>

         * When each node labelling is completed, the labelling of the incident

         * edges is updated, to complete their labelling as well.

         */

        private void labelIncompleteNodes() {

                for (Iterator ni = graph.getNodes().iterator(); ni.hasNext();) {

                        Node n = (Node) ni.next();

                        Label label = n.getLabel();

                        if (n.isIsolated()) {

                                if (label.isNull(0))

                                        labelIncompleteNode(n, 0);

                                else

                                        labelIncompleteNode(n, 1);

                        }

                        // now update the labelling for the DirectedEdges incident on this

                        // node

                        ((DirectedEdgeStar) n.getEdges()).updateLabelling(label);

                        //        n.print(System.out);

                }

        }

        /**

         * Label an isolated node with its relationship to the target geometry.

         */

        private void labelIncompleteNode(Node n, int targetIndex) {

                int loc = ptLocator.locate(n.getCoordinate(), arg[targetIndex]

                                .getGeometry());

                n.getLabel().setLocation(targetIndex, loc);

        }

        /**

         * Find all edges whose label indicates that they are in the result area(s),

         * according to the operation being performed. Since we want polygon shells

         * to be oriented CW, choose dirEdges with the interior of the result on the

         * RHS. Mark them as being in the result. Interior Area edges are the result

         * of dimensional collapses. They do not form part of the result area

         * boundary.

         */

        private void findResultAreaEdges(int opCode) {

                for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext();) {

                        DirectedEdge de = (DirectedEdge) it.next();

                        // mark all dirEdges with the appropriate label

                        Label label = de.getLabel();

                        if (label.isArea()

                                        && !de.isInteriorAreaEdge()

                                        && isResultOfOp(label.getLocation(0, Position.RIGHT), label

                                                        .getLocation(1, Position.RIGHT), opCode)) {

                                de.setInResult(true);

                                //        Debug.print("in result "); Debug.println(de);

                        }

                }

        }

        /**

         * If both a dirEdge and its sym are marked as being in the result, cancel

         * them out.

         */

        private void cancelDuplicateResultEdges() {

                // remove any dirEdges whose sym is also included

                // (they "cancel each other out")

                for (Iterator it = graph.getEdgeEnds().iterator(); it.hasNext();) {

                        DirectedEdge de = (DirectedEdge) it.next();

                        DirectedEdge sym = de.getSym();

                        if (de.isInResult() && sym.isInResult()) {

                                de.setInResult(false);

                                sym.setInResult(false);

                                //        Debug.print("cancelled "); Debug.println(de);

                                // Debug.println(sym);

                        }

                }

        }

        /**

         * This method is used to decide if a point node should be included in the

         * result or not.

         * 

         * @return true if the coord point is covered by a result Line or Area

         *         geometry

         */

        public boolean isCoveredByLA(Coordinate coord) {

                if (isCovered(coord, resultLineList))

                        return true;

                if (isCovered(coord, resultPolyList))

                        return true;

                return false;

        }

        /**

         * This method is used to decide if an L edge should be included in the

         * result or not.

         * 

         * @return true if the coord point is covered by a result Area geometry

         */

        public boolean isCoveredByA(Coordinate coord) {

                if (isCovered(coord, resultPolyList))

                        return true;

                return false;

        }

        /**

         * @return true if the coord is located in the interior or boundary of a

         *         geometry in the list.

         */

        private boolean isCovered(Coordinate coord, List geomList) {

                for (Iterator it = geomList.iterator(); it.hasNext();) {

                        Geometry geom = (Geometry) it.next();

                        int loc = ptLocator.locate(coord, geom);

                        if (loc != Location.EXTERIOR)

                                return true;

                }

                return false;

        }

        private Geometry computeGeometry(List resultPointList, List resultLineList,

                        List resultPolyList) {

                List geomList = new ArrayList();

                // element geometries of the result are always in the order P,L,A

                geomList.addAll(resultPointList);

                geomList.addAll(resultLineList);

                geomList.addAll(resultPolyList);

                // build the most specific geometry possible

                return geomFact.buildGeometry(geomList);

        }

        public static void main(String[] args){

                GeometryFactory factory = new GeometryFactory();

                com.vividsolutions.jts.io.WKTReader reader = new com.vividsolutions.jts.io.WKTReader(factory);

                Geometry a, b;

                try {

//                        a = reader.read("POLYGON ((7.008775237210479 383.60542879370206, 10.016604662315718 383.60542879370206 , 10.016604662315718 386.67903531618094, 7.008775237210479 386.67903531618094, 7.008775237210479 383.60542879370206))");

//                        Geometry b = reader.read("POLYGON ((13.024434087420959 383.60542879370206, 12.655055089709187 383.60542879370206, 7.008775237210479 389.375185029807 , 7.008775237210479 389.75264183865977, 13.024434087420959 383.60542879370206))");

                        //TODO METER ESTO EN JUNIT

                        a = reader.read("LINESTRING(0.001 0.001, 5.001 5.001)");

                        b = reader.read("LINESTRING(2.1 -3, 0.0 -0.001, -2.22 4.88, 10.0 10.0, 5.002 5.002)");

                        System.out.println(SnappingOverlayOperation.overlayOp(a, b, OverlayOp.INTERSECTION, 0.01));

                } catch (ParseException e) {

                        e.printStackTrace();

                }

        }

}