Application: gvSIG desktop » gvSIG tools: Vector editing

	    <include>org.gvsig:org.gvsig.vectorediting.lib.prov.split</include>

       <action name="modify-split" label="modify_split" tooltip="modify_split"

        position="601003000" action-command="modify-split" icon="modify-split"

      <action name="modify-split-line" label="modify_split_line" tooltip="modify_split_line"

        position="601003050" action-command="modify-split-line" icon="modify-split-line"

        accelerator="" />

      <menu text="Layer/Modify/modify_split" name="modify-split" />

        <selectable-tool name="modify-split" />

		<dependency>

			<groupId>org.gvsig</groupId>

			<artifactId>

				org.gvsig.vectorediting.lib.prov.split

			</artifactId>

		</dependency>

			<dependency>

				<groupId>org.gvsig</groupId>

				<artifactId>

					org.gvsig.vectorediting.lib.prov.split

				</artifactId>

				<version>1.0.1-SNAPSHOT</version>

			</dependency>

		<module>org.gvsig.vectorediting.lib.prov.split</module>

org.gvsig.vectorediting.lib.prov.split.SplitEditingLibrary

/**

 * 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;

import org.gvsig.fmap.geom.Geometry;

import org.gvsig.fmap.geom.exception.CreateGeometryException;

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

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

/**

 * @author llmarques

 *

 */

public interface SplitOperation {

    /**

     * Splits the geometry by a other splitter geometry. If splitter does not

     * intersect geometry return original geometry.

     * 

     * @param geometryToBeSplitted

     *            to be splitted

     * @param splitter

     *            the geometry that splits other geometries

     * @return If splitter does not intersect return original geometry, else

     *         return splitted geometry.

     */

    public Geometry split(Geometry geometryToBeSplitted, Geometry splitter)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException, CreateGeometryException;

}

/**

 * 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;

import java.util.HashMap;

import java.util.Map;

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.Geometry.TYPES;

import org.gvsig.fmap.geom.exception.CreateGeometryException;

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

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

import org.gvsig.fmap.geom.primitive.Curve;

import org.gvsig.fmap.geom.primitive.Point;

import org.gvsig.fmap.geom.primitive.Primitive;

/**

 * @author llmarques

 *

 */

public class SplitOperationUtils {

    private static Map<Integer, SplitOperation> operations =

        new HashMap<Integer, SplitOperation>();

    private SplitOperationUtils() {

    }

    public static void register(SplitOperation operation, int geometryType) {

        operations.put(geometryType, operation);

    }

    public static SplitOperation getOperation(Primitive geom) {

        Integer type = geom.getGeometryType().getType();

        SplitOperation operation = operations.get(type);

        return operation;

    }

    // FIXME: Deletes method when geometry manager has this utility method.

    public static Point getMidPoint(Point a, Point b, int subtype)

        throws CreateGeometryException {

        double x = (a.getX() + b.getX()) / 2;

        double y = (a.getY() + b.getY()) / 2;

        return createPoint(x, y, subtype);

    }

    // FIXME: Deletes method when geometry manager has this utility method.

    public static Point createPoint(double x, double y, int subtype)

        throws CreateGeometryException {

        Point point = null;

        point =

            (Point) GeometryLocator.getGeometryManager().create(TYPES.POINT,

                subtype);

        point.setX(x);

        point.setY(y);

        return point;

    }

    // FIXME: Deletes method when geometry manager has this utility methods.

    public static Point[] getPerpendicular(Double m, Double b, Point perp,

        int subtype) throws CreateGeometryException {

        if (m == Double.POSITIVE_INFINITY) {

            Point[] res = new Point[2];

            res[0] = createPoint(0, perp.getY(), subtype);

            res[1] = createPoint(1, perp.getY(), subtype);

            return res;

        } else if (m == Double.NEGATIVE_INFINITY) {

            Point[] res = new Point[2];

            res[0] = createPoint(1, perp.getY(), subtype);

            res[1] = createPoint(0, perp.getY(), subtype);

            return res;

        } else {

            // Pendiente de la recta perpendicular

            Double m1 = -1 / m;

            // b de la funcion de la recta perpendicular

            Double b1 = perp.getY() - (m1 * perp.getX());

            // Obtenemos un par de puntos

            Point[] res = new Point[2];

            if (Double.isInfinite(m1)) {

                res[0] = createPoint(perp.getX(), 0.0, subtype);

                res[1] = createPoint(perp.getX(), perp.getY(), subtype);

            } else {

                res[0] = createPoint(0, 0.0 + b1, subtype);

                res[1] =

                    createPoint(perp.getX(), (m1 * perp.getX()) + b1, subtype);

            }

            return res;

        }

    }

