| gvSIG desktop 1

/*

 * Created on 12-sep-2006 by azabala

 *

 */

package com.vividsolutions.jts.geomgraph;

import java.util.Collection;

import java.util.HashMap;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

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

import com.vividsolutions.jts.geom.*;

import com.vividsolutions.jts.geomgraph.*;

import com.vividsolutions.jts.geomgraph.index.EdgeSetIntersector;

import com.vividsolutions.jts.geomgraph.index.SegmentIntersector;

import com.vividsolutions.jts.geomgraph.index.SimpleMCSweepLineIntersector;

import com.vividsolutions.jts.util.Assert;

import com.vividsolutions.jts.algorithm.*;

/**

 */

public class SnappingGeometryGraph extends SnappingPlanarGraph {

        /**

         * This method implements the Boundary Determination Rule

         * for determining whether

         * a component (node or edge) that appears multiple times in elements

         * of a MultiGeometry is in the boundary or the interior of the Geometry

         * <br>

         * The SFS uses the "Mod-2 Rule", which this function implements

         * <br>

         * An alternative (and possibly more intuitive) rule would be

         * the "At Most One Rule":

         *    isInBoundary = (componentCount == 1)

         */

          public static boolean isInBoundary(int boundaryCount)

          {

            // the "Mod-2 Rule"

            return boundaryCount % 2 == 1;

          }

          public static int determineBoundary(int boundaryCount)

          {

            return isInBoundary(boundaryCount) ? Location.BOUNDARY : Location.INTERIOR;

          }

          private Geometry parentGeom;

          /**

           * The lineEdgeMap is a map of the linestring components of the

           * parentGeometry to the edges which are derived from them.

           * This is used to efficiently perform findEdge queries

           */

          private Map lineEdgeMap = new HashMap();

          /**

           * If this flag is true, the Boundary Determination Rule will used when deciding

           * whether nodes are in the boundary or not

           */

          private boolean useBoundaryDeterminationRule = false;

          private int argIndex;  // the index of this geometry as an argument to a spatial function (used for labelling)

          private Collection boundaryNodes;

          private boolean hasTooFewPoints = false;

          private Coordinate invalidPoint = null;

          private EdgeSetIntersector createEdgeSetIntersector()

          {

          // various options for computing intersections, from slowest to fastest

          //private EdgeSetIntersector esi = new SimpleEdgeSetIntersector();

          //private EdgeSetIntersector esi = new MonotoneChainIntersector();

          //private EdgeSetIntersector esi = new NonReversingChainIntersector();

          //private EdgeSetIntersector esi = new SimpleSweepLineIntersector();

          //private EdgeSetIntersector esi = new MCSweepLineIntersector();

            //return new SimpleEdgeSetIntersector();

            return new SimpleMCSweepLineIntersector();

          }

          /**

           * It builds a geometry graph from the parent geometry, applying snapping with

           * the specified snap tolerance

           * 

           * @param argIndex

           * @param parentGeom

           * @param snapTolerance

           */

          public SnappingGeometryGraph(int argIndex, Geometry parentGeom, double snapTolerance) {

                  super(snapTolerance);            

                  this.argIndex = argIndex;

            this.parentGeom = parentGeom;

            if (parentGeom != null) {

                    add(parentGeom);

            }

          }

          public boolean hasTooFewPoints() { 

                  return hasTooFewPoints; 

          }

          public Coordinate getInvalidPoint() { 

                  return invalidPoint; 

          }

          public Geometry getGeometry() { 

                  return parentGeom; 

          }

          public Collection getBoundaryNodes()

          {

            if (boundaryNodes == null)

              boundaryNodes = nodes.getBoundaryNodes(argIndex);

            return boundaryNodes;

          }

          public Coordinate[] getBoundaryPoints()

          {

            Collection coll = getBoundaryNodes();

            Coordinate[] pts = new Coordinate[coll.size()];

            int i = 0;

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

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

              pts[i++] = (Coordinate) node.getCoordinate().clone();

            }

