Building a connected graph with OSM data / Splitting LineStrings at their intersections

[Sicky]

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

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
2nd problem is that the path looks very strange:
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
Code for the polygon stuff:
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/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

EDIT: I'm using the Geotools 2.6-SNAPSHOT from the 10th of June!

[Sicky]

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

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

Help would be greatly appreciated!

[mbedward]

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

------------------------------------------------------------------------------
Crystal Reports - New Free Runtime and 30 Day Trial
Check out the new simplified licensing option that enables unlimited
royalty-free distribution of the report engine for externally facing
server and web deployment.
http://p.sf.net/sfu/businessobjects
_______________________________________________
Geotools-gt2-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users

[Sicky]

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<LineString> splitMLines(Vector<MultiLineString> mlines) {
    GeometryFactory geomFactory = new GeometryFactory();
    List<LineString> lines = new Vector<LineString>();
   
        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?

[mbedward]

Hi Christian,

I might not understand your data properly, but I think you want to do
something more like this...

    private List<LineString> splitMLines(ArrayList<MultiLineString> mlines) {
        GeometryFactory geomFactory = new GeometryFactory();
        List<LineString> lines = new ArrayList<LineString>();

        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

------------------------------------------------------------------------------
Are you an open source citizen? Join us for the Open Source Bridge conference!
Portland, OR, June 17-19. Two days of sessions, one day of unconference: $250.
Need another reason to go? 24-hour hacker lounge. Register today!
http://ad.doubleclick.net/clk;215844324;13503038;v?http://opensourcebridge.org
_______________________________________________
Geotools-gt2-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users

[Sicky]

mbedward wrote:

I might not understand your data properly, but I think you want to do
something more like this...

    private List<LineString> splitMLines(ArrayList<MultiLineString> mlines) {
        GeometryFactory geomFactory = new GeometryFactory();
        List<LineString> lines = new ArrayList<LineString>();

        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.

[mbedward]

No worries Christian.  Always nice to hear the sound of a satisfied customer :-)

Michael

------------------------------------------------------------------------------
Are you an open source citizen? Join us for the Open Source Bridge conference!
Portland, OR, June 17-19. Two days of sessions, one day of unconference: $250.
Need another reason to go? 24-hour hacker lounge. Register today!
http://ad.doubleclick.net/clk;215844324;13503038;v?http://opensourcebridge.org
_______________________________________________
Geotools-gt2-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users