    // FIXME: Deletes method when geometry manager has this utility method.

    public static Double[] getLineParams(Point point, Point nextPoint) {

        Double[] lineParams = new Double[2];

        double denom = nextPoint.getX() - point.getX();

        if (denom != 0) {

            lineParams[0] = (nextPoint.getY() - point.getY()) / denom;

            lineParams[1] = point.getY() - (lineParams[0] * point.getX());

        } else {

            if (nextPoint.getY() >= point.getY()) {

                lineParams[0] = Double.POSITIVE_INFINITY;

                lineParams[1] = Double.NEGATIVE_INFINITY;

                if (point.getX() == 0) {

                    lineParams[1] = 0.0;

                }

            } else {

                lineParams[0] = Double.NEGATIVE_INFINITY;

                lineParams[1] = Double.POSITIVE_INFINITY;

                if (point.getX() == 0) {

                    lineParams[1] = 0.0;

                }

            }

        }

        return lineParams;

    }

    // FIXME: Deletes method when geometry manager has this utility method.

    public static Point getIntersection(Point[] lineA, Point[] lineB,

        int subtype) throws CreateGeometryException {

        Point p1 = lineA[0];

        Point p2 = lineA[1];

        Point p3 = lineB[0];

        Point p4 = lineB[1];

        double m1 = Double.POSITIVE_INFINITY;

        if ((p2.getX() - p1.getX()) != 0) {

            m1 = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());

        }

        double m2 = Double.POSITIVE_INFINITY;

        if ((p4.getX() - p3.getX()) != 0) {

            m2 = (p4.getY() - p3.getY()) / (p4.getX() - p3.getX());

        }

        if ((m1 == Double.POSITIVE_INFINITY)

            && (m2 == Double.POSITIVE_INFINITY)) {

            return null;

        }

        double b1 = p2.getY() - (m1 * p2.getX());

        double b2 = p4.getY() - (m2 * p4.getX());

        if ((m1 != Double.POSITIVE_INFINITY)

            && (m2 != Double.POSITIVE_INFINITY)) {

            if (m1 == m2) {

                return null;

            }

            double x = (b2 - b1) / (m1 - m2);

            return createPoint(x, (m1 * x) + b1, subtype);

        } else if (m1 == Double.POSITIVE_INFINITY) {

            double x = p1.getX();

            return createPoint(x, (m2 * x) + b2, subtype);

        } else if (m2 == Double.POSITIVE_INFINITY) {

            double x = p3.getX();

            return createPoint(x, (m1 * x) + b1, subtype);

        }

