[geos-devel] Line intersections
Chris Hodgson
chodgson at refractions.net
Fri Apr 27 14:32:34 EDT 2012
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
More information about the geos-devel
mailing list