Could you tell me what is wrong with this part of code?
Coordinate[] c = new Coordinate[]{(l1.getStartPoint()).getCoordinate(),
p.getCoordinate()};
LineString l1a = new LineString(new CoordinateArraySequence(c), new
GeometryFactory());
l1_sub.add(l1a);
if(!l1.covers(l1a))
System.out.println("Error: a");
It displays "Error: a". Because of this, it happens that none of the
subparts of l1 intersects with l2 :(
Regards,
Chris.
On Jan 15, 2008 1:09 AM, Chris <[EMAIL PROTECTED]> wrote:
> Trying to see what's wrong with my graph, I decided to print some
> information. The node I chose to start from is supposed to have 3 edges
> (which is true, so far so good). However, I displayed the coordinates of the
> nodes:
> Origine node:
> x: 6.844562915500704, y: 47.641801629239914
>
> Nodes of the three connected edges:
> 6.84316081570757,47.645540708210135
> 6.844562915500704,47.641801629239914
> ___
> 6.844562915500704,47.641801629239914
> 6.844562915500704,47.641801629239914
> ___
> 6.844562915500704,47.641801629239914
> 6.844562915500704,47.641801629239914
>
> Two of the edges have the same NodeA and NodeB (which is the origin
> node)... One of the edges looks good though.
>
> Regards,
> Chris.
>
>
> On Jan 14, 2008 11:38 PM, Chris <[EMAIL PROTECTED]> wrote:
>
> > I simplified my function. That is to say, when I detect an intersection
> > between l1 and l2, I only split l2. I think that anyway, at some point, the
> > function will detect an intersection between l2 and l1, splitting l1.
> >
> > My LineString vector size is now 2.2M, when serialized. The problem is
> > that Dijkstra is still unable to find a path from a node to another. I think
> > that something must be wrong with my method. or maybe my graph creation? My
> > graph creation is pretty simple though:
> >
> > // Load the shapefile and make a graph
> > file = new File(shapefile);
> > try {
> > URL shapeURL = file.toURL();
> > ShapefileDataStore dataStore = new
> > ShapefileDataStore(shapeURL);
> > String[] typeNames = dataStore.getTypeNames();
> > String typeName = typeNames[0];
> > FeatureSource fs = dataStore.getFeatureSource(typeName);
> > FeatureResults fr = fs.getFeatures();
> > FeatureCollection fc = fr.collection();
> > Iterator featureIterator = fc.iterator();
> > while (featureIterator.hasNext()) {
> > Feature feature = (Feature) featureIterator.next();
> > MultiLineString multiLineString = (MultiLineString)
> > feature.getDefaultGeometry();
> > for (int i = 0; i < multiLineString.getNumGeometries();
> > i++) {
> > lines.add((LineString)
> > multiLineString.getGeometryN(i));
> > }
> > }
> > // Split lines at intersections
> > lines = splitLines(lines);
> > } catch (Exception ex) {
> > ex.printStackTrace();
> > return null;
> > }
> > //create a linear graph generate
> > DirectedLineStringGraphGenerator lineStringGen = new
> > DirectedLineStringGraphGenerator();
> > for (int i = 0; i < lines.size(); ++i) {
> > lineStringGen.add((LineString) lines.get(i));
> > }
> > return (DirectedGraph) lineStringGen.getGraph();
> >
> > I really need to get this project working. I'm making a lot of tests but
> > at the moment, the only time dijkstra did not return null was when using
> > splitlines4.txt (which was buggy IMO). I hope you can have a look at it
> > and point me in the right direction. Thanks in advance.
> >
> > 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
> > > > >
> > > >
> > > >
> > >
> >
>
-------------------------------------------------------------------------
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