        return null;

    }

    // FIXME: Deletes method when geometry manager has this utility method.

    public static double getAngle(Point start, Point end)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException {

        double angle =

            Math.acos((end.getX() - start.getX()) / start.distance(end));

        if (start.getY() > end.getY()) {

            angle = -angle;

        }

        if (angle < 0) {

            angle += (2 * Math.PI);

        }

        return angle;

    }

    public static Point getCenterOfCurve(Point p1, Point p2, Point p3, Point p4)

        throws CreateGeometryException {

        if (!p1.equals(p2) && !p3.equals(p4)) {

            int subtype = p1.getGeometryType().getSubType();

            Point midPointChord1 =

                SplitOperationUtils.getMidPoint(p1, p2, subtype);

            Point midPointChord2 =

                SplitOperationUtils.getMidPoint(p3, p4, subtype);

            Double[] bisector1Params =

                SplitOperationUtils.getLineParams(p1, p2);

            Double[] bisector2Params =

                SplitOperationUtils.getLineParams(p3, p4);

            Point[] bisector1 =

                SplitOperationUtils.getPerpendicular(bisector1Params[0],

                    bisector1Params[1], midPointChord1, subtype);

            Point[] bisector2 =

                SplitOperationUtils.getPerpendicular(bisector2Params[0],

                    bisector2Params[1], midPointChord2, subtype);

            return getIntersection(bisector1, bisector2, subtype);

        }

        return null;

    }

    public static Point getCenterOfCurve(Point p1, Point p2, Point p3)

        throws CreateGeometryException {

        if (!p1.equals(p2) && !p2.equals(p3)) {

            int subtype = p1.getGeometryType().getSubType();

            Double[] lineAParams = SplitOperationUtils.getLineParams(p1, p2);

            Double[] lineBParams = SplitOperationUtils.getLineParams(p2, p3);

            double mA = lineAParams[0]; // slope of A line

            double mB = lineBParams[0]; // slope of B line

            if (mB - mA != 0) {

                double x =

                    (mA * mB * (p1.getY() - p3.getY()) + mB

                        * (p1.getX() + p2.getX()) - mA

                        * (p2.getX() + p3.getX()))

                        / (2 * (mB - mA));

                Point midPointA =

                    SplitOperationUtils.getMidPoint(p1, p2, subtype);

                Point[] bisectorA =

                    SplitOperationUtils.getPerpendicular(lineAParams[0],

                        lineAParams[1], midPointA, subtype);

                Double[] bisectorAParams =

                    SplitOperationUtils.getLineParams(bisectorA[0],

                        bisectorA[1]);

                double mBisector = bisectorAParams[0]; // slope of bisector

                double yBisector = bisectorAParams[1]; // y-intercept of

                                                       // bisector

                double y = x * mBisector + yBisector;

                return createPoint(x, y, subtype);

            }

        }

        return null;

    }

    /**

     * Method use to know what segment intersect with projected point. Due to

     * accuracy of doubles it is necessary to create a buffer of line to know if

     * it intersects.

     * 

     * @param curve

     *            segment of line

     * @param projectedPoint

     *            of line

     * @return true if segment intersects with projected point, else false.

     */

    public static boolean intersects(Curve curve, Point projectedPoint)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException {

        double tolerance = 2;

        return curve.buffer(tolerance).intersects(projectedPoint);

    }

}

/**

 * 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;

import org.gvsig.fmap.geom.Geometry;

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.aggregate.MultiCurve;

import org.gvsig.fmap.geom.aggregate.MultiPoint;

import org.gvsig.fmap.geom.exception.CreateGeometryException;

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

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

import org.gvsig.fmap.geom.primitive.Curve;

import org.gvsig.fmap.geom.primitive.Point;

/**

 * @author llmarques

 *

 */

public class CurveSplitOperation implements SplitOperation {

    /*

     * Strategy:

     * 

     * 1. Get intersection points.

     * 2. Get difference between geometry and splitter. If splitter does not

     * touch geometry return original geometry.

     * 3. If any intersection points are not equal to first or last vertex of

     * original geometry, join last and first curve splitted. It's necessary do

     * it because the difference between geometry and splitter returns a

     * multicurve that its first curve starts at first vertex of ORGINAL and

     * ends at first intersection point and its last curve starts at

     * last intersection point and ends at last vertex of ORIGINAL geometry, so

     * we have to join them. If any intersecion points are equal to first or

     * last vertex do nothing.

     */

