Application: gvSIG desktop » gvSIG Linear Reference System

/* gvSIG. Desktop Geographic Information System.

 *

 * Copyright ? 2007-2015 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.lrs.lib.impl;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.List;

import java.util.Map.Entry;

import java.util.SortedMap;

import java.util.TreeMap;

import org.apache.commons.lang3.mutable.MutableInt;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

import org.gvsig.fmap.dal.feature.EditableFeature;

import org.gvsig.fmap.dal.feature.Feature;

import org.gvsig.fmap.dal.feature.FeatureAttributeDescriptor;

import org.gvsig.fmap.dal.feature.FeatureSet;

import org.gvsig.fmap.dal.feature.FeatureStore;

import org.gvsig.fmap.dal.feature.NewFeatureStoreParameters;

import org.gvsig.fmap.geom.Geometry;

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

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.GeometryManager;

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

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

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

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

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

import org.gvsig.lrs.lib.api.LrsAlgorithm;

import org.gvsig.lrs.lib.api.LrsAlgorithmParams;

import org.gvsig.lrs.lib.api.LrsCoordinatesPriority;

import org.gvsig.lrs.lib.api.LrsCreateRouteAlgorithmParams;

import org.gvsig.lrs.lib.api.LrsSourceOfMeasures;

import org.gvsig.lrs.lib.api.exceptions.LrsCreateRouteException;

import org.gvsig.lrs.lib.api.exceptions.LrsException;

import org.gvsig.tools.ToolsLocator;

import org.gvsig.tools.dataTypes.DataType;

import org.gvsig.tools.exception.BaseException;

import org.gvsig.tools.i18n.I18nManager;

import org.gvsig.tools.locator.LocatorException;

import org.gvsig.tools.service.Manager;

import org.gvsig.tools.task.SimpleTaskStatus;

import org.gvsig.tools.visitor.VisitCanceledException;

import org.gvsig.tools.visitor.Visitor;

/**

 * @author fdiaz

 *

 */

public class LrsCreateRouteAlgorithm implements LrsAlgorithm {

    private static final Logger logger = LoggerFactory.getLogger(LrsCreateRouteAlgorithm.class);

    private LrsCreateRouteAlgorithmParams parameters;

    /**

     *

     */

    public LrsCreateRouteAlgorithm(LrsCreateRouteAlgorithmParams parameters) {

        this.parameters = parameters;

    }

    /*

     * (non-Javadoc)

     *

     * @see org.gvsig.tools.service.Service#getManager()

     */

    public Manager getManager() {

        return null;

    }

    /*

     * (non-Javadoc)

     *

     * @see org.gvsig.lrs.lib.api.LrsAlgorithm#getParams()

     */

    public LrsAlgorithmParams getParams() {

        return this.parameters;

    }

    /*

     * (non-Javadoc)

     *

     * @see org.gvsig.lrs.lib.api.LrsAlgorithm#execute(org.gvsig.tools.task.

     * SimpleTaskStatus)

     */

    public void execute(SimpleTaskStatus taskStatus) throws LrsException {

        NewFeatureStoreParameters newFeatureStoreParameters = parameters.getNewFeatureStoreParameters();

        FeatureStore sourceFeatureStore = parameters.getSourceFeatureStore();

        FeatureAttributeDescriptor idRouteField = parameters.getIdRouteField();

        FeatureAttributeDescriptor fromMeasureField = parameters.getFromMeasureField();

        FeatureAttributeDescriptor toMeasureField = parameters.getToMeasureField();

        logger.info(parameters.toString());

        taskStatus.setTitle(parameters.getName());

        I18nManager i18nManager = ToolsLocator.getI18nManager();

        taskStatus.message(i18nManager.getTranslation("grouping_features"));

        try {

            final String routeFieldName = idRouteField.getName();

            final String fromFieldName;

            final DataType fromDataType;

            final DataType toDataType;

            if (fromMeasureField != null) {

                fromFieldName = fromMeasureField.getName();

                fromDataType = fromMeasureField.getDataType();

            } else {

                fromFieldName = null;

                fromDataType = null;

            }

            final String toFieldName;

            if (toMeasureField != null) {

                toFieldName = toMeasureField.getName();

                toDataType = toMeasureField.getDataType();

            } else {

                toFieldName = null;

                toDataType = null;

            }

            FeatureStore newFeatureStore =

                LrsAlgorithmUtils.createNewDataStore(newFeatureStoreParameters, idRouteField);

            FeatureSet sourceFeatures;

            if (sourceFeatureStore.getFeatureSelection().getSize() > 0) {

                sourceFeatures = sourceFeatureStore.getFeatureSelection();

            } else {

                sourceFeatures = sourceFeatureStore.getFeatureSet();

            }

            final SortedMap<String, List<MSegment>> featuresMap = new TreeMap<String, List<MSegment>>();

            final MutableInt contId = new MutableInt(0);

            sourceFeatures.accept(new Visitor() {

                public void visit(Object obj) throws VisitCanceledException, BaseException {

                    Feature feature = (Feature) obj;

                    String routeName = (String) feature.get(routeFieldName);

                    Object objFrom = null;

                    Object objTo = null;

                    if (fromFieldName != null) {

                        objFrom = feature.get(fromFieldName);

                    }

                    if (toFieldName != null) {

                        objTo = feature.get(toFieldName);

                    }

                    if (!featuresMap.containsKey(routeName)) {

                        featuresMap.put(routeName, new ArrayList<MSegment>());

                    }

                    List<MSegment> mList = featuresMap.get(routeName);

                    MSegment mSegment = new MSegment();

                    mSegment.geometry = feature.getDefaultGeometry().cloneGeometry();

                    mSegment.fromValue = LrsAlgorithmUtils.getAsDouble(objFrom, fromDataType);

                    mSegment.toValue = LrsAlgorithmUtils.getAsDouble(objTo, toDataType);

                    mSegment.id = contId.getValue();

                    contId.increment();

                    mList.add(mSegment);

                    featuresMap.put(routeName, mList);

                }

            });

            taskStatus.setRangeOfValues(0, featuresMap.size());

            int taskCount = 0;

            newFeatureStore.edit(FeatureStore.MODE_FULLEDIT);

            for (Entry<String, List<MSegment>> entry : featuresMap.entrySet()) {

                String routeName = entry.getKey();

                List<MSegment> mList = entry.getValue();

                EditableFeature newFeature = newFeatureStore.createNewFeature(true);

                newFeature.set(routeFieldName, routeName);

                Geometry route = createGeometryRoute(mList);

                newFeature.setDefaultGeometry(route);

                newFeatureStore.update(newFeature);

                taskCount++;

                taskStatus.setCurValue(taskCount);

            }

            newFeatureStore.finishEditing();

        } catch (Exception e1) {

            taskStatus.abort();

            throw new LrsCreateRouteException("Error creating routes", e1);

        }

        taskStatus.terminate();

    }