            return pts;

          }

          public Edge findEdge(LineString line)

          {

            return (Edge) lineEdgeMap.get(line);

          }

          public void computeSplitEdges(List edgelist)

          {

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

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

              e.eiList.addSplitEdges(edgelist);

            }

          }

          private void add(Geometry g)

          {

            if (g.isEmpty()) return;

            // check if this Geometry should obey the Boundary Determination Rule

            // all collections except MultiPolygons obey the rule

            if (g instanceof GeometryCollection

                && ! (g instanceof MultiPolygon))

                    useBoundaryDeterminationRule = true;

            if (g instanceof Polygon)                 addPolygon((Polygon) g);

                                // LineString also handles LinearRings

            else if (g instanceof LineString)         addLineString((LineString) g);

            else if (g instanceof Point)              addPoint((Point) g);

            else if (g instanceof MultiPoint)         addCollection((MultiPoint) g);

            else if (g instanceof MultiLineString)    addCollection((MultiLineString) g);

            else if (g instanceof MultiPolygon)       addCollection((MultiPolygon) g);

            else if (g instanceof GeometryCollection) addCollection((GeometryCollection) g);

            else  throw new UnsupportedOperationException(g.getClass().getName());

          }

          private void addCollection(GeometryCollection gc)

          {

            for (int i = 0; i < gc.getNumGeometries(); i++) {

              Geometry g = gc.getGeometryN(i);

              add(g);

            }

          }

          /**

           * Add a Point to the graph.

           */

          private void addPoint(Point p)

          {

            Coordinate coord = p.getCoordinate();

            insertPoint(argIndex, coord, Location.INTERIOR);

          }

          /**

           * The left and right topological location arguments assume that the ring is oriented CW.

           * If the ring is in the opposite orientation,

           * the left and right locations must be interchanged.

           */

          private void addPolygonRing(LinearRing lr, int cwLeft, int cwRight)

          {

            Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(lr.getCoordinates());

            if (coord.length < 4) {

              hasTooFewPoints = true;

              invalidPoint = coord[0];

              return;

            }

            int left  = cwLeft;

            int right = cwRight;

            if (cga.isCCW(coord)) {

              left = cwRight;

              right = cwLeft;

            }

            Edge e = new Edge(coord,

                                new Label(argIndex, Location.BOUNDARY, left, right));

            lineEdgeMap.put(lr, e);

            insertEdge(e);

            // insert the endpoint as a node, to mark that it is on the boundary

            insertPoint(argIndex, coord[0], Location.BOUNDARY);

          }

          private void addPolygon(Polygon p)

          {

            addPolygonRing(

                    (LinearRing) p.getExteriorRing(),

                    Location.EXTERIOR,

                    Location.INTERIOR);

            for (int i = 0; i < p.getNumInteriorRing(); i++) {

              // Holes are topologically labelled opposite to the shell, since

              // the interior of the polygon lies on their opposite side

              // (on the left, if the hole is oriented CW)

              addPolygonRing(

                    (LinearRing) p.getInteriorRingN(i),

                    Location.INTERIOR,

                    Location.EXTERIOR);

            }

          }

          private void addLineString(LineString line)

          {

            Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line.getCoordinates());

            if (coord.length < 2) {

              hasTooFewPoints = true;

              invalidPoint = coord[0];

              return;

            }

            // add the edge for the LineString

            // line edges do not have locations for their left and right sides

            Edge e = new Edge(coord, new Label(argIndex, Location.INTERIOR));

            lineEdgeMap.put(line, e);

            insertEdge(e);

            /**

             * Add the boundary points of the LineString, if any.

             * Even if the LineString is closed, add both points as if they were endpoints.

             * This allows for the case that the node already exists and is a boundary point.

             */

            Assert.isTrue(coord.length >= 2, "found LineString with single point");

            insertBoundaryPoint(argIndex, coord[0]);

            insertBoundaryPoint(argIndex, coord[coord.length - 1]);

          }

          /**

           * Add an Edge computed externally.  The label on the Edge is assumed

           * to be correct.

           */

          public void addEdge(Edge e)

          {

            insertEdge(e);

            Coordinate[] coord = e.getCoordinates();

            // insert the endpoint as a node, to mark that it is on the boundary

            insertPoint(argIndex, coord[0], Location.BOUNDARY);

            insertPoint(argIndex, coord[coord.length - 1], Location.BOUNDARY);

          }

          /**

           * Add a point computed externally.  The point is assumed to be a

           * Point Geometry part, which has a location of INTERIOR.

           */

          public void addPoint(Coordinate pt)

          {

            insertPoint(argIndex, pt, Location.INTERIOR);

          }

          /**

           * Compute self-nodes, taking advantage of the Geometry type to

           * minimize the number of intersection tests.  (E.g. rings are

           * not tested for self-intersection, since they are assumed to be valid).

           * @param li the LineIntersector to use

           * @param computeRingSelfNodes if <false>, intersection checks are optimized to not test rings for self-intersection

           * @return the SegmentIntersector used, containing information about the intersections found

           */

          public SegmentIntersector computeSelfNodes(LineIntersector li, boolean computeRingSelfNodes)

          {

            SegmentIntersector si = new SegmentIntersector(li, true, false);

            EdgeSetIntersector esi = createEdgeSetIntersector();

            // optimized test for Polygons and Rings

            if (! computeRingSelfNodes

                && (parentGeom instanceof LinearRing

                || parentGeom instanceof Polygon

                || parentGeom instanceof MultiPolygon)) {

              esi.computeIntersections(edges, si, false);

            }

            else {

              esi.computeIntersections(edges, si, true);

            }

//        System.out.println("SegmentIntersector # tests = " + si.numTests);

            addSelfIntersectionNodes(argIndex);

            return si;

          }

        /* NOT USED

          public SegmentIntersector computeSelfNodes(LineIntersector li)

          {

            return computeSelfNodes(li, false);

          }

        */

          public SegmentIntersector computeEdgeIntersections(

            GeometryGraph g,

            LineIntersector li,

            boolean includeProper)

          {

            SegmentIntersector si = new SegmentIntersector(li, includeProper, true);

            si.setBoundaryNodes(this.getBoundaryNodes(), g.getBoundaryNodes());

            EdgeSetIntersector esi = createEdgeSetIntersector();

            esi.computeIntersections(edges, g.edges, si);

        /*

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

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

        Debug.print(e.getEdgeIntersectionList());

        }

        */

            return si;

          }

          private void insertPoint(int argIndex, Coordinate coord, int onLocation)

          {

            Node n = nodes.addNode(coord);

            Label lbl = n.getLabel();

            if (lbl == null) {

              n.label = new Label(argIndex, onLocation);

            }

            else

              lbl.setLocation(argIndex, onLocation);

          }

          /**

           * Adds points using the mod-2 rule of SFS.  This is used to add the boundary

           * points of dim-1 geometries (Curves/MultiCurves).  According to the SFS,

           * an endpoint of a Curve is on the boundary

           * iff if it is in the boundaries of an odd number of Geometries

           */

          private void insertBoundaryPoint(int argIndex, Coordinate coord)

          {

            Node n = nodes.addNode(coord);

            Label lbl = n.getLabel();

            // the new point to insert is on a boundary

            int boundaryCount = 1;

            // determine the current location for the point (if any)

            int loc = Location.NONE;

            if (lbl != null) loc = lbl.getLocation(argIndex, Position.ON);

            if (loc == Location.BOUNDARY) boundaryCount++;

            // determine the boundary status of the point according to the Boundary Determination Rule

            int newLoc = determineBoundary(boundaryCount);

            lbl.setLocation(argIndex, newLoc);

          }

          private void addSelfIntersectionNodes(int argIndex)

          {

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

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

              int eLoc = e.getLabel().getLocation(argIndex);

              for (Iterator eiIt = e.eiList.iterator(); eiIt.hasNext(); ) {

                EdgeIntersection ei = (EdgeIntersection) eiIt.next();

                addSelfIntersectionNode(argIndex, ei.coord, eLoc);

              }

            }

          }

          /**

           * Add a node for a self-intersection.

           * If the node is a potential boundary node (e.g. came from an edge which

           * is a boundary) then insert it as a potential boundary node.

           * Otherwise, just add it as a regular node.

           */

          private void addSelfIntersectionNode(int argIndex, Coordinate coord, int loc)

          {

            // if this node is already a boundary node, don't change it

            if (isBoundaryNode(argIndex, coord)) return;

            if (loc == Location.BOUNDARY && useBoundaryDeterminationRule)

                insertBoundaryPoint(argIndex, coord);

            else

              insertPoint(argIndex, coord, loc);

          }

}