    public Geometry split(Geometry geometryToBeSplitted, Geometry splitter)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException, CreateGeometryException {

        Curve curveToBeSplitted = (Curve) geometryToBeSplitted;

        Geometry intersection = geometryToBeSplitted.intersection(splitter);

        MultiCurve multicurveSplitted = null;

        if (intersection instanceof MultiPoint) {

            MultiPoint intersectionMultiPoint = (MultiPoint) intersection;

            Point firstVertex = intersectionMultiPoint.getPointAt(0);

            Point lastVertex =

                intersectionMultiPoint.getPointAt(intersectionMultiPoint

                    .getPrimitivesNumber() - 1);

            MultiCurve difference =

                (MultiCurve) geometryToBeSplitted.difference(splitter);

            if (difference == null) {

                return geometryToBeSplitted;

            }

            if (!firstVertex.equals(curveToBeSplitted.getVertex(0))

                && !lastVertex.equals(curveToBeSplitted.getVertex(0))) {

                Curve firstCurve = difference.getCurveAt(0);

                Curve lastCurve =

                    difference.getCurveAt(difference.getPrimitivesNumber() - 1);

                Curve union =

                    GeometryLocator.getGeometryManager().createLine(

                        geometryToBeSplitted.getGeometryType().getSubType());

                for (int i = 0; i < lastCurve.getNumVertices(); i++) {

                    union.addVertex(lastCurve.getVertex(i));

                }

                for (int i = 0; i < firstCurve.getNumVertices(); i++) {

                    union.addVertex(firstCurve.getVertex(i));

                }

                multicurveSplitted =

                    GeometryLocator.getGeometryManager().createMultiCurve(

                        geometryToBeSplitted.getGeometryType().getSubType());

                multicurveSplitted.addCurve(union);

                for (int i = 1; i < difference.getPrimitivesNumber() - 1; i++) {

                    multicurveSplitted.addCurve(difference.getCurveAt(i));

                }

            } else {

                multicurveSplitted = difference;

            }

        }

        return multicurveSplitted;

    }

}

/**

 * 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;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

import org.gvsig.fmap.geom.Geometry;

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.GeometryManager;

import org.gvsig.fmap.geom.aggregate.MultiCurve;

import org.gvsig.fmap.geom.aggregate.MultiPoint;

import org.gvsig.fmap.geom.exception.CreateGeometryException;

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

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

import org.gvsig.fmap.geom.primitive.Arc;

import org.gvsig.fmap.geom.primitive.Point;

import org.gvsig.tools.exception.BaseException;

/**

 * @author llmarques

 *

 */

public class ArcSplitOperation implements SplitOperation {

    private static Logger logger = LoggerFactory

        .getLogger(ArcSplitOperation.class);

    /*

     * Strategy:

     * 

     * 1. Get intersection points.

     * 2. Get center and radius

     * 3. Order intersections points by angle

     * 4. Iterate over ordered intersection points and create splitted arcs.

     * Stop iteration when all intersections points have been iterated.

     */

    public Geometry split(Geometry geometryToBeSplitted, Geometry splitter)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException, CreateGeometryException {

        int subtype = geometryToBeSplitted.getGeometryType().getSubType();

        GeometryManager geoManager = GeometryLocator.getGeometryManager();

        Arc arcToBeSplitted = (Arc) geometryToBeSplitted;

        MultiPoint intersections =

            (MultiPoint) arcToBeSplitted.intersection(splitter);

        if (intersections == null) {

            return geometryToBeSplitted;

        }

        // Arc#getCenterPoint can return null if two points of arc are the same

        Point tmpCenter = arcToBeSplitted.getCenterPoint();

        if (tmpCenter == null) {

            // If center is null, we use this "trick". Get center of arc

            // envelope.

            tmpCenter =

                SplitOperationUtils.createPoint(arcToBeSplitted.getEnvelope()

                    .getCenter(0), arcToBeSplitted.getEnvelope().getCenter(1),

                    subtype);

        }

        final Point center = tmpCenter;

        double radius = center.distance(arcToBeSplitted.getEndPoint());

        // Order intersection points by angle to create arcs correctly

        List<Point> orderedIntersectionPoints = new ArrayList<Point>();

        for (int i = 0; i < intersections.getPrimitivesNumber(); i++) {

            orderedIntersectionPoints.add(intersections.getPointAt(i));

        }

        // Sort by angle

        Collections.sort(orderedIntersectionPoints, new Comparator<Point>() {

            public int compare(Point p1, Point p2) {

                double angle1 = 0;

                double angle2 = 0;

                try {

                    angle1 = SplitOperationUtils.getAngle(center, p1);

                    angle2 = SplitOperationUtils.getAngle(center, p2);

                } catch (BaseException e) {

                    logger.warn("Problems getting angle between center and"

                        + " one intersection point");

                    return 0;

                }

                return Double.compare(angle1, angle2);

            }

        });

        MultiCurve splittedArcs = geoManager.createMultiCurve(subtype);

        for (int i = 0; i < orderedIntersectionPoints.size(); i++) {

            Point intersecctionPoint = orderedIntersectionPoints.get(i);

            Point nextIntersecctionPoint;

            if (i + 1 >= orderedIntersectionPoints.size()) {

                nextIntersecctionPoint = orderedIntersectionPoints.get(0);

            } else {

                nextIntersecctionPoint = orderedIntersectionPoints.get(i + 1);

            }

            double angle1 =

                SplitOperationUtils.getAngle(center, intersecctionPoint);

            double angle2 =

                SplitOperationUtils.getAngle(center, nextIntersecctionPoint);

            Arc arc = (Arc) geoManager.create(Geometry.TYPES.ARC, subtype);

            arc.setPointsStartEnd(center, radius, angle1, angle2);

            splittedArcs.addCurve(arc);

        }

        return splittedArcs;

    }

}