    private Geometry createGeometryRoute(List<MSegment> mList) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException, CreateEnvelopeException {

        LrsSourceOfMeasures sourceOfMeasures = parameters.getSourceOfMeasures();

        Geometry geometryResult = null;

        simplifyMultilines(mList);

        switch (sourceOfMeasures) {

        case ONE_FIELD:

            geometryResult = calculateGeometryByOneField(mList);

            break;

        case TWO_FIELDS:

            geometryResult = calculateGeometryByTwoField(mList);

            break;

        case LENGTH:

        default:

            geometryResult = calculateGeometryByLength(mList);

            break;

        }

        geometryResult = applyOffsetAndFactor(geometryResult);

        return geometryResult;

    }

    private Geometry calculateGeometryByLength(List<MSegment> mList) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException, CreateEnvelopeException {

        boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

        for (MSegment mSegment : mList) {

            mSegment.fromValue = LrsAlgorithmUtils.getGeometryLength(mSegment.geometry, ignoreSpatialGaps);

        }

        return calculateGeometryByOneField(mList);

    }

    private Geometry calculateGeometryByOneField(List<MSegment> mList) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException, CreateEnvelopeException {

        boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

        GeometryManager gmanager = GeometryLocator.getGeometryManager();

        try {

            mList = sortMList(mList);

        } catch (Exception e) {

            logger.warn("Geometries couldn't be ordered");

        }

        MultiLine auxMultiLine = (MultiLine) gmanager.create(Geometry.TYPES.MULTILINE, Geometry.SUBTYPES.GEOM2DM);

        Point previousPoint = null;

        double previousM = 0.0;

        for (MSegment mSegment : mList) {

            Geometry geom = mSegment.geometry;

            Double geometryLength = mSegment.getLength(ignoreSpatialGaps);

            if (geom instanceof Line) {

                Line line = (Line) geom;

                Line auxLine = (Line) gmanager.create(Geometry.TYPES.LINE, Geometry.SUBTYPES.GEOM2DM);

                double distance = 0.0;

                double firstM = previousM;

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

                    Point vertex = line.getVertex(i);

                    Point point = (Point) gmanager.create(Geometry.TYPES.POINT, Geometry.SUBTYPES.GEOM2DM);

                    point.setX(vertex.getX());

                    point.setY(vertex.getY());

                    if (i == 0 && previousPoint != null) {

                        boolean gap = false;

                        if (areInSame2DLocation(previousPoint, vertex)) {

                            // Buscamos si ha sido una bifurcaci?n

                            Point fork = getPossibleFork(auxMultiLine, vertex);

                            if(fork!=null){

                                previousPoint = fork;

                            }

                            // OJO, aqu? previousPoint pasa a ser 2DM

                        } else {

                            // En caso de salto, calculamos el previousPoint

                            // // y si no, buscamos el v?rtice m?s cercano

                            previousPoint = getClosestVertex(auxMultiLine, vertex);

                            // OJO, aqu? previousPoint pasa a ser 2DM

                            gap = true;

                        }

                        previousM = previousPoint.getCoordinateAt(previousPoint.getDimension() - 1);

                        if (i == 0) {

                            firstM = previousM;

                        }

                        if (gap && !ignoreSpatialGaps) {

                            Point previousVertex = getPreviousVertexToPoint(auxMultiLine, previousPoint);

                            previousVertex.getCoordinateAt(previousVertex.getDimension() - 1);

                            previousM =

                                strightLineThroughTwoPointsEquation(0, previousVertex.distance(previousPoint),

                                    previousVertex.getCoordinateAt(previousVertex.getDimension() - 1), previousM,

                                    previousVertex.distance(previousPoint) + previousPoint.distance(point));

                            firstM = previousM;

                        }

                    }

                    if (i != 0) {

                        distance += previousPoint.distance(vertex);

                    }

                    double m =

                        strightLineThroughTwoPointsEquation(0, geometryLength, firstM, firstM + mSegment.fromValue,

                            distance);

                    point.setCoordinateAt(point.getDimension() - 1, m);

                    auxLine.addVertex(point);

                    previousM = m;

                    previousPoint = vertex;

                }

                auxMultiLine.addPrimitive(auxLine);

            } else if (geom instanceof MultiLine) {

                MultiLine multiline = (MultiLine) geom;

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

                    Line line = (Line) multiline.getPrimitiveAt(i);

                    Line auxLine = (Line) gmanager.create(Geometry.TYPES.LINE, Geometry.SUBTYPES.GEOM2DM);

                    double distance = 0.0;

                    double firstM = previousM;

                    for (int j = 0; j < line.getNumVertices(); j++) {

                        Point vertex = line.getVertex(j);

                        Point point = (Point) gmanager.create(Geometry.TYPES.POINT, Geometry.SUBTYPES.GEOM2DM);

                        point.setX(vertex.getX());

                        point.setY(vertex.getY());

                        if (j == 0 && previousPoint != null) {

                            boolean gap = false;

                            if (areInSame2DLocation(previousPoint, vertex)) {

                                // Buscamos si ha sido una bifurcaci?n

                                previousPoint = getPossibleFork(auxMultiLine, vertex);

                                // OJO, aqu? previousPoint pasa a ser 2DM

                            } else {

                                // En caso de salto, calculamos el previousPoint

                                previousPoint = getClosestVertex(auxMultiLine, vertex);

                                // OJO, aqu? previousPoint pasa a ser 2DM

                                gap = true;

                            }

                            previousM = previousPoint.getCoordinateAt(previousPoint.getDimension() - 1);

                            if (j == 0) {

                                firstM = previousM;

                            }

                            if (gap && !ignoreSpatialGaps) {

                                Point previousVertex = getPreviousVertexToPoint(auxMultiLine, previousPoint);

                                previousVertex.getCoordinateAt(previousVertex.getDimension() - 1);

                                previousM =

                                    strightLineThroughTwoPointsEquation(0, previousVertex.distance(previousPoint),

                                        previousVertex.getCoordinateAt(previousVertex.getDimension() - 1), previousM,

                                        previousVertex.distance(previousPoint) + previousPoint.distance(point));

                                firstM = previousM;

                            }

                        }

                        if (j != 0) {

                            distance += previousPoint.distance(vertex);

                        }

                        double m =

                            strightLineThroughTwoPointsEquation(0, geometryLength, firstM, firstM + mSegment.fromValue,

                                distance);

                        point.setCoordinateAt(point.getDimension() - 1, m);

                        auxLine.addVertex(point);

                        previousM = m;

                        previousPoint = vertex;

                    }

                    multiline.addPrimitive(auxLine);

                }

            } else {

                // NO deber?a entrar por aqu?

                logger.warn("A not LINE nor MULTILINE geometry found in CreateRoute process");

            }

        }

        return compactMultiLine(auxMultiLine);

    }

    /**

     * Joins consecutive adjacent lines into the multiLine that are not involved in a fork

     *

     * @param auxMultiLine

     * @return

     * @throws CreateGeometryException

     * @throws GeometryOperationException

     * @throws GeometryOperationNotSupportedException

     */

    private MultiLine compactMultiLine(MultiLine multiLine) throws CreateGeometryException, GeometryOperationNotSupportedException, GeometryOperationException {

        GeometryManager geomManager = GeometryLocator.getGeometryManager();

        MultiLine result =  (MultiLine) geomManager.create(multiLine.getGeometryType());

        int primitivesNumber = multiLine.getPrimitivesNumber();

        List<Line> lines = new ArrayList<Line>(primitivesNumber);

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

            lines.add((Line)multiLine.getPrimitiveAt(i).cloneGeometry());

        }

        if (lines.size() > 0) {

            Line line = lines.get(0);

            while (lines.size() > 1) {

                Point lastVertex = line.getVertex(line.getNumVertices() - 1);

                lines.remove(0);

                // Borramos la primera linea de la lista ==> lines.get(0) es la siguiente

                Line line2 = lines.get(0);

                // Si el ultimo punto de la primera

                if (lastVertex.equals(line2.getVertex(0)) && !bifurcation(lastVertex, lines)) {

                    for(int i = 1; i<line2.getNumVertices(); i++){

                        line.addVertex(line2.getVertex(i));

                    }

                } else {

                    result.addPrimitive(line);

                    line = line2;

                }

            }

            result.addPrimitive(line);

        }

        return result;

    }

    /**

     * Checks if a bifurcation occurs at one point.

     *

     * @param point

     * @param lines

     * @return

     */

    private boolean bifurcation(Point point, List<org.gvsig.fmap.geom.primitive.Line> lines) {

        // Saltamos la primera linea

        for(int i = 1; i<lines.size(); i++){

            if(point.equals(lines.get(i).getVertex(0))){

                return true;

            }

        }

        return false;

    }

    /**

     * Returns the previous vertex to a point.

     *

     * @param auxMultiLine

     * @param previousPoint

     * @return

     * @throws GeometryOperationException

     * @throws GeometryOperationNotSupportedException

     * @throws CreateGeometryException

     */

    private Point getPreviousVertexToPoint(MultiLine multiLine, Point point) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException {

        GeometryManager geomManager = GeometryLocator.getGeometryManager();

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

            Line line = (Line) multiLine.getPrimitiveAt(i);

            if (line.intersects(point)) {

                for (int j = 0; j < line.getNumVertices() - 1; j++) {

                    if (point.equals(line.getVertex(j + 1))) {

                        return line.getVertex(j);

                    }

                    Line auxLine = (Line) geomManager.create(Geometry.TYPES.LINE, Geometry.SUBTYPES.GEOM2DM);

                    auxLine.addVertex(line.getVertex(j));

                    auxLine.addVertex(line.getVertex(j + 1));

                    if (auxLine.intersects(point)) {

                        return line.getVertex(j);

                    }

                }

            }

        }

        return null;

    }

    /**

     * Checks if a bifurcation occurs at one point and return the vertex with maximum M

     *

     * @param multiLine

     * @param vertex

     * @return

     */

    private Point getPossibleFork(MultiLine multiLine, Point point) {

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

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

            Line line = (Line) multiLine.getPrimitiveAt(i);

            for (int j = 0; j < line.getNumVertices(); j++) {

                Point vertex = line.getVertex(j);

                if (areInSame2DLocation(vertex, point)) {

                    vertices.add(vertex);

                }

            }

        }

        if (vertices.size() > 0) {

            Double maxM = Double.NEGATIVE_INFINITY;

            Point forked = null;

            for (Iterator<Point> iterator = vertices.iterator(); iterator.hasNext();) {

                Point vertex = (Point) iterator.next();

                double m = vertex.getCoordinateAt(vertex.getDimension() - 1);

                if (m > maxM) {

                    maxM = m;

                    forked = vertex;

                }

            }

            return forked;

        }

        return null;

    }

    /**

     * Compares x & y coordinates of a point.

     *

     * @param p1

     * @param p2

     * @return

     */

    private boolean areInSame2DLocation(Point p1, Point p2) {

        return ((p1.getX() == p2.getX()) && (p1.getY() == p2.getY()));

    }

    /**

     * Returns the vertex of the multiline closest to a point

     *

     * @param mGeometry

     * @param vertex

     * @return

     * @throws GeometryOperationException

     * @throws GeometryOperationNotSupportedException

     * @throws CreateEnvelopeException

     */

    private Point getClosestVertex(MultiLine multiLine, Point point) throws CreateEnvelopeException,

        GeometryOperationNotSupportedException, GeometryOperationException {

        Point result = null;

        double minDistance = Double.POSITIVE_INFINITY;

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

            Line line = (Line) multiLine.getPrimitiveAt(i);

            for (int j = 0; j < line.getNumVertices(); j++) {

                Point vertex = line.getVertex(j);

                double distance = point.distance(vertex);

                if (distance <= minDistance) {

                    minDistance = distance;

                    result = vertex;

                }

            }

        }

        return result;

    }

    /**

     * Returns a multiline calculate by two field method

     *

     * @param mList

     * @return

     * @throws CreateGeometryException

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private MultiLine calculateGeometryByTwoField(List<MSegment> mList) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException {

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

        MultiLine mGeometry = (MultiLine) geomanager.create(Geometry.TYPES.MULTILINE, Geometry.SUBTYPES.GEOM2DM);

        for (MSegment mSegment : mList) {

            Geometry geometry = mSegment.geometry;

            List<Line> geometryLines = extractLines(geometry);

            Double geometryLength = LrsAlgorithmUtils.getGeometryLength(geometry);

            Double geometryMFirstPoint = mSegment.fromValue;

            Double geometryMLastPoint = mSegment.toValue;

            Double distance = Double.valueOf(0);

            for (Line line : geometryLines) {

                Double lineLength = getLineLength(line);

                Double mFirstPoint = calculateM(geometryMLastPoint, geometryMFirstPoint, distance, geometryLength);

                distance += lineLength;

                Double mLastPoint = calculateM(geometryMLastPoint, geometryMFirstPoint, distance, geometryLength);

                Line mLine = lineToMLine(line, mFirstPoint, mLastPoint);

                mGeometry.addPrimitive(mLine);

            }

        }

        return mGeometry;

    }

    /**

     * Converts a Line2D in a Line2DM filled it with proportional calculated M's

     *

     * @param line

     * @param minMValue

     * @param maxMValue

     * @return

     * @throws CreateGeometryException

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private Line lineToMLine(Line line, Double minMValue, Double maxMValue) throws CreateGeometryException,

        GeometryOperationNotSupportedException, GeometryOperationException {

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

        Double lineLength = getLineLength(line);

        Line lineM = (Line) geomanager.create(Geometry.TYPES.LINE, Geometry.SUBTYPES.GEOM2DM);

        Double inLineDistance = Double.valueOf(0);

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

            Point vertex = line.getVertex(i);

            Point mVertex = (Point) geomanager.create(Geometry.TYPES.POINT, Geometry.SUBTYPES.GEOM2DM);

            mVertex.setX(vertex.getX());

            mVertex.setY(vertex.getY());

            Double mValue;

            if (i == 0)

                mValue = minMValue;

            else if (i == line.getNumVertices() - 1)

                mValue = maxMValue;

            else {

                Point previousVertex = line.getVertex(i - 1);

                inLineDistance += vertex.distance(previousVertex);

                mValue = calculateM(maxMValue, minMValue, inLineDistance, lineLength);

            }

            mVertex.setCoordinateAt(mVertex.getDimension() - 1, mValue);

            lineM.addVertex(mVertex);

        }

        return lineM;

    }

    /**

     * Reduced versi?n of stright line through two points equation to calculate M's

     *

     * @param maxValue

     * @param minValue

     * @param relativeDistance

     * @param totalLength

     * @return

     */

    private Double calculateM(Double maxValue, Double minValue, Double relativeDistance, Double totalLength) {

        if (totalLength.equals(Double.valueOf(0)))

            return Double.POSITIVE_INFINITY;

        return ((maxValue - minValue) * (relativeDistance) / (totalLength)) + minValue;

    }

    /**

     * Stright line through two points equation.

     *

     * @param x1

     * @param x2

     * @param y1

     * @param y2

     * @param x

     * @return

     */

    private double strightLineThroughTwoPointsEquation(double x1, double x2, double y1, double y2, double x) {

        if (x2 - x1 == 0.0) {

            return Double.POSITIVE_INFINITY;

        }

        return ((y2 - y1) * (x - x1) / (x2 - x1)) + y1;

    }

    /**

     * Simplify the multilines in mList calling simplifyMultiline method

     *

     * @param mList

     * @throws CreateGeometryException

     * @throws LocatorException

     */

    private void simplifyMultilines(List<MSegment> mList) throws CreateGeometryException, LocatorException {

        for (MSegment mSegment : mList) {

            mSegment.geometry = simplifyMultiline(mSegment.geometry);

        }

    }

    /**

     * Simplify a Multiline ordering and joining her lines if can.

     *

     * @param geometry

     * @return

     * @throws CreateGeometryException

     * @throws LocatorException

     */

    private Geometry simplifyMultiline(Geometry geometry) throws CreateGeometryException, LocatorException {

        if (geometry instanceof MultiLine) {

            MultiLine multiline = (MultiLine) geometry;

            if (multiline.getPrimitivesNumber() == 1) {

                return multiline.getPrimitiveAt(0);

            } else {

                List<Line> simplifiedLines = new ArrayList<Line>();

                List<Line> complexLines = new ArrayList<Line>();

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

                    complexLines.add((Line) multiline.getPrimitiveAt(i));

                }

                Line line = null;

                while (complexLines.size() > 0) {

                    line = complexLines.remove(0);

                    int i = 0;

                    while (i < complexLines.size()) {

                        Line auxLine = complexLines.get(i);

                        Line unitedLine = unionAdjacentLines(line, auxLine);

                        if (unitedLine != null) {

                            line = unitedLine;

                            complexLines.remove(i);

                            i = 0;

                        } else {

                            i++;

                        }

                    }

                    simplifiedLines.add(line);

                }

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

                    geometry = simplifiedLines.get(0);

                } else {

                    MultiLine simplifiedMultiLine =

                        (MultiLine) GeometryLocator.getGeometryManager().create(multiline.getGeometryType());

                    for (Line simpleLine : simplifiedLines) {

                        simplifiedMultiLine.addPrimitive(simpleLine);

                    }

                    return simplifiedMultiLine;

                }

            }

        }

        return geometry;

    }

    /**

     * Join two adjacent lines flipping it if necessary

     *

     * @param line1

     * @param line2

     * @return

     */

    private Line unionAdjacentLines(Line line1, Line line2) {

        if (line1 == null || line2 == null) {

            return null;

        }

        Line resultLine;

        try {

            resultLine = (Line) GeometryLocator.getGeometryManager().create(line1.getGeometryType());

        } catch (Exception e) {

            return null;

        }

        Point firstPointL1 = line1.getVertex(0);

        Point lastPointL1 = line1.getVertex(line1.getNumVertices() - 1);

        Point firstPointL2 = line2.getVertex(0);

        Point lastPointL2 = line2.getVertex(line2.getNumVertices() - 1);

        if (lastPointL1.equals(firstPointL2)) {

            resultLine = (Line) line1.cloneGeometry();

            for (int i = 1; i < line2.getNumVertices(); i++) {

                resultLine.addVertex((Point) line2.getVertex(i).cloneGeometry());

            }

            return resultLine;

        }

        if (lastPointL2.equals(firstPointL1)) {

            resultLine = (Line) line2.cloneGeometry();

            for (int i = 1; i < line1.getNumVertices(); i++) {

                resultLine.addVertex((Point) line1.getVertex(i).cloneGeometry());

            }

            return resultLine;

        }

        if (firstPointL1.equals(firstPointL2)) {

            for (int i = line1.getNumVertices() - 1; i >= 0; i--) {

                resultLine.addVertex((Point) line1.getVertex(i).cloneGeometry());

            }

            for (int i = 1; i < line2.getNumVertices(); i++) {

                resultLine.addVertex((Point) line2.getVertex(i).cloneGeometry());

            }

            return resultLine;

        }

        if (lastPointL1.equals(lastPointL2)) {

            resultLine = (Line) line1.cloneGeometry();

            for (int i = line2.getNumVertices() - 2; i >= 0; i--) {

                resultLine.addVertex((Point) line2.getVertex(i).cloneGeometry());

            }

            return resultLine;

        }

        return null;

    }

    /**

     * Sorts mList

     *

     * @param mList

     * @return

     * @throws CreateEnvelopeException

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private List<MSegment> sortMList(List<MSegment> mList) throws CreateEnvelopeException,

        GeometryOperationNotSupportedException, GeometryOperationException {

        LrsCoordinatesPriority coordinatePriority = parameters.getCoordinatePriority();

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

        Envelope envelope = geomanager.createEnvelope(Geometry.SUBTYPES.GEOM2D);

        for (MSegment mSegment : mList) {

            envelope.add(mSegment.geometry.getEnvelope());

        }

        Point origin = envelope.getLowerCorner();

        switch (coordinatePriority) {

        case DOWN_LEFT:

            break;

        case DOWN_RIGHT:

            Double maxX = envelope.getMaximum(DIMENSIONS.X);

            origin.setX(maxX);

            break;

        case UP_LEFT:

            Double maxY = envelope.getMaximum(DIMENSIONS.Y);

            origin.setY(maxY);

            break;

        case UP_RIGHT:

            origin = envelope.getUpperCorner();

            break;

        default:

            break;

        }

        List<Stretch> stretches = createStretches(mList, origin);

        stretches = sortStretches(stretches, origin);

        return extractSegmentsFromStretches(stretches);

    }

    /**

     * Extracts segment from stretches and returns a list of segment.

     *

     * @param stretches

     * @return

     */

    private List<MSegment> extractSegmentsFromStretches(List<Stretch> stretches) {

        List<MSegment> result = new ArrayList<MSegment>();

        for (Stretch stretch : stretches) {

            for (int i = 0; i < stretch.getSegmentNumber(); i++) {

                result.add(stretch.getSegment(i));

            }

        }

        return result;

    }

    /**

     * Sort the stretches

     *

     * @param stretches

     * @param origin

     * @return

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private List<Stretch> sortStretches(List<Stretch> stretches, Point origin)

        throws GeometryOperationNotSupportedException, GeometryOperationException {

        List<Stretch> result = new ArrayList<Stretch>();

        Point originPoint = origin;

        while (result.size() < stretches.size()) {

            // Buscamos tramos que sean adyacentes al origin

            if (result.size() == 0) {

                addUnvisitedAdjacentStretches(stretches, result, originPoint);

            }

            if (result.size() == 0) {

                result.add(getNearestUnvisitedStretch(stretches, originPoint, result));

            }

            boolean addedAdjacentStretches = true;

            while (addedAdjacentStretches) {

                addedAdjacentStretches = false;

                int visitedNumber = result.size();

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

                    Stretch visited = result.get(i);

                    addUnvisitedAdjacentStretches(stretches, result, visited.getFinalPoint());

                }

                addedAdjacentStretches = (visitedNumber < result.size());

            }

            int visitedNumber = result.size();

            for (int i = visitedNumber - 1; i >= 0; i--) {

                Stretch visited = result.get(i);

                Stretch nearest = getNearestUnvisitedStretch(stretches, visited.getFinalPoint(), result);

                if (nearest != null) {

                    result.add(nearest);

                    break;

                }

            }

        }

        return result;

    }

    /**

     * Adds unvisited adjacent stretches to the visited list

     *

     * @param stretches

     * @param visited

     * @param originPoint

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private void addUnvisitedAdjacentStretches(List<Stretch> stretches, List<Stretch> visited, Point originPoint)

        throws GeometryOperationNotSupportedException, GeometryOperationException {

        for (Stretch stretch : stretches) {

            if (!visited.contains(stretch)) {

                if (areInSame2DLocation(stretch.getInitialPoint(), originPoint)) {

                    visited.add(stretch);

                } else if (areInSame2DLocation(stretch.getFinalPoint(), originPoint)) {

                    visited.add(stretch.flip());

                }

            }

        }

    }

    /**

     * Returns the unvisited stretch nearest to a point

     *

     * @param stretches

     * @param origin

     * @param visited

     * @return

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private Stretch getNearestUnvisitedStretch(List<Stretch> stretches, Point origin, List<Stretch> visited)

        throws GeometryOperationNotSupportedException, GeometryOperationException {

        double minDistance = Double.POSITIVE_INFINITY;

        Stretch nearest = null;

        boolean needFlip = false;

        for (Stretch stretch : stretches) {

            if (!visited.contains(stretch)) {

                Double initialDistance = origin.distance(stretch.getInitialPoint());

                if (initialDistance < minDistance) {

                    minDistance = initialDistance;

                    nearest = stretch;

                    needFlip = false;

                }

                Double finalDistance = origin.distance(stretch.getFinalPoint());

                if (finalDistance < minDistance) {

                    minDistance = finalDistance;

                    nearest = stretch;

                    needFlip = true;

                }

            }

        }

        if (needFlip && nearest != null) {

            nearest.flip();

        }

        return nearest;

    }

    /**

     * Creates stretches from mList and returns a list of stretches

     *

     * @param mList

     * @param origin

     * @return

     * @throws GeometryOperationNotSupportedException

     * @throws GeometryOperationException

     */

    private List<Stretch> createStretches(List<MSegment> mList, Point origin)

        throws GeometryOperationNotSupportedException, GeometryOperationException {

        List<MSegment> addedMSegment = new ArrayList<LrsCreateRouteAlgorithm.MSegment>();

        List<Stretch> stretches = new ArrayList<Stretch>();

        while (addedMSegment.size() < mList.size()) {

            for (MSegment mSegment : mList) {

                if (!addedMSegment.contains(mSegment)) {

                    Stretch stretch = new Stretch();

                    stretches.add(stretch);

                    stretch.addSegment(mSegment);

                    addedMSegment.add(mSegment);

                    List<MSegment> initialNextSegments =

                        mSegment.searchNextSegments(stretch.getInitialPoint(), mList);

                    do {

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

                            MSegment previousSegment = initialNextSegments.get(0);

                            if (!addedMSegment.contains(previousSegment)) {

                                if (!previousSegment.getFinalPoint().equals(stretch.getInitialPoint())) {

                                    previousSegment.flip();

                                }

                                stretch.addSegment(0, previousSegment);

                                addedMSegment.add(previousSegment);

                                initialNextSegments =

                                    previousSegment.searchNextSegments(stretch.getInitialPoint(), mList);

                            } else {

                                break;

                            }

                        } else {

                            break;

                        }

                    } while (initialNextSegments.size() == 1);

                    List<MSegment> finalNextSegments =

                        mSegment.searchNextSegments(stretch.getFinalPoint(), mList);

                    do {

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

                            MSegment nextSegment = finalNextSegments.get(0);

                            if (!addedMSegment.contains(nextSegment)) {

                                if (!nextSegment.getInitialPoint().equals(stretch.getFinalPoint())) {

                                    nextSegment.flip();

                                }

                                stretch.addSegment(nextSegment);

                                addedMSegment.add(nextSegment);

                                finalNextSegments =

                                    nextSegment.searchNextSegments(stretch.getFinalPoint(), mList);

                            } else {

                                break;

                            }

                        } else {

                            break;

                        }

                    } while ((finalNextSegments.size() == 1));

                }

            }

        }

        return stretches;

    }

    /**

     * Extracts lines of a geometry.

     *

     * @param geometry

     * @return

     */

    private List<Line> extractLines(Geometry geometry) {

        List<Line> lines = new ArrayList<Line>();

        if (geometry instanceof Line) {

            lines.add((Line) geometry);

        }

        if (geometry instanceof MultiLine) {

            MultiLine multiline = (MultiLine) geometry;

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

                lines.add((Line) multiline.getPrimitiveAt(i));

            }

        }

        return lines;

    }

    /**

     * Applies offsetAndFactor to a route

     *

     * @param geometry

     * @return

     */

    private Geometry applyOffsetAndFactor(Geometry geometry) {

        double measureFactor = parameters.getMeasureFactor();

        double measureOffset = parameters.getMeasureOffset();

        if (geometry instanceof Line) {

            Line line = (Line) geometry;

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

                Point mVertex = line.getVertex(i);

                Double mValue = mVertex.getCoordinateAt(mVertex.getDimension() - 1);

                Double newMValue = (mValue * measureFactor) + measureOffset;

                mVertex.setCoordinateAt(mVertex.getDimension() - 1, newMValue);

                line.setVertex(i, mVertex);

            }

        }

        if (geometry instanceof MultiLine) {

            MultiLine multiLine = (MultiLine) geometry;

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

                Line line = (Line) multiLine.getPrimitiveAt(i);

                for (int j = 0; j < line.getNumVertices(); j++) {

                    Point mVertex = line.getVertex(j);

                    Double mValue = mVertex.getCoordinateAt(mVertex.getDimension() - 1);

                    Double newMValue = (mValue * measureFactor) + measureOffset;

                    mVertex.setCoordinateAt(mVertex.getDimension() - 1, newMValue);

                    line.setVertex(j, mVertex);

                }

            }

        }

        return geometry;

    }

    /**

     * Returns the geometric length of a line

     *

     * @param line

     * @return lenght

     * @throws GeometryOperationException

     * @throws GeometryOperationNotSupportedException

     */

    private double getLineLength(Line line) throws GeometryOperationNotSupportedException, GeometryOperationException {

        double lenght = 0;

        Point previousVertex = null;

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

            Point vertex = line.getVertex(i);

            if (previousVertex != null) {

                lenght += previousVertex.distance(vertex);

            }

            previousVertex = vertex;

        }

        return lenght;

    }

    /*

     * (non-Javadoc)

     *

     * @see org.gvsig.lrs.lib.api.LrsAlgorithm#setParams(org.gvsig.lrs.lib.api.

     * LrsAlgorithmParams)

     */

    public void setParams(LrsAlgorithmParams params) throws IllegalArgumentException {

        if (!(params instanceof LrsCreateRouteAlgorithmParams)) {

            throw new IllegalArgumentException("params should be LrsCreateRouteAlgorithmParams type.");

        }

    }

    private class MSegment {

        Geometry geometry;

        Double fromValue;

        Double toValue;

        int id;

        protected MSegment clone() {

            MSegment cloned = new MSegment();

            cloned.geometry = geometry.cloneGeometry();

            cloned.fromValue = null;

            if (fromValue != null) {

                cloned.fromValue = new Double(fromValue);

            }

            cloned.toValue = null;

            if (toValue != null) {

                cloned.toValue = new Double(toValue);

            }

            cloned.id = id;

            return cloned;

        }

        protected Point getInitialPoint() {

            if (geometry instanceof Line) {

                Line line = ((Line) geometry);

                return line.getVertex(0);

            } else if (geometry instanceof MultiLine) {

                MultiLine multiLine = (MultiLine) geometry;

                Line firstLine = ((Line) multiLine.getPrimitiveAt(0));

                return firstLine.getVertex(0);

            }

            return null;

        }

        protected Point getFinalPoint() {

            if (geometry instanceof Line) {

                Line line = ((Line) geometry);

                return line.getVertex(line.getNumVertices() - 1);

            } else if (geometry instanceof MultiLine) {

                MultiLine multiLine = (MultiLine) geometry;

                Line lastLine = ((Line) multiLine.getPrimitiveAt(multiLine.getPrimitivesNumber() - 1));

                return lastLine.getVertex(lastLine.getNumVertices() - 1);

            }

            return null;

        }

        protected void flip() throws GeometryOperationNotSupportedException, GeometryOperationException {

            geometry.flip();

        }

        /**

         * @param point

         * @param mList

         * @return

         */

        protected List<MSegment> searchNextSegments(Point point, List<MSegment> mList) {

            List<MSegment> result = new ArrayList<LrsCreateRouteAlgorithm.MSegment>();

            for (Iterator<MSegment> iterator = mList.iterator(); iterator.hasNext();) {

                MSegment mSegment = (MSegment) iterator.next();

                if (mSegment != this) { // !addedSegments.contains(mSegment)) {

                    Geometry geom = mSegment.geometry;

                    if (geom instanceof Line) {

                        Line line = ((Line) geom);

                        if (line.getVertex(0).equals(point) || line.getVertex(line.getNumVertices() - 1).equals(point)) {

                            result.add(mSegment);

                        }

                        ;

                    } else if (geom instanceof MultiLine) {

                        MultiLine multiLine = (MultiLine) geom;

                        Line firstLine = ((Line) multiLine.getPrimitiveAt(0));

                        Line lastLine = ((Line) multiLine.getPrimitiveAt(multiLine.getPrimitivesNumber() - 1));

                        if (firstLine.getVertex(0).equals(point)

                            || lastLine.getVertex(lastLine.getNumVertices() - 1).equals(point)) {

                            result.add(mSegment);

                        }

                    }

                }

            }

            return result;

        }

        public double getLength(boolean ignoreSpatialGaps) throws GeometryOperationNotSupportedException,

            GeometryOperationException {

            return LrsAlgorithmUtils.getGeometryLength(geometry, ignoreSpatialGaps);

        }

    }

    private class Stretch {

        private List<MSegment> segments;

        private Point initialPoint;

        private Point finalPoint;

        public Stretch() {

            segments = new ArrayList<MSegment>();

        }

        public MSegment getSegment(int index) {

            return segments.get(index);

        }

        public int getSegmentNumber() {

            return segments.size();

        }

        public void addSegment(MSegment segment) {

            if (segments.isEmpty()) {

                initialPoint = segment.getInitialPoint();

            }

            finalPoint = segment.getFinalPoint();

            segments.add(segment);

        }

        public void addSegment(int index, MSegment segment) {

            if (index == 0) {

                initialPoint = segment.getInitialPoint();

            }

            if (index >= segments.size()) {

                finalPoint = segment.getFinalPoint();

            }

            segments.add(index, segment);

        }

        public double getLength(boolean ignoreSpatialGaps) throws GeometryOperationNotSupportedException,

            GeometryOperationException {

            double result = 0.0;

            for (MSegment segment : segments) {

                result += segment.getLength(ignoreSpatialGaps);

            }

            return result;

        }

        public Stretch flip() throws GeometryOperationNotSupportedException, GeometryOperationException {

            Collections.reverse(segments);

            for (Iterator<MSegment> iterator = segments.iterator(); iterator.hasNext();) {

                MSegment segment = (MSegment) iterator.next();

                segment.flip();

            }

            Point aux = initialPoint;

            initialPoint = finalPoint;

            finalPoint = aux;

            return this;

        }

        public Point getInitialPoint() {

            return initialPoint;

        }

        public Point getFinalPoint() {

            return finalPoint;

        }

    }

}