Line intersections

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Line intersections

Jochen123
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
--
Jochen Topf  [hidden email]  http://www.remote.org/jochen/  +49-721-388298

_______________________________________________
geos-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: 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

_______________________________________________
geos-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: Line intersections

Jochen123
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 <[hidden email]>
> To: GEOS Development List <[hidden email]>
> 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
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>

--
Jochen Topf  [hidden email]  http://www.remote.org/jochen/  +49-721-388298

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