/**

 * gvSIG. Desktop Geographic Information System.

 *

 * Copyright (C) 2007-2013 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 3

 * 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.

 */

/* Spatial Operations & Editing Tools for uDig

 * 

 * Axios Engineering under a funding contract with: 

 *      Diputación Foral de Gipuzkoa, Ordenación Territorial 

 *

 *      http://b5m.gipuzkoa.net

 *      http://www.axios.es 

 *

 * (C) 2006, Diputación Foral de Gipuzkoa, Ordenación Territorial (DFG-OT). 

 * DFG-OT agrees to licence under Lesser General Public License (LGPL).

 * 

 * You can redistribute it and/or modify it under the terms of the 

 * GNU Lesser General Public License as published by the Free Software 

 * Foundation; version 2.1 of the License.

 *

 * This library 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

 * Lesser General Public License for more details.

 */

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

import com.vividsolutions.jts.geom.Coordinate;

import com.vividsolutions.jts.geomgraph.DirectedEdge;

import com.vividsolutions.jts.geomgraph.EdgeEnd;

import com.vividsolutions.jts.geomgraph.Node;

/**

 * Custom node type. Does nothing special by now but to force the use of {@link SplitEdgeStar}

 * instances as the node's list of incident edges and allow to remove edges from its list of

 * incident edges.

 * 

 * @author Gabriel Roldán, Axios Engineering

 * @author Mauricio Pazos, Axios Engineering

 * @since 1.1.0

 */

class SplitGraphNode extends Node {

    public SplitGraphNode( Coordinate coord, SplitEdgeStar incidentEdges ) {

        super(coord, incidentEdges);

    }

    public void add( DirectedEdge edge ) {

        super.add(edge);

    }

    @Override

    public void add( EdgeEnd edge ) {

        add((DirectedEdge) edge);

    }

    /**

     * Removes the given <code>edge</code> from this node's {@link #getEdges() edge list}.

     * 

     * @param edge

     */

    public void remove( DirectedEdge edge ) {

        SplitEdgeStar edges = (SplitEdgeStar) getEdges();

        edges.remove(edge);

    }

    public String toString() {

        StringBuffer sb = new StringBuffer("Node[");

        sb.append(coord.x).append(":").append(coord.y);

        sb.append(", ").append(label);

        sb.append(", ").append(getEdges());

        sb.append("]");

        return sb.toString();

    }

}

/**

 * 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;

    }

}

/**

 * gvSIG. Desktop Geographic Information System.

 *

 * Copyright (C) 2007-2013 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 3

 * 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.

 */

/* Spatial Operations & Editing Tools for uDig

 * 

 * Axios Engineering under a funding contract with: 

 *      Diputación Foral de Gipuzkoa, Ordenación Territorial 

 *

 *      http://b5m.gipuzkoa.net

 *      http://www.axios.es 

 *

 * (C) 2006, Diputación Foral de Gipuzkoa, Ordenación Territorial (DFG-OT). 

 * DFG-OT agrees to licence under Lesser General Public License (LGPL).

 * 

 * You can redistribute it and/or modify it under the terms of the 

 * GNU Lesser General Public License as published by the Free Software 

 * Foundation; version 2.1 of the License.

 *

 * This library 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

 * Lesser General Public License for more details.

 */

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.Angle;

