There is also a seperate builder that builds a graph based on the line
segmenets; perhaps you could combine the two ideas in your own graph builder
and contribute the result back/
Jody
On 16/06/2010, at 8:08 PM, Oleg Demchenko wrote:
> Hi Dear All.
>
> I'm quite new in Geotools area and hope somebody of you will point me a
> proper direction.
>
> I'm developing a server side Java method which should estimate shortest
> vehicle path between any 2 points placed within 1 country.
>
> Data is given from a Denmark OSM highway shapefile downloaded from public
> CloudsMade server. In order to optimize process I'm selecting from database
> features (lines) placed within a rectangle between start and end points.
> Usually it is 1500- 10 000 of LineString objects.
>
> From geotools-gt2-users mail archive I've learnt that lines MUST be
> intersected each other otherwise DijkstraShortestPathFinder will not return
> any path between given source and destination nodes for a Directed graph
> built from a lines array.
> There is mailing initiated by Cris
> (http://www.mail-archive.com/geotools-gt2-users@lists.sourceforge.net/msg04520.html)
> regarding splitlines function. I'm using last function version published by
> Cris Jan 2008 (please find it at the end of the mail), but after days of
> debug found it over optimized.
>
> Usually it is only double number of lines from input Vector<LineString>. For
> 1500 lines it built less then 3000 of intersected lines. As an Impact
> DijkstraShortestPathFinder can't find a path for the most source/destination
> points distanced more then 40 Kms each other, because Graph is not well
> connected.
>
> Could somebody point me, please, on the source where I could find good
> intersection method for Vector<LineString> using Quadtree?
>
> How I can check that Graph is well partitioned and most of nodes are
> connected each other?
>
> Thank you in advance for your reply.
>
>
> I'm split lines with a following function:
>
>
> private Vector<LineString> splitLines(Vector<LineString> lines) {
> Quadtree index = new Quadtree();
> // Fill Spatial Index
> for (int i = 0; i < lines.size(); ++i) {
> LineString l = (LineString) lines.get(i);
> index.insert(l.getEnvelopeInternal(), l);
> }
> int imax = lines.size();
> System.out.println("Added " + String.valueOf(imax) + " new lines");
> for (int i = 0; i < imax; ++i) {
> LineString l1 = (LineString) lines.get(i);
> Vector<LineString> l1_sub = new Vector<LineString>();
> List close = index.query(l1.getEnvelopeInternal());
> for (int j = 0; j < close.size(); ++j) {
> LineString l2 = (LineString) close.get(j);
> Geometry gc = l1.intersection(l2);
> if (gc.getNumGeometries() > 0) {
> // Intersection
> try {
> Point p = (Point) gc.getGeometryN(0);
> if (l2.getStartPoint() != p && l2.getEndPoint() != p)
> {
> Coordinate[] c = new
> Coordinate[]{(l2.getStartPoint()).getCoordinate(), p.getCoordinate()};
> LineString l2a = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> c = new Coordinate[]{p.getCoordinate(),
> (l2.getEndPoint()).getCoordinate()};
> LineString l2b = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> // Update spatial index
> index.remove(l2.getEnvelopeInternal(), l2);
> index.insert(l2a.getEnvelopeInternal(), l2a);
> index.insert(l2b.getEnvelopeInternal(), l2b);
> }
> if (l1.getStartPoint() != p && l1.getEndPoint() != p)
> {
> if (l1_sub.size() == 0) {
> Coordinate[] c = new
> Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
> LineString l1a = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> l1_sub.add(l1a);
> c = new Coordinate[]{p.getCoordinate(),
> (l1.getEndPoint()).getCoordinate()};
> LineString l1b = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> l1_sub.add(l1b);
> } else {
> int k = 0;
> LineString l1part;
> do {
> l1part = (LineString) l1_sub.get(k);
> if
> (l1.intersection(l2).getNumGeometries()
> > 0) {
> break;
> }
> ++k;
> }while (k < l1_sub.size());
> l1_sub.remove(l1part);
> Coordinate[] c = new
> Coordinate[]{(l1part.getStartPoint()).getCoordinate(), p.getCoordinate()};
> LineString l1a = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> l1_sub.add(l1a);
> c = new Coordinate[]{p.getCoordinate(),
> (l1part.getEndPoint()).getCoordinate()};
> LineString l1b = new LineString(new
> CoordinateArraySequence(c), new GeometryFactory());
> l1_sub.add(l1b);
> }
> }
> } catch (Exception e) {
> }
> }
> }
> // Update l1 in spatial index
> index.remove(l1.getEnvelopeInternal(), l1);
> for(int k=0; k<l1_sub.size(); ++k) {
> LineString l = (LineString)l1_sub.get(k);
> index.insert(l.getEnvelopeInternal(), l);
> }
> }
> return new Vector<LineString>(index.queryAll());
> }
>
> --
> All the best
> Oleg Demchenko
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit. See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo_______________________________________________
> Geotools-gt2-users mailing list
> Geotools-gt2-users@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
------------------------------------------------------------------------------
ThinkGeek and WIRED's GeekDad team up for the Ultimate
GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
lucky parental unit. See the prize list and enter to win:
http://p.sf.net/sfu/thinkgeek-promo
_______________________________________________
Geotools-gt2-users mailing list
Geotools-gt2-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
