simple existence check

[mzrzvi]

hi @mourner — i think there may be some utility in having a function similar to search but is more efficient for the use case of when we want to simply check if at least 1 result exists such that the first value found in the search that passes the filter function makes it return true. this might only really be useful if the filterFn we're sending does somewhat heavy computation, and i guess it might just make more sense to accept the results and filter outside the hash. i don't know how the search works internally, but if there's any optimizations for an exists function, that'd be awesome!

[mourner]

Thanks for the suggestion! Perhaps the easiest approach would be to add an optional maxResults parameters to search (similar to how it works in neighbors), and return early when reaching the specified number after this line:

flatbush/index.js

Line 241 in b82579a

results.push(index); // leaf item

Not sure how common this use case is though. Can you tell more about yours?

[HansBrende]

@mourner here's a use-case: test if a polygon is simple--only need one intersection meeting certain criteria to prove otherwise!

Even better than a "maxResults" though might be a generator method... that way caller can determine when to early-exit without having to calculate how many results are needed in advance (which would be especially useful if the output is being piped through another generator method, for example.)

[goto-bus-stop]

Maybe introducing a more primitive callback-based API would be useful?

query(minX: number, minY: number, maxX: number, maxY: number, callback: (index: number) => boolean): void

The search would stop early if you return false from the callback.

let found = false
bush.query(minX, minY, maxX, maxY, (index) => {
  found = true
  return false // bail out early
})

bush.search could be implemented on top of bush.query like this:

const results = []
this.query(minX, minY, maxX, maxY, (index) => {
  if (filterFn === undefined || filterFn(index)) {
    results.push(index)
  }
  return true
})
return results

I haven't checked what the performance implications of this are, but it is a less invasive change than a generator and it's probably faster (though maybe the temporary objects returned by gen.next() are more optimiser-friendly than I think).

This would support doing a boolean check if there's any elements that match a filter function. In my case I'm using flatbush to see if a point is in any hole inside a polygon, here I would bail out as soon as I have one match. (I'm working with hundreds of thousands of points and polygons with thousands of holes, and flatbush makes this absurdly faster!)

It would also support a theoretical use case of collecting results of many queries into a single array without allocating temporary arrays, which could happen eg. if you're doing an intersect on many polygons.