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

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Map.Entry;

import java.util.SortedMap;

import java.util.TreeMap;

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

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

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

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;

import org.omg.CosNaming.IstringHelper;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

/**

 * @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();

        // LrsCoordinatesPriority coordinatePriority =

        // parameters.getCoordinatePriority();

        // LrsSourceOfMeasures sourceOfMeasures =

        // parameters.getSourceOfMeasures();

        FeatureAttributeDescriptor fromMeasureField =

            parameters.getFromMeasureField();

        FeatureAttributeDescriptor toMeasureField =

            parameters.getToMeasureField();

        // double measureFactor = parameters.getMeasureFactor();

        // double measureOffset = parameters.getMeasureOffset();

        // boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

        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<MStructure>> featuresMap =

                new TreeMap<String, List<MStructure>>();

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

                    Geometry originalGeometry = feature.getDefaultGeometry();

                    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<MStructure>());

                    }

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

                    MStructure mStructure = new MStructure();

                    mStructure.geometry = originalGeometry;

                    mStructure.fromField =

                        LrsAlgorithmUtils.getAsDouble(objFrom, fromDataType);

                    mStructure.toField =

                        LrsAlgorithmUtils.getAsDouble(objTo, toDataType);

                    mStructure.id=contId.getValue();

                    contId.increment();

                    mList.add(mStructure);

                    featuresMap.put(routeName, mList);

                }

            });

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

            int taskCount = 0;

            newFeatureStore.edit(FeatureStore.MODE_FULLEDIT);

            // TODO Added to facilitate Tests. Remove afterwards

            StringBuffer resultDebug = new StringBuffer();

            LrsSourceOfMeasures sourceOfMeasures =

                parameters.getSourceOfMeasures();

            boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

            LrsCoordinatesPriority coordinatePriority =

                parameters.getCoordinatePriority();

            resultDebug.append(sourceOfMeasures.getName());

            if (!sourceOfMeasures.equals(LrsSourceOfMeasures.TWO_FIELDS)) {

                if (ignoreSpatialGaps)

                    resultDebug.append(" WITHOUT GAPS ");

                else

                    resultDebug.append(" WITH GAPS ");

                resultDebug.append(coordinatePriority.getName());

            }

            // END of Test addition

            for (Entry<String, List<MStructure>> entry : featuresMap

                .entrySet()) {

                String routeName = entry.getKey();

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

                EditableFeature newFeature =

                    newFeatureStore.createNewFeature(true);

                newFeature.set(routeFieldName, routeName);

                Geometry route = createGeometryRoute(mList);

                newFeature.setDefaultGeometry(route);

                // TODO Added to facilitate Tests. Remove afterwards

                String lineSeparator = System.getProperty("line.separator");

                resultDebug.append(lineSeparator);

                resultDebug.append("Route: " + routeName);

                resultDebug.append(lineSeparator);

                if (route instanceof MultiLine) {

                    MultiLine multiLine = (MultiLine) route;

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

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

                        resultDebug.append("Line " + j + ":[");

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

                            Point point = line.getVertex(i);

                            Double x = point.getX();

                            Double y = point.getY();

                            Double m =

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

                            resultDebug.append("(x=" + x.toString() + ",y="

                                + y.toString() + ",m=" + m.toString() + ")");

                        }

                        resultDebug.append("]");

                        resultDebug.append(lineSeparator);

                    }

                }

                // END of Test addition

                newFeatureStore.update(newFeature);

                taskCount++;

                taskStatus.setCurValue(taskCount);

            }

            logger.debug(resultDebug.toString());

            newFeatureStore.finishEditing();

        } catch (Exception e1) {

            taskStatus.abort();

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

        }

        taskStatus.terminate();

    }

    private Geometry createGeometryRoute(List<MStructure> mList)

        throws CreateGeometryException, GeometryOperationNotSupportedException,

        GeometryOperationException {

        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 = simplifyMultiline(geometryResult);

        geometryResult = applyOffset(geometryResult);

        return geometryResult;

    }

    private Geometry calculateGeometryByLength(List<MStructure> mList)

        throws CreateGeometryException, GeometryOperationNotSupportedException,

        GeometryOperationException {

        boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

        for (MStructure mStructure : mList) {

            mStructure.fromField =

                getGeometryLength(mStructure.geometry, ignoreSpatialGaps);

        }

        return calculateGeometryByOneField(mList);

    }

    private Geometry calculateGeometryByOneField(List<MStructure> mList)

        throws CreateGeometryException, GeometryOperationNotSupportedException,

        GeometryOperationException {

        boolean ignoreSpatialGaps = parameters.ignoreSpatialGaps();

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

        try {

            mList=sortMList(mList);

        } catch (Exception e) {

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

        }

        MultiLine mGeometry = (MultiLine) geomanager

            .create(Geometry.TYPES.MULTILINE, Geometry.SUBTYPES.GEOM2DM);

        //MutableDouble lastMValue = new MutableDouble(0);

        Double lastMValueGeometry= Double.valueOf(0);

        Double gapBetweenGeometries = Double.valueOf(0);

        Point lastPoint = null;

        for (MStructure mStructure : mList) {

            Geometry geometry = mStructure.geometry;

            List<Line> geometryLines=extractLines(geometry);

            Double geometryLength=getGeometryLength(geometry, ignoreSpatialGaps);

            boolean firstLineInGeometry=true;

            if (!ignoreSpatialGaps) {

                gapBetweenGeometries = calculateGap(lastPoint, geometry);

                lastMValueGeometry+=gapBetweenGeometries;

            }

            Double previouslyCalculatedMValue= getCalculatedMValueForFirstPoint(mGeometry,geometry);

            if (previouslyCalculatedMValue!=null){

                lastPoint=null;

                lastMValueGeometry=previouslyCalculatedMValue;

            }

            Double geometryMFirstPoint = lastMValueGeometry;

            lastMValueGeometry+=mStructure.fromField;

            Double geometryMLastPoint=lastMValueGeometry;

            Double distance=Double.valueOf(0);;

            for (Line line:geometryLines){

                Double gapBetweenLines = Double.valueOf(0);

                Double lineLength=getLineLength(line);

                if (!ignoreSpatialGaps&&!firstLineInGeometry) {

                    gapBetweenLines = calculateGap(lastPoint, line);

                    distance+=gapBetweenLines;

                    firstLineInGeometry=false;

                }

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

                lastPoint = mLine.getVertex(mLine.getNumVertices() - 1);

            }

        }

        return mGeometry;

//        for (MStructure mStructure : mList) {

//            Geometry geometry = mStructure.geometry;

//

//            if (!ignoreSpatialGaps) {

//                gapBetweenLines = calculateGap(lastPoint, geometry);

//                lastMValue.add(gapBetweenLines);

//            }

//            Double fromDistance = lastMValue.getValue();

//            lastMValue.add(mStructure.fromField);

//            Double toDistance = lastMValue.getValue();

//

//            if (geometry instanceof Line) {

//                Line line = (Line) geometry;

//                Line lineM = lineToMLine(line, fromDistance, toDistance);

//                mGeometry.addPrimitive(lineM);

//                lastPoint = lineM.getVertex(lineM.getNumVertices() - 1);

//            }

//            if (geometry instanceof MultiLine) {

//                MultiLine multiLine = (MultiLine) geometry;

//                Line[] lines = multilineToMlines(multiLine, fromDistance,

//                    toDistance, ignoreSpatialGaps);

//                for (Line lineM : lines) {

//                    mGeometry.addPrimitive(lineM);

//                    lastPoint = lineM.getVertex(lineM.getNumVertices() - 1);

//                }

//            }

//        }

//        return mGeometry;

    }

    private Double getCalculatedMValueForFirstPoint(Geometry mGeometry,Geometry geometry){

        List<Point> mPoints=extractPoints(mGeometry);

        Point point=extractFirstPoint(geometry);

        for (Point mPoint:mPoints){

            if ( mPoint.getX()==point.getX() && mPoint.getY()==point.getY() ){

                int dimensionM=mPoint.getDimension()-1;

                return mPoint.getCoordinateAt(dimensionM);

            }

        }

        return null;

    }

    private Geometry calculateGeometryByTwoField(List<MStructure> mList)

        throws CreateGeometryException, GeometryOperationNotSupportedException,

        GeometryOperationException {

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

        MultiLine mGeometry = (MultiLine) geomanager

            .create(Geometry.TYPES.MULTILINE, Geometry.SUBTYPES.GEOM2DM);

        for (MStructure mStructure : mList) {

            Geometry geometry = mStructure.geometry;

            List<Line> geometryLines=extractLines(geometry);

            Double geometryLength=getGeometryLength(geometry);

            Double geometryMFirstPoint = mStructure.fromField;

            Double geometryMLastPoint=mStructure.toField;

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

            }

        }

//        for (MStructure mStructure : mList) {

//            Geometry geometry = mStructure.geometry;

//            Double fromDistance = mStructure.fromField;

//            Double toDistance = mStructure.toField;

//            if (geometry instanceof Line) {

//                Line line = (Line) geometry;

//                Line lineM = lineToMLine(line, fromDistance, toDistance);

//                mGeometry.addPrimitive(lineM);

//            }

//            if (geometry instanceof MultiLine) {

//                MultiLine multiLine = (MultiLine) geometry;

//                Line[] lines =

//                    multilineToMlines(multiLine, fromDistance, toDistance);

//                for (Line lineM : lines) {

//                    mGeometry.addPrimitive(lineM);

//                }

//            }

//        }

        return mGeometry;

    }

//    private Line[] multilineToMlines(MultiLine multiLine, Double fromDistance,

//        Double toDistance) throws GeometryOperationNotSupportedException,

//            GeometryOperationException, CreateGeometryException {

//        return multilineToMlines(multiLine, fromDistance, toDistance, true);

//    }

//

//    private Line[] multilineToMlines(MultiLine multiLine, Double fromDistance,

//        Double toDistance, boolean ignoreSpatialGaps)

//            throws GeometryOperationNotSupportedException,

//            GeometryOperationException, CreateGeometryException {

//

//        Line[] lines = new Line[multiLine.getPrimitivesNumber()];

//        Double multiLineLength =

//            getMultiLineLength(multiLine, ignoreSpatialGaps);

//        Double mFirstPoint = fromDistance;

//        Double mLastPoint = null;

//        Double distance = Double.valueOf(0);

//        Point lastPoint = null;

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

//

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

//            Double lineLength = getLineLength(line);

//            Double gap = Double.valueOf(0);

//

//            if (!ignoreSpatialGaps && lastPoint != null) {

//                Point firstPoint = line.getVertex(0);

//                gap = firstPoint.distance(lastPoint);

//                distance += gap;

//            }

//            mFirstPoint =

//                calculateM(toDistance, fromDistance, distance, multiLineLength);

//            distance += lineLength;

//            mLastPoint =

//                calculateM(toDistance, fromDistance, distance, multiLineLength);

//            lines[i] = lineToMLine(line, mFirstPoint, mLastPoint);

//            lastPoint = lines[i].getVertex(line.getNumVertices() - 1);

//        }

//        return lines;

//    }

    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;

    }

    private Double calculateM(Double maxValue, Double minValue,

        Double relativeDistance, Double totalLength) {

        // mValue=((newMax-newMin)*(mCoordinate-oldMin)/(oldMax-oldMin))+newMin;

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

            return Double.POSITIVE_INFINITY;

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

            + minValue;

    }

    private void simplifyMultilines(List<MStructure> mList)

        throws CreateGeometryException, LocatorException {

        List<MStructure> simplifiedMList = new ArrayList<MStructure>();

        for (MStructure mStructure : mList) {

            mStructure.geometry=simplifyMultiline(mStructure.geometry);

            simplifiedMList.add(mStructure);

        }

        mList = simplifiedMList;

    }

    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.get(0);

                    complexLines.remove(0);

                    int i=0;

                    while (i<complexLines.size()) {

                        Line auxLine=null;

                        if (complexLines.size()>0){

                            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;

    }

    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;

    }

//    private Double calculateGap(Point lastPoint, Line line)

//        throws GeometryOperationNotSupportedException,

//        GeometryOperationException {

//        Double gap = new Double(0);

//        if (lastPoint != null) {

//            Point firstPoint = line.getVertex(0);

//            gap = firstPoint.distance(lastPoint);

//        }

//        return gap;

//    }

    private Double calculateGap(Point lastPoint, Geometry geometry)

        throws GeometryOperationNotSupportedException,

        GeometryOperationException {

        Double gap = new Double(0);

        if (geometry instanceof Line) {

            Line line = (Line) geometry;

            if (lastPoint != null) {

                Point firstPoint = line.getVertex(0);

                gap = firstPoint.distance(lastPoint);

            }

        }

        if (geometry instanceof MultiLine) {

            MultiLine multiLine = (MultiLine) geometry;

            if (lastPoint != null) {

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

                Point firstPoint = line.getVertex(0);

                gap = firstPoint.distance(lastPoint);

            }

        }

        return gap;

    }

    private List<MStructure> sortMList(List<MStructure> mList)

        throws CreateEnvelopeException, GeometryOperationNotSupportedException,

        GeometryOperationException {

        LrsCoordinatesPriority coordinatePriority =

            parameters.getCoordinatePriority();

        GeometryManager geomanager = GeometryLocator.getGeometryManager();

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

        for (MStructure mStructure : mList) {

            envelope.add(mStructure.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<Route> routes=createRoutes(mList,origin);

        mList=extractMStructures(routes,origin,mList);

        return mList;

        //SECOND ATTEMPT

//        List<MStructure> orderedMlist=new ArrayList<MStructure>();

//        while (!mList.isEmpty()){

//            List<Point> orderedExtremePoints=getExtremePoints(mList,origin);

//            while ( !orderedExtremePoints.isEmpty() ){

//                Point initialPoint= orderedExtremePoints.get(0);

//                orderedExtremePoints.remove(0);

//                MStructure initialMStructure=getMStructureWithExtremePoint(initialPoint);

//                orderMStructure(initialMStructure,origin); //Flips Geometry if it is necessary.

//                orderedMlist.add(initialMStructure);

//                mList.remove(initialMStructure);

//                List<Point> pointsInMStructure=getPointsInMStructure(initialMStructure);

//                orderedExtremePoints.removeAll(pointsInMStructure);

//                Point nextPoint=getNextPointInLine(initialMStructure, initialPoint);

//                while (nextPoint!=null){

//                    MStructure nextMStructure=getMStructureWithNextPoint(nextPoint);

//                    orderMStructure(nextMStructure,origin);

//                    orderedMlist.add(initialMStructure);

//                    mList.remove(initialMStructure);

//                    pointsInMStructure=getPointsInMStructure(nextMStructure);

//                    orderedExtremePoints.removeAll(pointsInMStructure);

//                    nextPoint=getNextPointInLine(nextMStructure, nextPoint);

//                }

//            }

//        }

//        mList=orderedMlist;

        //FIRST ATTEMPT

//        GeometryDistanceToPointComparator comaparatorMList =

//            new GeometryDistanceToPointComparator(origin);

//        Collections.sort(mList, comaparatorMList);

//

//        for (MStructure mStructure : mList) {

//            Geometry geometry = mStructure.geometry;

//            if (geometry instanceof Line) {

//                Line line = (Line) geometry;

//                Double firstPointDistance = origin.distance(line.getVertex(0));

//                Double lastPointDistance =

//                    origin.distance(line.getVertex(line.getNumVertices() - 1));

//                if (lastPointDistance < firstPointDistance) {

//                    geometry.flip();

//                }

//            }

//            if (geometry instanceof MultiLine) {

//                MultiLine multiLine = (MultiLine) geometry;

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

//                Line lastLine = (Line) multiLine

//                    .getPrimitiveAt(multiLine.getPrimitivesNumber() - 1);

//                Double firstPointDistance =

//                    origin.distance(firstLine.getVertex(0));

//                Double lastPointDistance = origin.distance(

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

//                if (lastPointDistance < firstPointDistance) {

//                    geometry.flip();

//                }

//            }

//            mStructure.geometry = geometry;

//        }

    }

    private List<MStructure> extractMStructures(List<Route> routes, Point origin,List<MStructure> mList) throws GeometryOperationNotSupportedException, GeometryOperationException{

        List<MStructure> orderedMList=new ArrayList<MStructure>();

        Point initialPoint=origin;

        while (!routes.isEmpty()){

            Route route=getNearestRoute(routes, initialPoint, mList,origin);

            routes.remove(route);

            int i=0;

            while (!route.structures.isEmpty()){

                MStructure structure=route.structures.get(i);

                route.structures.remove(i);

                orderedMList.add(structure);

                removeRepeatedStructures(routes, structure);

            }

            initialPoint=route.finalPoint;

        }

        return orderedMList;

    }

    private Route getNearestRoute(List<Route> routes, Point point,List<MStructure> mList, Point originPoint)

        throws GeometryOperationNotSupportedException, GeometryOperationException{

        double minDistance = Double.POSITIVE_INFINITY;

        Route nearestRoute = null;

        if (!point.equals(originPoint)){

            if (isTriplePoint(mList, point)){

                point=originPoint;

            }

        }

        for (Route route:routes){

            Double initialDistance=point.distance(route.initialPoint);

            if(initialDistance<minDistance){

                minDistance = initialDistance;

                nearestRoute = route;

            }

            Double finalDistance=point.distance(route.finalPoint);

            if(finalDistance<minDistance){

                minDistance = finalDistance;

                nearestRoute = route;

            }

        }

        Double initialDistance=point.distance(nearestRoute.initialPoint);

        Double finalDistance=point.distance(nearestRoute.finalPoint);

        if (finalDistance<initialDistance){

            Collections.reverse(nearestRoute.structures);

            for (MStructure structure :nearestRoute.structures){

                structure.geometry.flip();

            }

        }

        return nearestRoute;

    }

    private void removeRepeatedStructures(List<Route>routes, MStructure structureToRemove){

        for (Route route:routes){

            int i=0;

            boolean removed=false;

            while (i< route.structures.size()&&!removed){

                if (route.structures.get(i).id==structureToRemove.id){

                    route.structures.remove(i);

                    removed=true;

                }

                i++;

            }

        }

    }

    private List <Route> createRoutes(List<MStructure> mList, Point origin) throws GeometryOperationNotSupportedException, GeometryOperationException{

        List <Route> routes=new ArrayList<Route>();

        for (MStructure mStructure:mList){

            Geometry geometry=mStructure.geometry;

            List<Line> lines=extractLines(geometry);

            for (Line initialLine:lines){

                if (!isAddedLine(routes,initialLine)){

                    Route route=new Route();

                    routes.add(route);

                    MStructure mStructureOrdered=mStructure.clone();

                    if (isFlippedLine(initialLine, origin)){

                        mStructureOrdered.geometry.flip();

                        route.initialPoint=initialLine.getVertex(initialLine.getNumVertices()-1);

                        route.finalPoint=initialLine.getVertex(0);

                    }else{

                        route.initialPoint=initialLine.getVertex(0);

                        route.finalPoint=initialLine.getVertex(initialLine.getNumVertices()-1);

                    }

                    route.structures.add(mStructureOrdered);

                    route.lines.add(initialLine);

                    Double initialPointDistance=route.initialPoint.distance(origin);

                    Double finalPointDistance=route.finalPoint.distance(origin);

                    int i=0;

                    boolean insertLowPriority=false;

                    while (i<mList.size() && !insertLowPriority){

                        if (i>=mList.size()){

                            insertLowPriority=true;

                            i=0;

                        }

                        boolean lineAdded=false;

                        MStructure mStructureAdded=mList.get(i);

                        Geometry geometryAdded=mStructureAdded.geometry;

                        List<Line> linesAdded=extractLines(geometryAdded);

                        for (Line addedLine:linesAdded){

                            if (!isAddedLine(routes,addedLine)){

                                MStructure mStructureAddedOrdered=mStructureAdded.clone();

                                Point initialPoint=addedLine.getVertex(0);

                                Point finalPoint=addedLine.getVertex(addedLine.getNumVertices()-1);

                                if ( route.initialPoint.equals(initialPoint) ){

                                    if (!isTriplePoint(mList,initialPoint)){

                                        Double distanceAddedPoint=origin.distance(finalPoint);

                                        boolean lowPriority=false;

                                        if (distanceAddedPoint>finalPointDistance){

                                            lowPriority=true;

                                        }

                                        if (!lowPriority||insertLowPriority){

                                            initialPointDistance=distanceAddedPoint;

                                            mStructureAddedOrdered.geometry.flip();

                                            route.initialPoint=finalPoint;

                                            route.structures.add(0, mStructureAddedOrdered);

                                            route.lines.add(addedLine);

                                            lineAdded=true;

                                        }

                                    }

                                }else if ( route.initialPoint.equals(finalPoint)  ) {

                                    if (!isTriplePoint(mList,finalPoint)){

                                        Double distanceAddedPoint=origin.distance(initialPoint);

                                        boolean lowPriority=false;

                                        if (distanceAddedPoint>initialPointDistance){

                                            lowPriority=true;

                                        }

                                        if (!lowPriority||insertLowPriority){

                                            initialPointDistance=distanceAddedPoint;

                                            route.initialPoint=initialPoint;

                                            route.structures.add(0, mStructureAddedOrdered);

                                            route.lines.add(addedLine);

                                            lineAdded=true;

                                        }

                                    }

                                }else if ( route.finalPoint.equals(initialPoint) ){

                                   if (!isTriplePoint(mList,finalPoint)){

                                        Double distanceAddedPoint=origin.distance(initialPoint);

                                        boolean lowPriority=false;

                                        if (distanceAddedPoint<initialPointDistance){

                                            lowPriority=true;

                                        }

                                        if (!lowPriority||insertLowPriority){

                                            finalPointDistance=distanceAddedPoint;

                                            route.finalPoint=finalPoint;

                                            route.structures.add(mStructureAddedOrdered);

                                            route.lines.add(addedLine);

                                            lineAdded=true;

                                        }

                                    }

                                }else if ( route.finalPoint.equals(finalPoint) ){

                                    if (!isTriplePoint(mList,finalPoint)){

                                        Double distanceAddedPoint=origin.distance(initialPoint);

                                        boolean lowPriority=false;

                                        if (distanceAddedPoint<finalPointDistance){

                                            lowPriority=true;

                                        }

                                        if (!lowPriority||insertLowPriority){

                                            finalPointDistance=distanceAddedPoint;

                                            mStructureAddedOrdered.geometry.flip();

                                            route.finalPoint=initialPoint;

                                            route.structures.add(mStructureAddedOrdered);

                                            route.lines.add(addedLine);

                                            lineAdded=true;

                                        }

                                    }

                                }

                            }

                        }

                        if (lineAdded){

                            i=0;

                        }else{

                            i++;

                        }

                    }

                }

            }

        }

        return routes;

    }

    private boolean isTriplePoint(List <MStructure> mList,Point point){

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

        for (MStructure structure:mList){

            points.addAll(extractPoints(structure.geometry));

        }

        int cont=0;

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

            if (points.get(i).equals(point)){

                cont++;

            }

            if (cont==3){

                return true;

            }

        }

        return false;

    }

    private Point extractFirstPoint(Geometry geometry){

        Point firstPoint=null;

        List<Line> lines= extractLines(geometry);

        if (lines!=null && !lines.isEmpty()){

            firstPoint=lines.get(0).getVertex(0);

        }

        return firstPoint;

    }

    private List<Point> extractPoints(Geometry geometry){

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

        List<Line> lines=extractLines(geometry);

        for (Line line: lines){

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

                points.add(line.getVertex(i));

            }

        }

        return points;

    }

    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;

    }

    private boolean isAddedLine(List<Route> routes,Line line){

        for (Route route:routes){

            if (route.lines.contains(line)){

                return true;

            }

        }

        return false;

    }

    private boolean isFlippedLine(Line line,Point origin) throws GeometryOperationNotSupportedException, GeometryOperationException{

        Point initialPoint=line.getVertex(0);

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

        Double distance1=origin.distance(initialPoint);

        Double distance2=origin.distance(finalPoint);

        if (distance1>distance2){

            return true;

        }else {

            return false;

        }

    }

//    private List<Point> getExtremePoints(List<MStructure> mList,Point origin){

//        List<Point> pointsInExtremes=new ArrayList<Point>();

//        for (MStructure mStructure: mList){

//            Geometry geometry=mStructure.geometry;

//            if (geometry instanceof Line){

//                Line line=(Line)geometry;

//                pointsInExtremes.add(line.getVertex(0));

//                pointsInExtremes.add(line.getVertex(line.getNumVertices()-1));

//            }

//            if (geometry instanceof MultiLine){

//                MultiLine multiline=(MultiLine)geometry;

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

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

//                    pointsInExtremes.add(line.getVertex(0));

//                    pointsInExtremes.add(line.getVertex(line.getNumVertices()-1));

//                }

//            }

//

//            PointToReferencePointComparator pointComparator= new PointToReferencePointComparator(origin);

//            Collections.sort(pointsInExtremes, pointComparator);

//

//            List<Point> orderedExtremePoints=new ArrayList<Point>();

//            while ( !pointsInExtremes.isEmpty() ){

//                Point extremePoint=pointsInExtremes.get(0);

//                if ( isLoopOrUnique(mList, extremePoint) ){

//                    orderedExtremePoints.add(extremePoint);

//                }

//                while (pointsInExtremes.contains(extremePoint)){

//                    pointsInExtremes.remove(extremePoint);

//                }

//            }

//        }

//

//        return orderedExtremePoints;

//    }

//    private boolean isLoopOrUnique(List<MStructure> mList, Point extremePoint){

//        boolean repeated=false;

//        boolean loop=false;

//

//        int i=0;

//        boolean firstAparition=false;

//        while( !repeated && !loop){

//            if (geometry instanceof Line){

//                Line line=(Line)geometry;

//                pointsInExtremes.add(line.getVertex(0));

//                pointsInExtremes.add(line.getVertex(line.getNumVertices()-1));

//            }

//            if (geometry instanceof MultiLine){

//                MultiLine multiline=(MultiLine)geometry;

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

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

//                    pointsInExtremes.add(line.getVertex(0));

//                    pointsInExtremes.add(line.getVertex(line.getNumVertices()-1));

//                }

//            }

//        }

//

//        return loop&&!repeated;

//    }

    private Geometry applyOffset(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;

    }

    private Map<Object, List<FeatureReference>> getGroupedReferences(

        FeatureSelection selection,

        final FeatureAttributeDescriptor idRouteField) throws BaseException {

        final Map<Object, List<FeatureReference>> refs =

            new HashMap<Object, List<FeatureReference>>();

        selection.accept(new Visitor() {

            public void visit(Object obj)

                throws VisitCanceledException, BaseException {

                Feature feature = (Feature) obj;

                Object id = feature.getFeature(idRouteField.getName());

                FeatureReference reference = feature.getReference();

                List<FeatureReference> references = refs.get(id);

                if (references == null) {

                    references = new ArrayList<FeatureReference>();

                }

                references.add(reference);

                refs.put(id, references);

            }

        });

        return refs;

    }

    /**

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

    }

    private Double getGeometryLength(Geometry geometry) throws GeometryOperationNotSupportedException, GeometryOperationException{

        return getGeometryLength(geometry, true);

    }

    private Double getGeometryLength(Geometry geometry,

        boolean ignoreSpatialGaps)

            throws GeometryOperationNotSupportedException,

            GeometryOperationException {

        if (geometry instanceof Line) {

            Line line = (Line) geometry;

            return getLineLength(line);

        }

        if (geometry instanceof MultiLine) {

            MultiLine multiLine = (MultiLine) geometry;

            return getMultiLineLength(multiLine, ignoreSpatialGaps);

        }

        return Double.NaN;

    }

    /**

     * @param multiLine

     * @return lenght

     * @throws GeometryOperationException

     * @throws GeometryOperationNotSupportedException

     */

    private double getMultiLineLength(MultiLine multiLine,

        boolean ignoreSpatialGaps)

            throws GeometryOperationNotSupportedException,

            GeometryOperationException {

        double lenght = 0;

        Point previousVertex = null;

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

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

            if (ignoreSpatialGaps) {

                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.");

        }

    }

    class MStructure {

        Geometry geometry;

        Double fromField;

        Double toField;

        int id;

        protected MStructure clone(){

            MStructure otherMStructure=new MStructure();

            otherMStructure.geometry=geometry.cloneGeometry();

            if (fromField==null){

                otherMStructure.fromField=null;

            }else{

                otherMStructure.fromField=new Double(fromField);

            }

            if (toField==null){

                otherMStructure.toField=null;

            }else{

                otherMStructure.toField=new Double(toField);

            }

            otherMStructure.id=id;

            return otherMStructure;

        }

    }

    class Route{

        public Route(){

            structures=new ArrayList<MStructure>();

            lines=new ArrayList<Line>();

        }

        List<MStructure> structures;

        Point initialPoint;

        Point finalPoint;

        List<Line> lines;

        Double distance;

    }

    class PointToReferencePointComparator implements Comparator<Point>{

        private Point referencePoint;

        public PointToReferencePointComparator(Point referencePoint) {

            this.referencePoint = referencePoint;

        }

        public int compare(Point point1, Point point2) {

            Double distance1;

            try {

                distance1 = point1.distance(referencePoint);

            } catch (Exception e) {

                distance1 = Double.MAX_VALUE;

            }

            Double distance2;

            try {

                distance2 = point2.distance(referencePoint);

            } catch (Exception e) {

                distance2 = Double.MAX_VALUE;

            }

            return distance1.compareTo(distance2);

        }

    }

//    class GeometryDistanceToPointComparator implements Comparator<MStructure> {

//

//        private Point referencePoint;

//

//        public GeometryDistanceToPointComparator(Point referencePoint) {

//            this.referencePoint = referencePoint;

//        }