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

[hidden email]
http://lists.osgeo.org/mailman/listinfo/geos-devel