Question: better way to find intersections?

[jliebrand]

Hi there,

I have a bunch of polygons, and a lineSegment, and I'm using rbush to try and determine if the line segment intersects with any of the polygons. Here's in pseudo code what I do:

1- for each line segment in each polygon, calculate it's bounding box and add it to an array
2- when done, bulk load the array of bboxes to the tree
3- create a bbox around the line segment to search for
4- search for bounding boxes in the tree that are covered by the bounding box of the line segment
5- for all of those, loop through the original line segments and do a simple line intersect check

This gets inefficient if the line i'm looking for is a (long) diagonal, because the bounding box gets large. To counteract this, I actually split the line segment up in to smaller line segments and draw a bounding box around each smaller segment, and then use those to do the search in the tree...

Are there better ways to do this? Is there a way to do a search in the tree for just a line segment so that it returns the bounding boxes the line crosses (which I'd then have to check for true intersection)

Or is there even a completely different, more efficient way you would recommend to check if one line segment intersects with any part of a hundred or so different polygons?

[mourner]

One more efficient way I know is to write a custom search function — like the original one, but instead of intersects(searchBBox, nodeBBox) you would call segmentIntersectsBox(searchSegment, nodeBBox) to filter out nodes that don't intersect the query segment. I think this should be pretty fast.

BTW if your set of polygons to search is static, I recommend also looking into https://github.com/mourner/flatbush.

[jliebrand]

Sweet! Thanks - that should be pretty straight forward

(And nope, the polygons aren't static :-( )