## geotools-gt2-users

 [Geotools-gt2-users] Calculating internal intersections From: Jase - 2005-12-22 18:44:29 Attachments: Message as HTML ```Ooops, the mail got sent out before I even got to finish writing it but.... anway, after a long break, I decided to get back to my project on geotools which is building a traversable road network. Justin has given me lots of pointers which I really appreciate. A typical road network in my database would look like this LINESTRING (101.65546500 3.18735800,101.65534200 3.18778200,101.65518800 3.18819300,101.65503000 3.18857400,101.65489700 3.18884600,101.65472600 3.18905400,101.65455000 3.18920800,101.65391400 3.18965200,101.65354600) Now since the code does not take into account internal intersections, I would have to manually calculate the internal intersections. What I initially did was to copy the entire LineString object into a string and split them up using a string tokenizer and convert it back again to a LineString object . It was silly and inefficient. I realized it halfway tha= t perhaps there could be a better method in doing this. I've been looking through the API and can't find anything suitable for this. Am i missing something here? Are there any classes i can use to directly operate on the object? Thanks.... ```
 Re: [Geotools-gt2-users] Calculating internal intersections From: Justin Deoliveira - 2005-12-22 19:16:17 ```Hi Jase, You could do this efficiently with a spatial index and the normal geometry intersection routines. Here is some pseudeo code. LineString[] lines = ... QuadTree index = .. for (LineString line : lines) { index.insert(line); } for (LineString line: lines) { Lines close = index.query(line); for (LineString other : close) { if (line.insersects(close)) { Point p = line.intersection(close): LineString[] lineSplit = line.split(p); LineString[] closeSplit = close.split(p); lines.remove(line); lines.remove(close); lines.addAll(lineSplit); lines.addAll(closeSplit); index.remove(line); index.remove(close); index.addAll(lineSplit); index.addAll(closeSplit); } } } Of course the actual algorithm will be more complicated as there will be more bookkeeping going on. And you will have to deal with special cases such as lines that intersect multiple times, etc... Hope that helps. -Justin Jase wrote: > Ooops, the mail got sent out before I even got to finish writing it > but.... anway, after a long break, I decided to get back to my project > on geotools which is building a traversable road network. Justin has > given me lots of pointers which I really appreciate. > > A typical road network in my database would look like this > LINESTRING (101.65546500 3.18735800,101.65534200 3.18778200,101.65518800 > 3.18819300,101.65503000 3.18857400,101.65489700 3.18884600,101.65472600 > 3.18905400,101.65455000 3.18920800,101.65391400 3.18965200,101.65354600) > > Now since the code does not take into account internal intersections, I > would have to manually calculate the internal intersections. What I > initially did was to copy the entire LineString object into a string and > split them up using a string tokenizer and convert it back again to a > LineString object . It was silly and inefficient. I realized it halfway > that perhaps there could be a better method in doing this. I've been > looking through the API and can't find anything suitable for this. Am i > missing something here? Are there any classes i can use to directly > operate on the object? > > Thanks.... -- Justin Deoliveira The Open Planning Project http://topp.openplans.org ```