Application: gvSIG desktop » gvSIG tools: Vector editing

/**

 * gvSIG. Desktop Geographic Information System.

 *

 * Copyright ? 2007-2014 gvSIG Association

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2

 * of the License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,

 * MA  02110-1301, USA.

 *

 * For any additional information, do not hesitate to contact us

 * at info AT gvsig.com, or visit our website www.gvsig.com.

 */

package org.gvsig.vectorediting.lib.prov.split.operation.splitsurface;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

import com.vividsolutions.jts.algorithm.CGAlgorithms;

import com.vividsolutions.jts.geom.Coordinate;

import com.vividsolutions.jts.geom.CoordinateArrays;

import com.vividsolutions.jts.geom.GeometryFactory;

import com.vividsolutions.jts.geom.LineString;

import com.vividsolutions.jts.geom.LinearRing;

import com.vividsolutions.jts.geom.Location;

import com.vividsolutions.jts.geom.Polygon;

import com.vividsolutions.jts.geomgraph.DirectedEdge;

import com.vividsolutions.jts.geomgraph.Node;

import org.gvsig.fmap.geom.Geometry;

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.GeometryManager;

import org.gvsig.fmap.geom.operation.GeometryOperationContext;

import org.gvsig.fmap.geom.operation.GeometryOperationException;

import org.gvsig.fmap.geom.operation.GeometryOperationNotSupportedException;

import org.gvsig.vectorediting.lib.prov.split.operation.SplitOperation;

/**

 * This class is based in the AXIOS team work for UDIG project.

 * 

 * @author llmarques

 *

 */

/*

 * Performs a split of a LineString, MultiLineString, Polygon or MultiPolygon

 * using a provided

 * LineString as cutting edge.

 * 

 * @author Gabriel Rold?n, Axios Engineering

 * 

 * @author Mauricio Pazos, Axios Engineering

 * 

 * @since 1.1.0

 */

public class SurfaceSplitOperation implements SplitOperation {

    /**

     * Strategy:

     * <ul>

     * <li>Build a graph with all edges and intersection nodes between polygon

     * and linestring.

     * <li>Weigth the amount of nodes according to the number of incident edges.

     * Nodes are only the intersection beetween polygon bondary and linestring

     * and initial points of each part of boundary.

     * <li>Weigth edges according to shared (linestring node) or non shared

     * (boundary of polygon). Store edge cordinates at edge.

     * <li>Iterate over node graph. Start at any node, starting at its first

     * segment.

     * <li>Iterate always to next node, choosing the edge that its first

     * linestring segment that has less left angle (CCW) with the last segment

     * of edge linestring.

     * <li>Delete non shared used edges that was used

     * <li>Decrease weight at 1 of used nodes

     * <li>Delete of graph nodes with weight 1

     * </ul>

     * 

     * @author Gabriel Rold?n, Axios Engineering

     * @author Mauricio Pazos, Axios Engineering

     * @since 1.1.0

     */

    public Geometry split(Geometry geometryToBeSplitted, Geometry splitter)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException {

        com.vividsolutions.jts.geom.Geometry jtsGeom =

            (com.vividsolutions.jts.geom.Geometry) geometryToBeSplitted

                .invokeOperation("toJTS", null);

        com.vividsolutions.jts.geom.Geometry jtsSplitter =

            (com.vividsolutions.jts.geom.Geometry) splitter.invokeOperation(

                "toJTS", null);

        if (jtsGeom instanceof Polygon && jtsSplitter instanceof LineString) {

            SplitGraph graph =

                new SplitGraph((Polygon) jtsGeom, (LineString) jtsSplitter);

            final GeometryFactory gf = jtsGeom.getFactory();

            // store unsplitted holes for later addition

            List<LinearRing> unsplittedHoles = findUnsplittedHoles(graph, gf);

            List<List<SplitEdge>> allRings = findRings(graph);

            List<Polygon> resultingPolygons =

                buildSimplePolygons(allRings, unsplittedHoles, gf);

            com.vividsolutions.jts.geom.Geometry result;

            if (resultingPolygons.size() == 1) {

                result = resultingPolygons.get(0);

            } else {

                Polygon[] array =

                    resultingPolygons.toArray(new Polygon[resultingPolygons

                        .size()]);

                result = gf.createMultiPolygon(array);

            }

            GeometryManager manager = GeometryLocator.getGeometryManager();

            GeometryOperationContext params = new GeometryOperationContext();

            params.setAttribute("JTSGeometry", result);

            return (Geometry) manager.invokeOperation("fromJTS", params);

        }

        return null;

    }

    /**

     * Finds out and removes from the graph the edges that were originally holes

     * in the polygon and were not splitted by the splitting line.

     * 

     * @param graph

     * @param gf

     * @return

     */

    private List<LinearRing> findUnsplittedHoles(SplitGraph graph,

        GeometryFactory gf) {

        final List<LinearRing> unsplittedHoles = new ArrayList<LinearRing>(2);

        final List<SplitEdge> edges = new ArrayList<SplitEdge>();

        for (Iterator it = graph.getEdgeIterator(); it.hasNext();) {

            SplitEdge edge = (SplitEdge) it.next();

            edges.add(edge);

        }

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

            SplitEdge edge = (SplitEdge) it.next();

            if (edge.isHoleEdge()) {

                Coordinate[] coordinates = edge.getCoordinates();

                Coordinate start = coordinates[0];

                Coordinate end = coordinates[coordinates.length - 1];

                boolean isLinearRing = start.equals2D(end);

                if (isLinearRing) {

                    graph.remove(edge);

                    LinearRing ring = gf.createLinearRing(coordinates);

                    unsplittedHoles.add(ring);

                }

            }

        }