import com.vividsolutions.jts.algorithm.CGAlgorithms;

import com.vividsolutions.jts.geom.Coordinate;

import com.vividsolutions.jts.geomgraph.DirectedEdge;

import com.vividsolutions.jts.geomgraph.DirectedEdgeStar;

import com.vividsolutions.jts.geomgraph.EdgeEnd;

import com.vividsolutions.jts.util.Assert;

/**

 * A {@link DirectedEdgeStar} for the {@link SplitGraphNode nodes} in a {@link SplitGraph}

 * 

 * @author Gabriel Roldán, Axios Engineering

 * @author Mauricio Pazos, Axios Engineering

 * @since 1.1.0

 */

class SplitEdgeStar extends DirectedEdgeStar {

    /**

     * Adds a DirectedEdge to the list of incident edges on this star

     * 

     * @param de non null directed edge to insert on this node star

     */

    public void insert( DirectedEdge de ) {

        if (de == null) {

            throw new NullPointerException();

        }

        insertEdgeEnd(de, de);

    }

    /**

     * Overrides {@link DirectedEdgeStar#insert(EdgeEnd)} just to delegate to

     * {@link #insert(DirectedEdge)} forcing the argument type

     */

    @Override

    public void insert( EdgeEnd ee ) {

        insert((DirectedEdge) ee);

    }

    /**

     * Removes the given edge from this edge star

     * 

     * @param edge

     * @throws IllegalArgumentException if <code>edge</code> is not one of this star's edges

     */

    public void remove( DirectedEdge edge ) {

        if (edge == null) {

            throw new NullPointerException("edge");

        }

        int degree = getDegree();

        Object removed = edgeMap.remove(edge);

        int afterDegree = getDegree();

        Assert.isTrue(afterDegree == degree - 1);

        if (edge != removed) {

            throw new IllegalArgumentException(

                                               "Tried to remove an edge not registered in this edge star: "

                                                       + edge);

        }

        edgeList = null; // edge list has changed - clear the cache

    }

    /**

     * Returns the list of Directed edges whose direction is outgoing from this star's node. That

     * is, for all the DirectedEdges in the star, if the edge's start point is coincident whith the

     * edge star node, returns the same DirectedNode, otherwise returns the edge's

     * {@link DirectedEdge#getSym() symmetric edge}.

     * 

     * @return

     */

    private List getOutgoingEdges() {

        final Coordinate nodeCoord = getCoordinate();

        final List edges = getEdges();

        final List outgoingEdges = new ArrayList(edges.size());

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

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

            if (!nodeCoord.equals2D(edge.getCoordinate())) {

                edge = edge.getSym();

            }

            assert nodeCoord.equals2D(edge.getCoordinate());

            outgoingEdges.add(edge);

        }

