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