        return unsplittedHoles;

    }

    /**

     * Builds a list of rings from the graph's edges

     * 

     * @param graph

     * @return

     */

    private List<List<SplitEdge>> findRings(SplitGraph graph) {

        final List<List<SplitEdge>> rings = new ArrayList<List<SplitEdge>>();

        DirectedEdge startEdge;

        // build each ring starting with the first edge belonging to the

        // shell found

        while ((startEdge = findShellEdge(graph)) != null) {

            List<SplitEdge> ring = buildRing(graph, startEdge);

            rings.add(ring);

        }

        return rings;

    }

    /**

     * Returns the first edge found that belongs to the shell (not an interior

     * edge, not one of a hole boundary)

     * <p>

     * This method relies on shell edges being labeled {@link Location#EXTERIOR

     * exterior} to the left and {@link Location#INTERIOR interior} to the

     * right.

     * </p>

     * 

     * @param graph

     * @return the first shell edge found, or <code>null</code> if there are no

     *         more shell edges in <code>graph</code>

     */

    private DirectedEdge findShellEdge(SplitGraph graph) {

        Iterator it = graph.getEdgeEnds().iterator();

        DirectedEdge firstShellEdge = null;

        while (it.hasNext()) {

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

            SplitEdge edge = (SplitEdge) de.getEdge();

            if (edge.isShellEdge()) {

                firstShellEdge = de;

                break;

            }

        }

        return firstShellEdge;

    }

    private List<SplitEdge> buildRing(final SplitGraph graph,

        final DirectedEdge startEdge) {

        final List<SplitEdge> ring = new ArrayList<SplitEdge>();

        // follow this tessellation direction while possible,

        // switch to the opposite when not, and continue with

        // the same direction while possible.

        // Start travelling clockwise, as we start with a shell edge,

        // which is in clockwise order

        final int direction = CGAlgorithms.COUNTERCLOCKWISE;

        DirectedEdge currentDirectedEdge = startEdge;

        DirectedEdge nextDirectedEdge = null;

        while (nextDirectedEdge != startEdge) {

            SplitEdge edge = (SplitEdge) currentDirectedEdge.getEdge();

            if (ring.contains(edge)) {

                throw new IllegalStateException("trying to add edge twice: "

                    + edge);

            }

            ring.add(edge);

            DirectedEdge sym = currentDirectedEdge.getSym();

            SplitGraphNode endNode = (SplitGraphNode) sym.getNode();

            SplitEdgeStar nodeEdges = (SplitEdgeStar) endNode.getEdges();

            nextDirectedEdge =

                nodeEdges.findClosestEdgeInDirection(sym, direction);

            assert nextDirectedEdge != null;

            currentDirectedEdge = nextDirectedEdge;

        }

        removeUnneededEdges(graph, ring);

        return ring;

    }

    /**

     * Removes from <code>graph</code> the edges in <code>ring</code> that are

     * no more needed

     * 

     * @param graph

     * @param ring

     */

    private void removeUnneededEdges(final SplitGraph graph,

        final List<SplitEdge> ring) {

        for (SplitEdge edge : ring) {

            if (!edge.isInteriorEdge()) {

                graph.remove(edge);

            }

        }

        for (SplitEdge edge : ring) {

            if (edge.isInteriorEdge()) {

                Node node = graph.find(edge.getCoordinate());

                int degree = node.getEdges().getDegree();

                if (degree < 2) {

                    graph.remove(edge);

                }

            }

        }

    }

    private List<Polygon> buildSimplePolygons(List<List<SplitEdge>> allRings,

        List<LinearRing> unsplittedHoles, GeometryFactory gf) {

        List<Polygon> polygons = new ArrayList<Polygon>(allRings.size());

        for (List<SplitEdge> edgeList : allRings) {

            Polygon poly = buildPolygon(edgeList, gf);

            List<LinearRing> thisPolyHoles =

                new ArrayList<LinearRing>(unsplittedHoles.size());

            for (LinearRing holeRing : unsplittedHoles) {

                if (poly.covers(holeRing)) {

                    thisPolyHoles.add(holeRing);

                }

            }

            unsplittedHoles.removeAll(thisPolyHoles);

            int numHoles = thisPolyHoles.size();

            if (numHoles > 0) {

                LinearRing[] holes =

                    thisPolyHoles.toArray(new LinearRing[numHoles]);

                LinearRing shell =

                    gf.createLinearRing(poly.getExteriorRing().getCoordinates());

                poly = gf.createPolygon(shell, holes);

            }

            polygons.add(poly);

        }

        return polygons;

    }

    private Polygon buildPolygon(List<SplitEdge> edgeList, GeometryFactory gf) {

        List<Coordinate> coords = new ArrayList<Coordinate>();

        Coordinate[] lastCoordinates = null;

        for (SplitEdge edge : edgeList) {

            Coordinate[] coordinates = edge.getCoordinates();

            if (lastCoordinates != null) {

                Coordinate endPoint =

                    lastCoordinates[lastCoordinates.length - 1];

                Coordinate startPoint = coordinates[0];

                if (!endPoint.equals2D(startPoint)) {

                    coordinates = CoordinateArrays.copyDeep(coordinates);

                    CoordinateArrays.reverse(coordinates);

                }

            }

            lastCoordinates = coordinates;

            for (int i = 0; i < coordinates.length; i++) {

                Coordinate coord = coordinates[i];

                coords.add(coord);

            }

        }

        Coordinate[] shellCoords = new Coordinate[coords.size()];

        coords.toArray(shellCoords);

        shellCoords = CoordinateArrays.removeRepeatedPoints(shellCoords);

        LinearRing shell = gf.createLinearRing(shellCoords);

        Polygon poly = gf.createPolygon(shell, (LinearRing[]) null);

        return poly;

    }

}