        return outgoingEdges;

    }

    /**

     * Finds the first edge to the passed in in the <code>searchDrirection</code> direction.

     * 

     * @param searchDirection one of {@link CGAlgorithms#CLOCKWISE},

     *        {@link CGAlgorithms#COUNTERCLOCKWISE}

     * @return the edge forming the acutest angle with <code>edge</code> in the

     *         <code>prefferredDirection</code> or <code>null</code> if there are no edges in

     *         the prefferred direction.

     */

    public DirectedEdge findClosestEdgeInDirection( DirectedEdge edge, final int searchDirection ) {

        if (edge == null) {

            throw new NullPointerException("edge");

        }

        if (CGAlgorithms.CLOCKWISE != searchDirection

                && CGAlgorithms.COUNTERCLOCKWISE != searchDirection) {

            throw new IllegalArgumentException("Allowed values for for searchDirection "

                    + "are CGAlgorithms.CLOCKWISE and CGAlgorithms.COUNTERCLOCKWISE: "

                    + searchDirection);

        }

        // ensure we're using the node's outgoing edge

        if (super.findIndex(edge) == -1) {

            edge = edge.getSym();

            if (super.findIndex(edge) == -1) {

                throw new IllegalArgumentException("Edge does not belongs to this edgestar");

            }

        }

        final int degree = getDegree();

        if (degree < 2) {

            throw new IllegalStateException("there must be at least two edges in the edge star");

        }

        final Coordinate nodeCoord = getCoordinate();

        assert nodeCoord.equals2D(edge.getCoordinate());

        double acutestAngle = Double.MAX_VALUE;

        DirectedEdge acutest = null;

        DirectedEdge adjacentEdge = null;

        final Coordinate tip1 = edge.getDirectedCoordinate();

        final Coordinate tail = nodeCoord;

        // ensure we're using outgoing edges

        final List outgoingEdges = getOutgoingEdges();

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

            adjacentEdge = (DirectedEdge) it.next();

            if (adjacentEdge == edge) {

                continue;

            }

            Coordinate tip2 = adjacentEdge.getDirectedCoordinate();

            double angle = computeAngleInDirection(tip1, tail, tip2, searchDirection);

            if (angle < acutestAngle) {

                acutestAngle = angle;

                acutest = adjacentEdge;

            }

        }

        return acutest;

    }

    /**

     * Computes the angle comprised between the vector <code>tail:tip1</code> looking in the

     * specified <code>direction</code> to the vector <code>tail:tip2</code>

     * 

     * @param tip1

     * @param tail

     * @param tip2

     * @param direction one of {@link CGAlgorithms#CLOCKWISE},

     *        {@link CGAlgorithms#COUNTERCLOCKWISE}

     * @return the angle in radians defined by the vectors tail-tip1:tail-tip2 calculated in the

     *         specified <code>direction</code> from tail-tip1

     */

    public double computeAngleInDirection( Coordinate tip1, Coordinate tail, Coordinate tip2,

                                           int direction ) {

        final int orientation = CGAlgorithms.computeOrientation(tail, tip1, tip2);

        // minimal angle (non oriented)

        double angle = Angle.angleBetween(tip1, tail, tip2);

        if (orientation != direction) {

            angle = Angle.PI_TIMES_2 - angle;

        }

        return angle;

    }

    public String toString() {

        StringBuffer sb = new StringBuffer("SplitEdgeStar[degree: ");

        sb.append(getDegree()).append(", edges: ");

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

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

            sb.append("DirectedEdge[");

            sb.append(de.getEdge()).append(" ");

            sb.append("]");

        }

        sb.append("]");

        return sb.toString();

    }

}

/**

 * gvSIG. Desktop Geographic Information System.

 *

 * Copyright (C) 2007-2013 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 3

 * 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.

 */

/* Spatial Operations & Editing Tools for uDig

 * 

 * Axios Engineering under a funding contract with: 

 *      Diputación Foral de Gipuzkoa, Ordenación Territorial 

 *

 *      http://b5m.gipuzkoa.net

 *      http://www.axios.es 

 *

 * (C) 2006, Diputación Foral de Gipuzkoa, Ordenación Territorial (DFG-OT). 

 * DFG-OT agrees to licence under Lesser General Public License (LGPL).

 * 

 * You can redistribute it and/or modify it under the terms of the 

 * GNU Lesser General Public License as published by the Free Software 

 * Foundation; version 2.1 of the License.

 *

 * This library 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

 * Lesser General Public License for more details.

 */

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

import com.vividsolutions.jts.geom.Coordinate;

import com.vividsolutions.jts.geomgraph.Node;

import com.vividsolutions.jts.geomgraph.NodeFactory;

/**

 * Custom node factory to create {@link SplitGraphNode}s initialized with an empty

 * {@link SplitEdgeStar}

 * 

 * @author Gabriel Roldán, Axios Engineering

 * @author Mauricio Pazos, Axios Engineering

 * @since 1.1.0

 * @see SplitGraphNode

 */

class SplitGraphNodeFactory extends NodeFactory {

    public Node createNode( Coordinate coord ) {

        return new SplitGraphNode(coord, new SplitEdgeStar());

    }