[geos-devel] Line intersections

[Chris Hodgson]

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