Menu
▾
▴
[Geotools-commits] svn - r38851 - in trunk/modules/extension/graph/src: main/java/org/geotools/graph/build/feature main/java/org/geotools/graph/build/line test/java/org/geotools/graph/build test/java/org/geotools/graph/build/line
Author: jdeolive
Date: 2012-06-29 09:49:42 -0700 (Fri, 29 Jun 2012)
New Revision: 38851
Added:
trunk/modules/extension/graph/src/test/java/org/geotools/graph/build/line/
trunk/modules/extension/graph/src/test/java/org/geotools/graph/build/line/LineStringGraphGeneratorTest.java
Modified:
trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/feature/FeatureGraphGenerator.java
trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/BasicLineGraphGenerator.java
trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/LineStringGraphGenerator.java
Log:
GEOT-4164, added ability to build line graph with tolerance, patch submitted by Anders Bakkevold
Modified: trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/feature/FeatureGraphGenerator.java
===================================================================
--- trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/feature/FeatureGraphGenerator.java 2012-06-29 14:30:32 UTC (rev 38850)
+++ trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/feature/FeatureGraphGenerator.java 2012-06-29 16:49:42 UTC (rev 38851)
@@ -16,6 +16,7 @@
*/
package org.geotools.graph.build.feature;
+import com.vividsolutions.jts.geom.Geometry;
import org.geotools.graph.build.GraphBuilder;
import org.geotools.graph.build.GraphGenerator;
import org.geotools.graph.build.basic.BasicGraphGenerator;
@@ -30,10 +31,8 @@
* builds a graph from geometries.
* </p>
* @author Justin Deoliveira, The Open Planning Project, jde...@op...
+ * @author Anders Bakkevold, Bouvet AS, bak...@gm...
*
- *
- *
- *
* @source $URL$
*/
public class FeatureGraphGenerator extends BasicGraphGenerator {
@@ -58,8 +57,10 @@
public Graphable add( Object obj ) {
SimpleFeature feature = (SimpleFeature) obj;
Graphable g = decorated.add( feature.getDefaultGeometry() );
- g.setObject( feature );
-
+ Geometry geom = (Geometry) g.getObject();
+ //Preserve geometry from Graphable, as it may be changed.
+ feature.setDefaultGeometry(geom);
+ g.setObject( feature );
return g;
}
Modified: trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/BasicLineGraphGenerator.java
===================================================================
--- trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/BasicLineGraphGenerator.java 2012-06-29 14:30:32 UTC (rev 38850)
+++ trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/BasicLineGraphGenerator.java 2012-06-29 16:49:42 UTC (rev 38851)
@@ -17,8 +17,11 @@
package org.geotools.graph.build.line;
import java.util.HashMap;
+import java.util.List;
import java.util.Map;
+import com.vividsolutions.jts.index.bintree.Bintree;
+import com.vividsolutions.jts.index.bintree.Interval;
import org.geotools.graph.build.GraphBuilder;
import org.geotools.graph.build.GraphGenerator;
import org.geotools.graph.build.basic.BasicGraphBuilder;
@@ -39,6 +42,9 @@
* records the end coordinates of each line added, and maintains a map of
* coordinates to nodes, creating nodes when neccessary.<BR>
* <BR>
+ * If a tolerance distance is set, the end coordinates matched to nodes with
+ * a tolerance distance (using a spatial index). <BR>
+ * <BR>
* Edges created by the generator are of type BasicEdge and contain an object
* of type LineSegment.<BR>
* Nodes created by the generator are of type BasicXYNode and contain an object
@@ -50,28 +56,52 @@
* @see com.vividsolutions.jts.geom.Coordinate
*
* @author Justin Deoliveira, Refractions Research Inc, jde...@re...
+ * @author Anders Bakkevold, Bouvet AS, bak...@gm...
*
- *
- *
* @source $URL$
*/
public class BasicLineGraphGenerator implements LineGraphGenerator {
/** coordinate to node map **/
- private HashMap m_coord2node;
+ private HashMap<Coordinate,Node> m_coord2node;
/** underlying builder **/
private GraphBuilder m_builder;
-
+
+ /** tolerance distance **/
+ private double tolerance = 0.0;
+
+ /** used when tolerance is greater than 0.0 */
+ private Bintree spatialIndex;
+
/**
* Constructs a new BasicLineGraphGenerator.
+ * <p>
+ * Tolerance is 0.0 as default, meaning coordinates must be equal for lines to connect
+ * at a node.
+ * </p>
*/
public BasicLineGraphGenerator () {
- m_coord2node = new HashMap();
+ m_coord2node = new HashMap<Coordinate, Node>();
setGraphBuilder(new BasicGraphBuilder());
}
-
+
/**
+ * Constructs a new BasicLineGraphGenerator.
+ * <p>
+ * If two coordinates are considered equal (and should be snapped to the same Node),
+ * the distance between them must be less than the tolerance value.
+ * </p>
+ * @param tolerance threshold distance value for coordinates to be considered equal
+ */
+ public BasicLineGraphGenerator (double tolerance) {
+ this.tolerance = tolerance;
+ spatialIndex = new Bintree();
+ m_coord2node = new HashMap<Coordinate,Node>();
+ setGraphBuilder(new BasicGraphBuilder());
+ }
+
+ /**
* Adds a line to the graph.
*
* @param obj An instance of LineSegment.
@@ -83,48 +113,47 @@
*/
public Graphable add(Object obj) {
LineSegment line = (LineSegment)obj;
- Coordinate c;
+ Coordinate first,last;
Node n1, n2;
//check first coordinate
- c = line.p0;
- if ((n1 = (Node)m_coord2node.get(c)) == null) {
- //first time coordinate seen, create node for it
- n1 = getGraphBuilder().buildNode();
-
- //set underlying object to coordinate
- //n1.setObject(c);
- setObject(n1, c);
-
- getGraphBuilder().addNode(n1);
- m_coord2node.put(c,n1);
+ first = line.p0;
+ n1 = retrieveNode(first);
+ if (n1 == null) {
+ n1 = createNode(first);
}
-
+
//check second coordinate
- c = line.p1;
- if ((n2 = (Node)m_coord2node.get(c)) == null) {
- //first time coordinate seen, create node for it
- n2 = getGraphBuilder().buildNode();
-
- //set underlying object to coordiante
- //n2.setObject(c);
- setObject(n2,c);
-
- getGraphBuilder().addNode(n2);
- m_coord2node.put(c,n2);
+ last = line.p1;
+ n2 = retrieveNode(last);
+ if (n2 == null) {
+ n2 = createNode(last);
}
-
+
//build the edge setting underlying object to line
Edge e = getGraphBuilder().buildEdge(n1,n2);
- //e.setObject(line);
+
+ getGraphBuilder().addEdge(e);
+
+ if (useTolerance()) {
+ line = alterLine(line, n1, n2);
+ }
+
setObject(e, line);
-
- getGraphBuilder().addEdge(e);
-
+
//return the created edge
return(e);
}
+ protected LineSegment alterLine(LineSegment line, Node n1, Node n2) {
+ Coordinate c1added = ((Coordinate) n1.getObject());
+ Coordinate c2added = ((Coordinate) n2.getObject());
+ if (!c1added.equals2D(line.p0) || c2added.equals2D(line.p1)) {
+ return new LineSegment(c1added,c2added);
+ }
+ return line;
+ }
+
/**
* Returns the edge which represents a line. Note that if the exact same line
* has been added to the graph multiple times, then only one of the edges that
@@ -140,8 +169,8 @@
LineSegment line = (LineSegment)obj;
//get nodes representing coordinate
- Node n1 = (Node)m_coord2node.get(line.p0);
- Node n2 = (Node)m_coord2node.get(line.p1);
+ Node n1 = retrieveNode(line.p0);
+ Node n2 = retrieveNode(line.p1);
if (n1 == null || n2 == null) return(null);
@@ -161,12 +190,12 @@
*/
public Graphable remove(Object obj) {
LineSegment line = (LineSegment)obj;
- Node n1 = (Node)m_coord2node.get(line.p0);
- Node n2 = (Node)m_coord2node.get(line.p1);
+ Node n1 = retrieveNode(line.p0);
+ Node n2 = retrieveNode(line.p1);
if (n1 == null || n2 == null) return(null);
- Edge e = (Edge)n1.getEdge(n2);
+ Edge e = n1.getEdge(n2);
getGraphBuilder().removeEdge(e);
return(e);
@@ -197,7 +226,7 @@
* Returns the coordinate to node map used to build nodes representing line
* endpoint coordinates.
*
- * @return coordinate to ndoe map.
+ * @return coordinate to node map.
*/
public Map getNodeMap() {
return(m_coord2node);
@@ -205,12 +234,12 @@
//TODO COMMENT ME!
public Node getNode(Coordinate c) {
- return((Node)m_coord2node.get(c));
+ return retrieveNode(c);
}
public Edge getEdge(Coordinate c1, Coordinate c2) {
- Node n1 = (Node)m_coord2node.get(c1);
- Node n2 = (Node)m_coord2node.get(c2);
+ Node n1 = retrieveNode(c1);
+ Node n2 = retrieveNode(c2);
return(n1.getEdge(n2));
}
@@ -221,5 +250,47 @@
protected void setObject(Node n, Object obj) {
n.setObject(obj);
- }
+ }
+
+ private Node createNode(Coordinate c) {
+ Node node;
+ node = getGraphBuilder().buildNode();
+ setObject(node, c);
+ getGraphBuilder().addNode(node);
+ m_coord2node.put(c, node);
+ if (useTolerance()) {
+ spatialIndex.insert(new Interval(c.y, c.y), c);
+ }
+ return node;
+ }
+
+ private Node retrieveNode(Coordinate c) {
+ Node node = m_coord2node.get(c);
+ if (node == null && useTolerance()) {
+ node = findClosestNodeWithinTolerance(c);
+ }
+ return node;
+ }
+
+ protected boolean useTolerance() {
+ return tolerance > 0.0;
+ }
+
+ // spatial search with tolerance
+ private Node findClosestNodeWithinTolerance(Coordinate inCoord) {
+ double closestDistance = Double.MAX_VALUE;
+ Coordinate closestCoordinate = null;
+ List<Coordinate> list = spatialIndex.query(new Interval(inCoord.y - tolerance, inCoord.y + tolerance));
+ for (Coordinate c : list) {
+ double distance = inCoord.distance(c);
+ if (distance < closestDistance) {
+ closestDistance = distance;
+ closestCoordinate = c;
+ }
+ }
+ if (closestCoordinate != null && closestCoordinate.distance(inCoord) < tolerance) {
+ return m_coord2node.get(closestCoordinate);
+ }
+ return null;
+ }
}
Modified: trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/LineStringGraphGenerator.java
===================================================================
--- trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/LineStringGraphGenerator.java 2012-06-29 14:30:32 UTC (rev 38850)
+++ trunk/modules/extension/graph/src/main/java/org/geotools/graph/build/line/LineStringGraphGenerator.java 2012-06-29 16:49:42 UTC (rev 38851)
@@ -16,15 +16,14 @@
*/
package org.geotools.graph.build.line;
+import com.vividsolutions.jts.geom.*;
import org.geotools.graph.structure.Edge;
import org.geotools.graph.structure.Graphable;
import org.geotools.graph.structure.Node;
-import com.vividsolutions.jts.geom.Coordinate;
-import com.vividsolutions.jts.geom.GeometryFactory;
-import com.vividsolutions.jts.geom.LineSegment;
-import com.vividsolutions.jts.geom.LineString;
-import com.vividsolutions.jts.geom.MultiLineString;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
/**
* Builds a graph representing a line network in which edges in the network are
@@ -39,21 +38,29 @@
* @see com.vividsolutions.jts.geom.Point
*
* @author Justin Deoliveira, Refractions Research Inc, jde...@re...
+ * @author Anders Bakkevold, Bouvet AS, bak...@gm...
*
- *
- *
* @source $URL$
*/
public class LineStringGraphGenerator extends BasicLineGraphGenerator {
private static GeometryFactory gf = new GeometryFactory();
-
+
+ public LineStringGraphGenerator(double tolerance) {
+ super(tolerance);
+ }
+
+ public LineStringGraphGenerator() {
+ }
+
public Graphable add(Object obj) {
- LineString ls = null;
- if (obj instanceof MultiLineString)
- ls = (LineString) ((MultiLineString)obj).getGeometryN(0);
- else
- ls = (LineString)obj;
+ LineString ls = null;
+ if (obj instanceof MultiLineString) {
+ ls = (LineString) ((MultiLineString) obj).getGeometryN(0);
+ }
+ else {
+ ls = (LineString) obj;
+ }
//parent class expects a line segment
Edge e = (Edge)super.add(
@@ -61,12 +68,35 @@
ls.getCoordinateN(0), ls.getCoordinateN(ls.getNumPoints()-1)
)
);
-
+ //check if the LineSegment has been changed
+ if (useTolerance()) {
+ LineSegment lineSegment = (LineSegment) e.getObject();
+ Coordinate[] coordinates = ls.getCoordinates();
+ List<Coordinate> coordinateList = Arrays.asList(coordinates);
+ // list from asList does not support add(index,object), must make an arraylist
+ List<Coordinate> nCoordinateList = new ArrayList<Coordinate>(coordinateList);
+ if (!ls.getCoordinateN(0).equals(lineSegment.p0)) {
+ nCoordinateList.add(0, lineSegment.p0);
+ } else if (!ls.getCoordinateN(ls.getNumPoints()-1).equals(lineSegment.p1)){
+ nCoordinateList.add(lineSegment.p1);
+ }
+ Coordinate[] newCoordinates = nCoordinateList.toArray(new Coordinate[nCoordinateList.size()]);
+ ls = gf.createLineString(newCoordinates);
+ }
//over write object to be the linestring
e.setObject(ls);
return(e);
}
+ protected LineSegment alterLine(LineSegment line, Node n1, Node n2) {
+ Point c1added = ((Point) n1.getObject());
+ Point c2added = ((Point) n2.getObject());
+ if (!c1added.getCoordinate().equals(line.p0) || c2added.getCoordinate().equals(line.p1)) {
+ line = new LineSegment(c1added.getCoordinate(), c2added.getCoordinate());
+ }
+ return line;
+ }
+
public Graphable remove(Object obj) {
LineString ls = (LineString)obj;
@@ -93,133 +123,9 @@
);
}
-
protected void setObject(Node n, Object obj) {
//set underlying object to be point instead of coordinate
Coordinate c = (Coordinate)obj;
n.setObject(gf.createPoint(c));
}
-
-// /** underlying line graph generator **/
-// private LineGraphGenerator m_generator;
-//
-// /**
-// * Constructs a new LineStringGraphGenerator.
-// *
-// */
-// public LineStringGraphGenerator() {
-// this(new BasicLineGraphGenerator());
-// }
-//
-// /**
-// * Constructs a new LineStringGraphGenerator.
-// *
-// * @param generator Underlying generator.
-// */
-// public LineStringGraphGenerator(LineGraphGenerator generator) {
-// m_generator = generator;
-// }
-//
-// /**
-// * Adds a LineString object to the graph. An edge is created to represent the
-// * LineString and its underlying object is set to the LineString.
-// *
-// * @param obj A LineString.
-// *
-// * @see GraphGenerator#add(Object)
-// */
-// public Graphable add(Object obj) {
-// LineString line = (LineString)obj;
-// Coordinate[] c = line.getCoordinates();
-//
-// //instruct the underlying line graph generate and edge represented by
-// // the endpoints of the linestring, set the underlying object to be the
-// //linstring itself
-// Edge e = (Edge)m_generator.add(
-// new LineSegment(c[0], c[c.length-1])
-// );
-// e.setObject(line);
-//
-// //check nodes of edge, if not visited, set object to point
-// if (!e.getNodeA().isVisited()) {
-// e.getNodeA().setVisited(true);
-// e.getNodeA().setObject(line.getPointN(0));
-// }
-//
-// if (!e.getNodeB().isVisited()) {
-// e.getNodeB().setVisited(true);
-// e.getNodeB().setObject(line.getPointN(c.length-1));
-// }
-//
-// return(e);
-// }
-//
-// /**
-// * Returns the edge created to represent a LineString object.
-// *
-// * @param obj A LineString.
-// *
-// * @see GraphGenerator#get(Object)
-// */
-// public Graphable get(Object obj) {
-// LineString line = (LineString)obj;
-// Coordinate[] c = line.getCoordinates();
-//
-// Edge e = (Edge)m_generator.get(
-// new LineSegment(c[0], c[c.length-1])
-// );
-//
-// return(e);
-// }
-//
-// /**
-// * Removes an edge from the graph which represents a LineString object.
-// *
-// * @param A LineString.
-// *
-// * @see GraphGenerator#remove(Object)
-// */
-// public Graphable remove(Object obj) {
-// LineString line = (LineString)obj;
-// Coordinate[] c = line.getCoordinates();
-//
-// Edge e = (Edge)m_generator.remove(
-// new LineSegment(c[0], c[c.length-1])
-// );
-//
-// return(e);
-// }
-//
-// /**
-// * Sets the underlying builder of the underlying generator.
-// *
-// * @see GraphGenerator#setGraphBuilder(GraphBuilder)
-// */
-// public void setGraphBuilder(GraphBuilder builder) {
-// m_generator.setGraphBuilder(builder);
-// }
-//
-// /**
-// * Returns the underlying builder of the underlying generator.
-// *
-// * @see GraphGenerator#getGraphBuilder()
-// */
-// public GraphBuilder getGraphBuilder() {
-// return(m_generator.getGraphBuilder());
-// }
-//
-// /**
-// * @see GraphGenerator#getGraph()
-// */
-// public Graph getGraph() {
-// return(m_generator.getGraph());
-// }
-//
-// public Node getNode(Coordinate c) {
-// return(m_generator.getNode(c));
-// }
-//
-// public Edge getEdge(Coordinate c1, Coordinate c2) {
-// return(m_generator.getEdge(c1,c2));
-// }
}
Added: trunk/modules/extension/graph/src/test/java/org/geotools/graph/build/line/LineStringGraphGeneratorTest.java
===================================================================
--- trunk/modules/extension/graph/src/test/java/org/geotools/graph/build/line/LineStringGraphGeneratorTest.java (rev 0)
+++ trunk/modules/extension/graph/src/test/java/org/geotools/graph/build/line/LineStringGraphGeneratorTest.java 2012-06-29 16:49:42 UTC (rev 38851)
@@ -0,0 +1,80 @@
+/*
+ * GeoTools - The Open Source Java GIS Toolkit
+ * http://geotools.org
+ *
+ * (C) 2012, Open Source Geospatial Foundation (OSGeo)
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation;
+ * version 2.1 of the License.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ */
+package org.geotools.graph.build.line;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import com.vividsolutions.jts.geom.Point;
+import junit.framework.TestCase;
+
+import org.geotools.graph.structure.Graph;
+import org.geotools.graph.structure.basic.BasicNode;
+
+import com.vividsolutions.jts.geom.Coordinate;
+import com.vividsolutions.jts.geom.GeometryFactory;
+import com.vividsolutions.jts.geom.LineString;
+
+/**
+ * @author Anders Bakkevold, Bouvet AS, bak...@gm...
+ */
+public class LineStringGraphGeneratorTest extends TestCase {
+
+ private Coordinate c1, c2, c3, c4, c6, c7;
+
+ private GeometryFactory gf;
+
+ private LineStringGraphGenerator gen;
+
+ public void setUp() throws Exception {
+ c1 = new Coordinate(1, 1);
+ c2 = new Coordinate(2, 2);
+ c3 = new Coordinate(3, 3);
+ c4 = new Coordinate(4, 4);
+ c6 = new Coordinate(2.01, 2.0007); // within tolerance (0.02) of c2
+ c7 = new Coordinate(2.0, 1.75); // outsite tolerance (0.02) of c2
+
+ gf = new GeometryFactory();
+ gen = new LineStringGraphGenerator(0.2);
+ }
+
+ public void testThatCoordinatesNearbySnapToSameNode() {
+ LineString lineString = gf.createLineString(new Coordinate[] { c1, c2 });
+ LineString lineString2 = gf.createLineString(new Coordinate[] { c6, c3 });
+ LineString lineString3 = gf.createLineString(new Coordinate[] { c7, c4 });
+ gen.add(lineString);
+ gen.add(lineString2);
+ gen.add(lineString3);
+
+ Graph graph = gen.getGraph();
+ Collection graphNodes = graph.getNodes();
+ assertEquals(5, graphNodes.size());
+ Collection<Coordinate> graphNodeCoordinates = getCoordinates(graphNodes);
+ assertTrue(graphNodeCoordinates.contains(c2));
+ assertFalse("c6 should be snapped to c2", graphNodeCoordinates.contains(c6));
+ assertTrue("c7 should not have been snapped to c2 - distance bigger than tolerance", graphNodeCoordinates.contains(c7)); //
+ assertEquals(3, graph.getEdges().size());
+ }
+
+ private Collection<Coordinate> getCoordinates(Collection<BasicNode> graphNodes) {
+ Collection<Coordinate> coordinates = new ArrayList<Coordinate>();
+ for (BasicNode node : graphNodes) {
+ coordinates.add(((Point) node.getObject()).getCoordinate());
+ }
+ return coordinates;
+ }
+}
|
