After displaying the itineraries on a map (Google maps), I noticed that
Dijkstra returned strange results sometimes. It would not take a shorter
path for no apparent reason. Hence, I decided to have a look at the
splitting function again to see if I could find a problem.
I did find one, a test was bad near the end of the function. I fixed it and
now the graph is lighter (5 MB instead of 10 MB when serialized). However,
dijstra can't seem to find itineraries anymore (just returns null).
I'm pretty sure that my patch is Ok, hence the problem must be somewhere
else in the function but I can find where.
Regards,
Chris.
On Jan 12, 2008 1:42 AM, Chris <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I managed to optimize the code so that the work is done in approximately 2
> minutes now. This is a great progress.
>
> Other good news is that now Dijkstra does not return null anymore, which
> means that my graph is well connected.
>
> Could you look if there is any way to do it faster? 2 minutes is still
> pretty long and I think I'll have to find a way to save the resulting graph
> to a file and reload it when needed if it can't be done faster.
>
> Anyway, you were right, the Spatial index does allow to gain a lot of
> time. Thanks a lot.
>
> Regards,
> Chris.
>
>
> On Jan 12, 2008 12:32 AM, Chris < [EMAIL PROTECTED]> wrote:
>
> > First of all, thanks a lot for your help. I improved my function using a
> > spatial index (Quadtree). My function seems to be working but I would
> > greatly appreciate if you could have a look and see if I'm doing it right
> > and if it is still possible to optimize it.
> >
> > It has been running for 10 minutes already and it is only the second
> > loop iteration, I get this output:
> > Added 2146 new lines
> > Added 9532 new lines
> >
> > Apparently, there are only 2146 LineStrings in my shapefile, this does
> > not look like much (Is it?). I will let the program run a little to see how
> > it goes.
> >
> > Best regards,
> > Chris.
> >
> >
> > On Jan 11, 2008 11:12 PM, Justin Deoliveira < [EMAIL PROTECTED]>
> > wrote:
> >
> > > Chris wrote:
> > > > I added some debug, and apparently, the LineString intersection is
> > > not
> > > > due to my algorithm. It happens approximately 12 times in the first
> > > loop
> > > > iteration, then it does not happen anymore. This was probably due to
> > > my
> > > > shapefile.
> > > >
> > > > So I chose to ignore the LineString intersections and now my
> > > algorithm
> > > > has been running for approximately half an hour and it is the fourth
> > > > iteration of the while loop (still unfinished). I added some debug
> > > to
> > > > see how many LineStrings were created for each iteration:
> > > > Added 2200 new lines
> > > > Added 7666 new lines
> > > > Added 26234 new lines
> > > >
> > > > Is my algorithm ok? Is it normal it is taking so long? Is there any
> > > way
> > > > I can optimize this? If not, I guess I need to save the result
> > > somewhere
> > > > in a file and work from the result from now on because it is taking
> > > too
> > > > much time.
> > >
> > > Intersection is quite an expensive operation. I am not surprised it is
> > >
> > > taking this long with any non-trivial amount of data. Luckily there
> > > are
> > > some easy ways to optimize this. The best way to be to use a spatial
> > > index instead of looping through every line string and doing an
> > > intersection. So the the first step of your algorithm will be to
> > > populate the index with all of your lines. Its pretty easy to use:
> > >
> > > SpatialIndex index = ...;
> > > for ( LineString l : lines ) {
> > > index.insert( l.getEnvelopInternal(), l );
> > > }
> > >
> > > Then you can replace the second loop with a lookup in the index.
> > >
> > > //current line being processed
> > > LineString l = ...;
> > >
> > > //do a looup in the index
> > > List close = index.query( l.getEnvelopeInternal() );
> > >
> > > //do intersection on close lines
> > > for ( LineString c : close ) {
> > > l.intersect( c );
> > > }
> > >
> > > .. etc..
> > >
> > >
> > > This will greatly reduce the number of intersections you have to do
> > > and
> > > you should see a pretty drastic performance improvement. There are two
> > > implementations of com.vividsolutions.jts.index.SpatialIndex: STRTree
> > > and QuadTree. The STRTree will give you best performance but it is
> > > static, which means you cant update over the stage of your algorithm
> > > which you will probably want to do with the new lines that are
> > > produced.
> > > So you will probably have to just use a the QuadTree implementation.
> > > Either one should suffice in this case.
> > >
> > > Try that and let me know how it works.
> > >
> > > -Justin
> > >
> > > >
> > > > Regards,
> > > > Chris.
> > > >
> > > > On Jan 11, 2008 9:28 PM, Chris <[EMAIL PROTECTED]
> > > > <mailto:[EMAIL PROTECTED] >> wrote:
> > > >
> > > > I tried to use another Vector as you advised. This way, the size
> > > the
> > > > the lines Vector is not changing while iterating on it. I'm
> > > joining
> > > > the new code to this mail.
> > > >
> > > > It is taking quite some time (2-3 minutes) but this time I got
> > > an
> > > > exception:
> > > > java.lang.ClassCastException:
> > > com.vividsolutions.jts.geom.LineString
> > > > cannot be cast to com.vividsolutions.jts.geom.Point
> > > >
> > > > at this line:
> > > > Point p = (Point) gc.getGeometryN(0);
> > > >
> > > > where gc is the intersection between the two lines. Apparently,
> > > the
> > > > intersection between two LineStrings can be a LineString. I
> > > guess
> > > > this means that the two lines are identical? How could this
> > > happen?
> > > > Is my algorithm still wrong? or maybe I should just ignore when
> > > this
> > > > case happens?
> > > >
> > > > Regards,
> > > > Chris.
> > > >
> > > >
> > > > On Jan 11, 2008 7:28 PM, Justin Deoliveira <
> > > [EMAIL PROTECTED]
> > > > <mailto: [EMAIL PROTECTED]>> wrote:
> > > >
> > > > Hi Chris,
> > > >
> > > > I would have to mock up some data and test it but I dont
> > > think the
> > > > problem is the method but in the management of the data
> > > > structure. The
> > > > code is modifying the same list it is iterating over...
> > > which is
> > > > generally not a great idea.
> > > >
> > > > I recommend restructuring the algorithm so that when two new
> > >
> > > > lines are
> > > > created they are added to a separate list. When the outer
> > > loop
> > > > termines
> > > > add the new lines to the original list and repeat the
> > > algorithm
> > > > terminating when there are no more new lines.
> > > >
> > > > Hope that helps. I could be wrong as i said since i have not
> > > run the
> > > > code. If you find you continue to have the same problem let
> > > us
> > > > know .
> > > >
> > > > -Justin
> > > >
> > > > Chris wrote:
> > > > > Hi,
> > > > >
> > > > > After loading a shapefile (ESRI), I created a graph using
> > > a
> > > > > DirectedLineStringGraphGenerator. The creation went fine
> > > but
> > > > when using
> > > > > a DijkstraShortestPathFinder.getPath() on it, I noticed
> > > that
> > > > there was a
> > > > > problem because it returned null. Apparently, the
> > > linestring graph
> > > > > generator does not take internal intersections of
> > > > > lines into account when building the graph. Hence, I
> > > decided
> > > > to code a
> > > > > routine to split the LineStrings at their intersection as
> > > > advised there:
> > > > >
> > > >
> > > > http://www.nabble.com/Re%3A-LineString-Graph-Traversal-p1489791.html
> > >
> > > > <
> > > http://www.nabble.com/Re%3A-LineString-Graph-Traversal-p1489791.html>
> > > > >
> > > > > The problem is that My routine is taking "forever" to do
> > > the
> > > > splitting.
> > > > > Either, I'm doing it wrong or it is not optimized enough.
> > > > After waiting
> > > > > for 10 minutes, it is still not finished (although, the
> > > > shapefile is not
> > > > > that big). Could someone have a look at my function and
> > > see
> > > > what the
> > > > > problem is?
> > > > >
> > > > > Thanks in advance,
> > > > >
> > > > > Best regards,
> > > > > Chris.
> > > > >
> > > > >
> > > > >
> > > > >
> > > >
> > > ------------------------------------------------------------------------
> > > > >
> > > > >
> > > >
> > > -------------------------------------------------------------------------
> > > > > Check out the new SourceForge.net Marketplace.
> > > > > It's the best place to buy or sell services for
> > > > > just about anything Open Source.
> > > > >
> > > >
> > > http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
> > > > >
> > > > > !DSPAM:4007,4787a0db264908992556831!
> > > > >
> > > > >
> > > > >
> > > >
> > > ------------------------------------------------------------------------
> > > >
> > > > >
> > > > > _______________________________________________
> > > > > Geotools-gt2-users mailing list
> > > > > [email protected]
> > > > <mailto: [email protected]>
> > > > >
> > > > https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
> > >
> > > > >
> > > > >
> > > > > !DSPAM:4007,4787a0db264908992556831!
> > > >
> > > >
> > > > --
> > > > Justin Deoliveira
> > > > The Open Planning Project
> > > > http://topp.openplans.org
> > > >
> > > >
> > > >
> > > > !DSPAM:4007,4787dd5553261439371379!
> > >
> > >
> > > --
> > > Justin Deoliveira
> > > The Open Planning Project
> > > http://topp.openplans.org
> > >
> >
> >
>
private static 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);
}
// Detect intersection and cut the lines
Vector<LineString> l1_sub = new Vector<LineString>();
int imax = lines.size();
for (int i = 0; i < imax; ++i) {
LineString l1 = (LineString) lines.get(i);
List close_lines = index.query(l1.getEnvelopeInternal());
for (int j = 0; j < close_lines.size(); ++j) {
LineString l2 = (LineString) close_lines.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_sub.size() == 0) {
if (l1.getStartPoint() != p && l1.getEndPoint() !=
p) {
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 {
// l1 was already cut out
int k = 0;
while (k < l1_sub.size() && !((LineString)
l1_sub.get(k)).intersects(l2)) {
++k;
}
LineString l1part = (LineString) l1_sub.get(k);
if (l1part.getStartPoint() != p &&
l1part.getEndPoint() != p) {
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) {
System.out.print(e.getMessage());
}
}
}
// 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);
}
l1_sub.clear();
}
return new Vector<LineString>(index.queryAll());
}
-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
Geotools-gt2-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
