use rbush to speed up intersection tests

[tcql]

No description provided.

[shawnmgoulet]

@tcql @jfirebaugh @morganherlocker could anyone point me in the direction of (rbush + turf-intersect) implementation or something of the like? I am needing to populate an array of multiple intersecting polygons from a single clicked polygon of a multipolygon geojson.

OR is/are some other library(ies) recommended for this use case. Need to implement this in a Mapbox-GL-JS project and due to the suspected large number of intersects that will be needed, I don't think looping through would be great for speed..which is why I was looking towards pairing rbush for spatial indexing and then implementing turf-intersect off indexed polygons. I've not yet done this, but this workflow was suggested by @DenisCarriere.

The suggestion of rbush + turf-intersect in issue 567.

The geojson can be visualized here.

[morganherlocker]

@shawnmgoulet this is a common pairing, although I am not aware of any open source implementations (this would normally be implemented at the application/api-server level rather than in a library). The basic approach works like this:

preprocessing

1. foreach polygon
   1. calculate bbox (turf.bbox)
   2. insert bbox + polygon index into array of bboxes
2. bulk load bboxes into rtree (rbush.load)

querying

1. calculate bbox of query polygon (turf.bbox)
2. search rtree against the bbox (rbush.search)
3. foreach bbox collision
   1. use the collision index (stored earlier) to lookup the collided polygon
   2. intersect the query polygon against the collided polygon (turf.intersect)
   3. add the intersected geometry to an accumulating collection
4. return the collection of intersections

Each of these operations (ie: turf.bbox, turf.intersect, rbush.load, rbush.search) are documented in their respective repos, but I'm happy to help if you run into any snags with the implementation after reading the docs and giving it a try. Hope that helps!

[shawnmgoulet]

Hi again @morganherlocker so now I need to (if possible) spatially select polygons (using hexes right now) based of the encoded cardinal direction of the hex selected. So that, on user click, it would select a "cone" of hexes to manipulate encoded values of hexes within a cone based off the cardinal direction of the hexagon clicked on, basically a "cone" of sorts, or you could think of it as a fan, I suppose. I am trying to understand if using turf + rbush is still a workflow for achieving this new wrinkle? If not, what would you suggest...I'd still like to use Mapbox-GL-JS for this app.

I am attaching a screen shot of what this might look like, the selection set being the hexes within the outlined cone with a cardinal direction of East here. The application is for applying storm surge defending strategies to coastal land. I appreciate your assistance.

[DenisCarriere]

@shawnmgoulet please try to keep your issues relevant to TurfJS.

However, here's a suggestion that might help.

1. Find the centroid (point) of your hex.
2. Using @turf/destination find the next point using your cardinal direction (ex: East would have a bearing of 90 degrees) and the distance would be the width of a single hex.
3. Find the intersecting hex from the destination point.

Or you can create some kind of custom key/value dictionary that would be used as an index, it's totally up to you and how you design your application.

FYI: I recently published geojson-rbush which makes it a bit easier to load your GeoJSON into and RBush spatial index.

[shawnmgoulet]

@DenisCarriere thank you for the suggestion and help. Looks like that would be very relevant to TurfJS using @turf/destination. Apologies for my misunderstanding and low-end level of experience with the library and piecing together these spatial selections/queries. This approach (or something like it) seems logical to me and I will give it a go.

Also, I appreciate the update RE geojson-rbush.