## geotools-gt2-users

 [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Sicky - 2009-06-16 14:45:20 ```Hi! As you might see I'm a new user and hope everything goes well with my registration/posting here. I've been digging myself into the GeoTools framework for the past weeks but now can't get any more help on my subject on this list or with google. Here's what I have done so far: 1) put some shapes (railroad network, road network and rivers) with osm data (downloaded from geofabrik) into a postgis database 2) displayed the data with geotools 3) build a graph using the LineStringGraphGenerator and just the railroad network data 4) select two points on the map which are on the graph 5) use Dijkstra to find the shortest way between these points. The problem is point 3) I saw that the graph generated is not well connected and checked this with the GraphPartitioner which had approx. 167 partitions while the dataset (railroad network) hast just 531 entries. At that point I informed myself here and got to know that I have to make a point/node whenever 2 lines crosses and make 4 lines from them (or 3 in a special case) Then I saw 2 possible solutions for this here: 1) Use a PolygonGraphGenerator to get the intersection. 2) Split the linestrings in a seperate method and still build the graph with the LineStringGraphGenerator (code taken from here: http://n2.nabble.com/Splitting-LineStrings-at-their-intersection-td1941502.html http://n2.nabble.com/Splitting-LineStrings-at-their-intersection-td1941502.html ) I tried both and run into the following problems: 1) Graph seems to be way to small, resulting graph is: V=[14, 19, 5, 7, 8, 12, 2, 4, 13, 0, 23, 16, 22, 1, 10, 26, 24, 17, 20] E=[3 (2,1), 21 (20,13), 6 (5,1), 9 (8,1), 15 (14,1), 18 (17,1), 25 (24,1), 11 (10,1)] whenever I want to route I get: Shortest path: null 2) I see 2 problems here, first that it doesn't allways find a path, like in this picture/case: http://sicky.i-networx.de/temp/no_shortest_path.png http://sicky.i-networx.de/temp/no_shortest_path.png 2nd problem is that the path looks very strange: http://sicky.i-networx.de/temp/strange_behavior.png http://sicky.i-networx.de/temp/strange_behavior.png The discussion in the topic I mentioned above unde 2) ended apruptly so I don't have a real solution. So, to take this to and end my questions: 1. What's wrong with the code and/or 2. is there an easy way to route with osm data when you use geotools. Here's all you need to understand my problems: Code for the implementation with the splitting of lines: http://sicky.i-networx.de/temp/TestGUI.java http://sicky.i-networx.de/temp/TestGUI.java Code for the polygon stuff: http://sicky.i-networx.de/temp/TestGUI2.java http://sicky.i-networx.de/temp/TestGUI2.java additional needed classes: http://sicky.i-networx.de/temp/DijkstraShortestPath.java http://sicky.i-networx.de/temp/DijkstraShortestPath.java http://sicky.i-networx.de/temp/SelectionTool.java http://sicky.i-networx.de/temp/SelectionTool.java postgis database dump: http://sicky.i-networx.de/temp/imotris_os.backup I hope that was all and my problems are understandable. If there's something missing or if there are any questions, just drop me a line. Thanks in advance for your help :-) -- View this message in context: http://n2.nabble.com/Building-a-connected-graph-with-OSM-data---Splitting-LineStrings-at-their-intersections-tp3086758p3086758.html Sent from the geotools-gt2-users mailing list archive at Nabble.com. ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Sicky - 2009-06-18 14:06:49 ```There must be something wrong with the algorithm that splits the lines, but I don't know what, because when I display the splitted lines on the maps, it looks like this: http://sicky.i-networx.de/temp/splitlines_vis.png http://sicky.i-networx.de/temp/splitlines_vis.png As you can see all the lines are not on top of the black lines (the railroads) where they should be on... but that's not the only problem, the graph seems to be not that well connected, because it has 50 partitions. When I display every partition of the graph on the map with another color you can see that very well: http://sicky.i-networx.de/temp/graph_vis.png http://sicky.i-networx.de/temp/graph_vis.png Help would be greatly appreciated! :-) -- View this message in context: http://n2.nabble.com/Building-a-connected-graph-with-OSM-data---Splitting-LineStrings-at-their-intersections-tp3086758p3113464.html Sent from the geotools-gt2-users mailing list archive at Nabble.com. ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Michael Bedward - 2009-06-19 14:08:21 ```Hello > 2) Split the linestrings in a seperate method and still build the graph with > the LineStringGraphGenerator (code taken from here: > http://n2.nabble.com/Splitting-LineStrings-at-their-intersection-td1941502.html > http://n2.nabble.com/Splitting-LineStrings-at-their-intersection-td1941502.html I'm not sure if this is relevant to your problem (I haven't used the graph code in geotools) but to split your LineStrings at intersections you could try the following JTS trick (courtesy of Martin Davis's presentation at 2007 FOSS4G conference Collection lines = ... // your line strings Geometry mls = geomFactory.buildGeometry(lines); // create a MultiLineString Point mlsPt = geomFactory.createPoint(mls.getCoordinate()); // get an arbitrary point on a line Geometry nodedLines = mls.union(pt); // union the MultiLineString with the point This has the (almost magical) effect of noding all of the line intersections. Hope this helps Michael ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Sicky - 2009-06-22 08:50:10 ``` mbedward wrote: > > I'm not sure if this is relevant to your problem (I haven't used the > graph code in geotools) but to split your LineStrings at intersections > you could try the following JTS trick (courtesy of Martin Davis's > presentation at 2007 FOSS4G conference > > Collection lines = ... // your line strings > Geometry mls = geomFactory.buildGeometry(lines); // create a > MultiLineString > Point mlsPt = geomFactory.createPoint(mls.getCoordinate()); // get an > arbitrary point on a line > Geometry nodedLines = mls.union(pt); // union the MultiLineString > with the point > > This has the (almost magical) effect of noding all of the line > intersections. > Thanks Michael! Here's the method I built out of your reply: private List splitMLines(Vector mlines) { GeometryFactory geomFactory = new GeometryFactory(); List lines = new Vector(); int imax = mlines.size(); for (int i = 0; i < imax; ++i) { MultiLineString mls = mlines.get(i); for (int j = 0;j <= mls.getNumGeometries()-1;j++) { // get an arbitrary point on a line Point mlsPt = geomFactory.createPoint(mls.getCoordinate()); // union the MultiLineString with the point Geometry nodedLines = mls.union(mlsPt); if (nodedLines instanceof MultiLineString) { for (int z = 0;z <= mls.getNumGeometries()-1;z++) { LineString ls = (LineString) mls.getGeometryN(z); lines.add(ls); } } else if (nodedLines instanceof LineString){ lines.add((LineString) nodedLines); } else System.out.println("Error! Type is: " + nodedLines.getGeometryType()); } } return lines; } But it gives me 167 partitions and that way the graph that is not well connected. Did I do something wrong? -- View this message in context: http://n2.nabble.com/Building-a-connected-graph-with-OSM-data---Splitting-LineStrings-at-their-intersections-tp3086758p3131785.html Sent from the geotools-gt2-users mailing list archive at Nabble.com. ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Michael Bedward - 2009-06-22 10:29:16 ```Hi Christian, I might not understand your data properly, but I think you want to do something more like this... private List splitMLines(ArrayList mlines) { GeometryFactory geomFactory = new GeometryFactory(); List lines = new ArrayList(); for (MultiLineString mls : mlines) { for (int i = 0; i < mls.getNumGeometries(); i++) { lines.add((LineString)mls.getGeometryN(i)); } } Geometry grandMls = geomFactory.buildGeometry(lines); Point mlsPt = geomFactory.createPoint(grandMls.getCoordinate()); Geometry nodedLines = grandMls.union(mlsPt); lines.clear(); for (int i = 0, n = nodedLines.getNumGeometries(); i < n; i++) { Geometry g = nodedLines.getGeometryN(i); if (g instanceof LineString) { lines.add((LineString)g); } } return lines; } Let us know what happens :) Michael ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Sicky - 2009-06-22 11:49:03 ``` mbedward wrote: > > I might not understand your data properly, but I think you want to do > something more like this... > > private List splitMLines(ArrayList > mlines) { > GeometryFactory geomFactory = new GeometryFactory(); > List lines = new ArrayList(); > > for (MultiLineString mls : mlines) { > for (int i = 0; i < mls.getNumGeometries(); i++) { > lines.add((LineString)mls.getGeometryN(i)); > } > } > > Geometry grandMls = geomFactory.buildGeometry(lines); > Point mlsPt = geomFactory.createPoint(grandMls.getCoordinate()); > Geometry nodedLines = grandMls.union(mlsPt); > > lines.clear(); > > for (int i = 0, n = nodedLines.getNumGeometries(); i < n; i++) { > Geometry g = nodedLines.getGeometryN(i); > if (g instanceof LineString) { > lines.add((LineString)g); > } > } > > return lines; > } > Thank you very much, I knew I was missing something fundamental. Your code does an awesome job so far. It's very fast, too. Really great stuff I think. If I ran into further problems, I'll get back to this topic. Thanks again, Christian. -- View this message in context: http://n2.nabble.com/Building-a-connected-graph-with-OSM-data---Splitting-LineStrings-at-their-intersections-tp3086758p3132467.html Sent from the geotools-gt2-users mailing list archive at Nabble.com. ```
 Re: [Geotools-gt2-users] Building a connected graph with OSM data / Splitting LineStrings at their intersections From: Michael Bedward - 2009-06-23 03:14:55 ```No worries Christian. Always nice to hear the sound of a satisfied customer :-) Michael ```