[geos-devel] Line intersections

[Jochen Topf]

Hi!

thanks for the suggestions. All of that seems rather expensive to me. So in the
end I wrote the intersection check myself: Create std::vector with all line
segments, sort the vector. Go through the vector in two nested loops. Outer
loop goes through all segments, inner starts from position of outer plus one
until it finds a segment thats outside the envelope of first segment. Check
for intersection with usual line segment intersection check.

Nearly 30 million segments fit easily into memory and the whole things takes
not even 30 seconds including reading in of data etc.

Jochen

On Fri, Apr 27, 2012 at 11:32:34AM -0700, Chris Hodgson wrote:
> Date: Fri, 27 Apr 2012 11:32:34 -0700
> From: Chris Hodgson <chodgson at refractions.net>
> To: GEOS Development List <geos-devel at lists.osgeo.org>
> Subject: Re: [geos-devel] Line intersections
> 
> Jochen,
> 
> I'll have to admit, I'm not sure exactly what functions you want to
> use in GEOS to do this, but from an algorithmic standpoint I suggest
> the following line of reasoning:
> 
> - depending on how long your linestrings are, and how big a machine
> you have, they may or may not be able to fit all in memory
>   - if they all fit in memory:
>     - build an index on them
>     - loop over them, using the index to retrieve a list of all the
> linestrings that overlap the bounding box of the current linestring
>     - loop over all those and test for intersection with the current
> 
>   - if they don't all fit in memory:
>     - put them in postgis and use a single SQL query to do the same
> logic as above (this also works even if they do fit in memory :)
>     - alternatively, create a grid where within each cell is a
> number of linestrings that will fit in memory, and for each cell,
> retrieve linestrings that overlap that cell (brute force) and use
> the above algorithm (make the cells as large as possible so there
> are fewer of them so you don't have to spend to much time finding
> all the linestrings that overlap each cell)
> 
> - one other thing to consider is the degree of entanglement of your
> linestrings, that is, how many linestrings' bounding boxes do you
> expect to overlap the bounding box of any given linestring? eg. low
> entanglement would be the line segments of a downtown city road
> network, high entanglement might be contour lines, depending on how
> they're modeled. If you have high entanglement, it might serve to
> break down all the linestrings into smaller pieces, possibly even
> into 2-point line segments which are really easy to test, before
> doing either of the above approaches. The idea here is to minimize
> the number of intersection tests between large linestrings.
> 
> Cheers,
> Chris
> 
> 
> On 12-04-27 10:46 AM, Jochen Topf wrote:
> >Hi!
> >
> >I have a dataset with hundreds of thousands of linestrings and want to find any
> >intersections between those linestrings. There will only be a few
> >intersections.
> >
> >Any suggestions on how to do this efficiently with GEOS?
> >
> >Jochen
> 
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
> 

-- 
Jochen Topf  jochen at remote.org  http://www.remote.org/jochen/  +49-721-388298