Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
Dear Jan. Thank you for you reply. I've downloaded denmark.osm.highway.bz2 (data exactly I'm looking for) and imported it into PostgreSQL db configured to API v.6.0 Now I have ways, nodes, relatins, etc, there... Could you point me please, how to build a graph now in Java app(I didn't find a command for OSMOSIS to build a graph) and find a shortest route? Did you mentioned Traveling SalesMan library and Route interface? ( http://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=TS/Examples 2010/6/17 Jan Torben Heuer jan_key67...@jtheuer.de Oleg Demchenko wrote: Well, there are RegionName.osm.bz2 and RegionName.highway.bz2 available for each region/country on CloudsMade. I've loaded it to my postGIS DB wiith osm2pgsql Utility. File * I took the OSMOSIS importer. It creates graphs. Jan P.S. Please only reply to list, not to my email address. -- From address is valid until 01.06.2011 -- 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 -- 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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
2010/6/16 Jan Torben Heuer jan_key67...@jtheuer.de Oleg Demchenko wrote: Data is given from a Denmark OSM highway shapefile downloaded from public CloudsMade server. In order to optimize process I'm selecting from database If you use the OSM data, why don't you download their nodes and ways directly instead of using the generated shapefile and try to reconstruct the graph based on intersections? You'll end up as Geisterfahrer on the Autobahn ;-) Thank for your reply Jan. Yes, I'm guite new on GeoTools and OSM data formats Autobahn :-)) Sorry, in advance for my next questions. Well, there are RegionName.osm.bz2 and RegionName.highway.bz2 available for each region/country on CloudsMade. I've loaded it to my postGIS DB wiith osm2pgsql Utility. File * planet_osm_roads* was created. Does this file (field waygeometry) contains in MultiLineString nodes and ways you've mentioned in you post above? Jan -- From address is valid until 01.06.2011 -- 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 -- 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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
Hi Jody.
I'm using DirectedLineStringGraphGenerator to build a Directed Graph from
VectorLineString.
...
//create a linear graph generate
DirectedLineStringGraphGenerator lineStringGen =
new DirectedLineStringGraphGenerator();
for (int i = 0; i lines.size(); ++i) {
lineStringGen.add((LineString) lines.get(i));
}
DirectedGraph g= lineStringGen.getGraph();
Also there is example from GEOTools documentation which use
FeatureGraphGenerator wrapper
*// get a feature collection somehow
FeatureCollection fCollection = featureSource.getFeatures(Filter.INCLUDE);
FeatureIterator featureIterator = fCollection.features();
//create a linear graph generate
LineStringGraphGenerator lineStringGen = new LineStringGraphGenerator();*
*//wrap it in a feature graph generator
FeatureGraphGenerator featureGen = new FeatureGraphGenerator( lineStringGen
);*
*//throw all the features into the graph generator
Iterator iter = fCollection.iterator();
while(iter.hasNext()){
Feature feature = (Feature)iter.next();
featureGen.add( feature );
}*
*Graph g = featureGen.getGraph()
*
Please, advice what is class name of the builder which may help me to build
a well connected graph from a line segments?
2010/6/17 Jody Garnett jody.garn...@gmail.com
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 VectorLineString.
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 VectorLineString 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.
--
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
I think you will want to look inside the code of both of those; and produce
your own graph generator that does exactly what you want.
Jody
On 17/06/2010, at 5:27 PM, Oleg Demchenko wrote:
Hi Jody.
I'm using DirectedLineStringGraphGenerator to build a Directed Graph from
VectorLineString.
...
//create a linear graph generate
DirectedLineStringGraphGenerator lineStringGen = new
DirectedLineStringGraphGenerator();
for (int i = 0; i lines.size(); ++i) {
lineStringGen.add((LineString) lines.get(i));
}
DirectedGraph g= lineStringGen.getGraph();
Also there is example from GEOTools documentation which use
FeatureGraphGenerator wrapper
// get a feature collection somehow
FeatureCollection fCollection = featureSource.getFeatures(Filter.INCLUDE);
FeatureIterator featureIterator = fCollection.features();
//create a linear graph generate
LineStringGraphGenerator lineStringGen = new LineStringGraphGenerator();
//wrap it in a feature graph generator
FeatureGraphGenerator featureGen = new FeatureGraphGenerator( lineStringGen );
//throw all the features into the graph generator
Iterator iter = fCollection.iterator();
while(iter.hasNext()){
Feature feature = (Feature)iter.next();
featureGen.add( feature );
}
Graph g = featureGen.getGraph()
Please, advice what is class name of the builder which may help me to build a
well connected graph from a line segments?
2010/6/17 Jody Garnett jody.garn...@gmail.com
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 VectorLineString. 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 VectorLineString 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.
--
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
Oleg Demchenko wrote: Well, there are RegionName.osm.bz2 and RegionName.highway.bz2 available for each region/country on CloudsMade. I've loaded it to my postGIS DB wiith osm2pgsql Utility. File * I took the OSMOSIS importer. It creates graphs. Jan P.S. Please only reply to list, not to my email address. -- From address is valid until 01.06.2011 -- 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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
Oleg Demchenko wrote: Data is given from a Denmark OSM highway shapefile downloaded from public CloudsMade server. In order to optimize process I'm selecting from database If you use the OSM data, why don't you download their nodes and ways directly instead of using the generated shapefile and try to reconstruct the graph based on intersections? You'll end up as Geisterfahrer on the Autobahn ;-) Jan -- From address is valid until 01.06.2011 -- 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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection for DijkstraShortestPathFinder
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 VectorLineString. 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 VectorLineString 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 VectorLineString splitLines(VectorLineString 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);
VectorLineString l1_sub = new VectorLineString();
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;
}
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
Could you confirm that you received the data you needed?
Chris.
On Jan 19, 2008 1:06 AM, Justin Deoliveira [EMAIL PROTECTED] wrote:
Hi Chris,
Sorry, its been a busy week and I have not had time to keep up with your
questions. Its not immediately evident to me what is wrong with your
code. I would have to debug it over on my end. You said your data is a
shapefile with a few thousands rows in it? If there are no licensing or
confidentiality issues is there any chance i can get my hands on it?
that way i could test over here.
If so, please send the location of the shapefile (you can in a private
email if you wish). Also the most recent version of all your code.
-justin
Chris wrote:
Sorry, it is me again but I'm still stuck with the same problem: I
tried the following
Coordinate[] c = new
Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l1a = new LineString(new CoordinateArraySequence(c), new
GeometryFactory(new PrecisionModel(
PrecisionModel.maximumPreciseValue), 4326));
l1_sub.add(l1a);
if(!l1.covers(l1a))
System.out.println(Error: a);
But this did not improve anything (Still prints Error: a). Hence, in
the following of my routine, I trying to see which sub_part of l1 is
having an intersection with l2, it happens (more than 1000 times for
my shapefile) that I can find any l1 sub_part intersecting l2.
To detect the intersection, I'm using the following code:
int k = 0;
while (k l1_sub.size() !((LineString) l1_sub.get(k)).intersects(l2)) {
++k;
}
if(k = l1_sub.size()) {
System.out.println(error);
}
I hope someone can help me with this, because of this, my graph is
not perfectly connected and this is kinda annoying. This is the last
problem in my project... thanks in advance.
P.S: I forgot to mention in my previous mail that p in the
intersection point between l1 and another linestring l2.
On Jan 15, 2008 2:12 AM, Chris [EMAIL PROTECTED] wrote:
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.
!DSPAM:4007,4790fcb4143341804284693!
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Geotools-gt2-users mailing list
Geotools-gt2-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
Hi Chris,
Yes I got the data you sent. My apologies for not being able to dedicate
time to this but I am quite swamped with project work at the moment and
probably wont be able to get to this until the weekend.
-Justin
Chris wrote
Could you confirm that you received the data you needed?
Chris.
On Jan 19, 2008 1:06 AM, Justin Deoliveira [EMAIL PROTECTED] wrote:
Hi Chris,
Sorry, its been a busy week and I have not had time to keep up with your
questions. Its not immediately evident to me what is wrong with your
code. I would have to debug it over on my end. You said your data is a
shapefile with a few thousands rows in it? If there are no licensing or
confidentiality issues is there any chance i can get my hands on it?
that way i could test over here.
If so, please send the location of the shapefile (you can in a private
email if you wish). Also the most recent version of all your code.
-justin
Chris wrote:
Sorry, it is me again but I'm still stuck with the same problem: I
tried the following
Coordinate[] c = new
Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l1a = new LineString(new CoordinateArraySequence(c), new
GeometryFactory(new PrecisionModel(
PrecisionModel.maximumPreciseValue), 4326));
l1_sub.add(l1a);
if(!l1.covers(l1a))
System.out.println(Error: a);
But this did not improve anything (Still prints Error: a). Hence, in
the following of my routine, I trying to see which sub_part of l1 is
having an intersection with l2, it happens (more than 1000 times for
my shapefile) that I can find any l1 sub_part intersecting l2.
To detect the intersection, I'm using the following code:
int k = 0;
while (k l1_sub.size() !((LineString) l1_sub.get(k)).intersects(l2)) {
++k;
}
if(k = l1_sub.size()) {
System.out.println(error);
}
I hope someone can help me with this, because of this, my graph is
not perfectly connected and this is kinda annoying. This is the last
problem in my project... thanks in advance.
P.S: I forgot to mention in my previous mail that p in the
intersection point between l1 and another linestring l2.
On Jan 15, 2008 2:12 AM, Chris [EMAIL PROTECTED] wrote:
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.
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
!DSPAM:4007,47987ff0190371336712104!
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Geotools-gt2-users mailing list
Geotools-gt2-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
Hi Chris,
Sorry, its been a busy week and I have not had time to keep up with your
questions. Its not immediately evident to me what is wrong with your
code. I would have to debug it over on my end. You said your data is a
shapefile with a few thousands rows in it? If there are no licensing or
confidentiality issues is there any chance i can get my hands on it?
that way i could test over here.
If so, please send the location of the shapefile (you can in a private
email if you wish). Also the most recent version of all your code.
-justin
Chris wrote:
Sorry, it is me again but I'm still stuck with the same problem: I
tried the following
Coordinate[] c = new
Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l1a = new LineString(new CoordinateArraySequence(c), new
GeometryFactory(new PrecisionModel(
PrecisionModel.maximumPreciseValue), 4326));
l1_sub.add(l1a);
if(!l1.covers(l1a))
System.out.println(Error: a);
But this did not improve anything (Still prints Error: a). Hence, in
the following of my routine, I trying to see which sub_part of l1 is
having an intersection with l2, it happens (more than 1000 times for
my shapefile) that I can find any l1 sub_part intersecting l2.
To detect the intersection, I'm using the following code:
int k = 0;
while (k l1_sub.size() !((LineString) l1_sub.get(k)).intersects(l2)) {
++k;
}
if(k = l1_sub.size()) {
System.out.println(error);
}
I hope someone can help me with this, because of this, my graph is
not perfectly connected and this is kinda annoying. This is the last
problem in my project... thanks in advance.
P.S: I forgot to mention in my previous mail that p in the
intersection point between l1 and another linestring l2.
On Jan 15, 2008 2:12 AM, Chris [EMAIL PROTECTED] wrote:
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.
!DSPAM:4007,4790fcb4143341804284693!
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Geotools-gt2-users mailing list
Geotools-gt2-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
Sorry, it is me again but I'm still stuck with the same problem: I
tried the following
Coordinate[] c = new
Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l1a = new LineString(new CoordinateArraySequence(c), new
GeometryFactory(new PrecisionModel(
PrecisionModel.maximumPreciseValue), 4326));
l1_sub.add(l1a);
if(!l1.covers(l1a))
System.out.println(Error: a);
But this did not improve anything (Still prints Error: a). Hence, in
the following of my routine, I trying to see which sub_part of l1 is
having an intersection with l2, it happens (more than 1000 times for
my shapefile) that I can find any l1 sub_part intersecting l2.
To detect the intersection, I'm using the following code:
int k = 0;
while (k l1_sub.size() !((LineString) l1_sub.get(k)).intersects(l2)) {
++k;
}
if(k = l1_sub.size()) {
System.out.println(error);
}
I hope someone can help me with this, because of this, my graph is
not perfectly connected and this is kinda annoying. This is the last
problem in my project... thanks in advance.
P.S: I forgot to mention in my previous mail that p in the
intersection point between l1 and another linestring l2.
On Jan 15, 2008 2:12 AM, Chris [EMAIL PROTECTED] wrote:
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.
private static VectorLineString splitLines(VectorLineString 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
VectorLineString l1_sub = new VectorLineString();
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
Point p;
try {
p = (Point) gc.getGeometryN(0);
} catch (Exception e) {
continue;
}
if
(!l2.getStartPoint().getCoordinate().equals2D(p.getCoordinate())
!l2.getEndPoint().getCoordinate().equals2D(p.getCoordinate())) {
Coordinate[] c = new
Coordinate[]{(l2.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l2a = new LineString(new
CoordinateArraySequence(c), new GeometryFactory(new
PrecisionModel(PrecisionModel.maximumPreciseValue), 4326));
c = new Coordinate[]{p.getCoordinate(),
(l2.getEndPoint()).getCoordinate()};
LineString l2b = new LineString(new
CoordinateArraySequence(c), new GeometryFactory(new
PrecisionModel(PrecisionModel.maximumPreciseValue), 4326));
// 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().getCoordinate().equals2D(p.getCoordinate())
!l1.getEndPoint().getCoordinate().equals2D(p.getCoordinate())) {
Coordinate[] c = new
Coordinate[]{(l1.getStartPoint()).getCoordinate(), p.getCoordinate()};
LineString l1a = new LineString(new
CoordinateArraySequence(c), new GeometryFactory(new
PrecisionModel(PrecisionModel.maximumPreciseValue), 4326));
l1_sub.add(l1a);
c = new Coordinate[]{p.getCoordinate(),
(l1.getEndPoint()).getCoordinate()};
LineString l1b = new LineString(new
CoordinateArraySequence(c), new GeometryFactory(new
PrecisionModel(PrecisionModel.maximumPreciseValue), 4326));
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;
}
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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 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. !DSPAM:4007,4787a0db264908992556831! - 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 Geotools-gt2-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users !DSPAM:4007,4787a0db264908992556831! -- 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 Geotools-gt2-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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. Regards, Chris. On Jan 11, 2008 9:28 PM, Chris [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.LineStringcannot 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] 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 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. !DSPAM:4007,4787a0db264908992556831! - 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 Geotools-gt2-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users !DSPAM:4007,4787a0db264908992556831! -- 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 Geotools-gt2-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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] 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
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.
!DSPAM:4007,4787a0db264908992556831!
-
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
Geotools-gt2-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
!DSPAM:4007,4787a0db264908992556831!
--
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org
private VectorLineString splitLines(VectorLineString lines) {
VectorLineString new_lines = new VectorLineString();
boolean first = true;
int imax = lines.size()-1;
do {
if(!first) {
imax = new_lines.size()-1; // Optimization
// Merge the two vectors
lines.addAll(0, new_lines);
new_lines.clear();
}
for (int i = 0; i imax; ++i) {
LineString l1 = (LineString) lines.get(i);
int jmax = lines.size();
for (int j = i + 1; j jmax; ++j) {
LineString l2 = (LineString) lines.get(j);
Geometry gc = l1.intersection(l2);
if (gc.getNumGeometries() 0) {
// Intersection
Point p = (Point) gc.getGeometryN(0);
if (l2.getStartPoint() != p l2.getEndPoint() != p) {
// Remove old line from table
lines.remove(j);
// Split into two lines
Coordinate[] c = new
Coordinate[]{(l2.getStartPoint()).getCoordinate(), p.getCoordinate()};
lines.add(j, new LineString(new
CoordinateArraySequence(c), new GeometryFactory()));
c = new Coordinate[]{p.getCoordinate(),
(l2.getEndPoint()).getCoordinate()};
new_lines.add(new LineString(new
CoordinateArraySequence(c), new GeometryFactory()));
}
if (l1.getStartPoint() != p l1.getEndPoint() != p) {
// Remove old line from table
Re: [Geotools-gt2-users] Splitting LineStrings at their intersection
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
