Giter Club home page Giter Club logo

static_aabb2d_index's Introduction

StaticAABB2DIndex

Summary

Fast static spatial index data structure for 2D axis aligned bounding boxes utilizing hilbert curve spatial ordering. This is a rust port of the excellent flatbush javascript library.

By default no unsafe code is used (#![forbid(unsafe_code)] is applied). Some unsafe optimizations can be enabled by toggling on the unsafe_optimizations flag. Note the API is still safe when this flag is enabled, all optimizations are internal to the library. Currently the unsafe code is used to eliminate slice bounds checking and utilize uninitialized memory to avoid zeroing arrays when allocated.

Quick Links

Crate

Documentation

Examples

Benchmarks Repo

Quick Code Example

use static_aabb2d_index::*;
// create builder for index containing 4 axis aligned bounding boxes
// index also supports integers and custom types that implement the IndexableNum trait
let mut builder: StaticAABB2DIndexBuilder<f64> = StaticAABB2DIndexBuilder::new(4);
// add bounding boxes to the index
// add takes in (min_x, min_y, max_x, max_y) of the bounding box
builder.add(0.0, 0.0, 2.0, 2.0);
builder.add(-1.0, -1.0, 3.0, 3.0);
builder.add(0.0, 0.0, 1.0, 3.0);
builder.add(4.0, 2.0, 16.0, 8.0);
// note build may return an error if the number of added boxes does not equal the static size
// given at the time the builder was created or the type used fails to cast to a f64
let index: StaticAABB2DIndex<f64> = builder.build().unwrap();
// query the created index (min_x, min_y, max_x, max_y)
let query_results = index.query(-1.0, -1.0, -0.5, -0.5);
// query_results holds the index positions of the boxes that overlap with the box given
// (positions are according to the order boxes were added the index builder)
assert_eq!(query_results, vec![1]);
// the query may also be done with a visiting function that can stop the query early
let mut visited_results: Vec<usize> = Vec::new();
let mut visitor = |box_added_pos: usize| -> Control<()> {
    visited_results.push(box_added_pos);
    // return continue to continue visiting results, break to stop early
    Control::Continue
};

index.visit_query(-1.0, -1.0, -0.5, -0.5, &mut visitor);
assert_eq!(visited_results, vec![1]);

static_aabb2d_index's People

Contributors

jbuckmccready avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

Forkers

rreverser

static_aabb2d_index's Issues

Zero-copy compatibility with the JS implementation?

I assume the answer will be no, in which case feel free to close this issue.

I'm interested in use cases where I can share the index data with other implementations, such as flatbush in the browser or a python flatbush implementation. In the original JS implementation, the entire index is self-contained in a single buffer, which allows it to be shared both across web workers in the browser, but also with e.g. a rust-wasm implementation.

I see in your implementation you use a sensible rust approach that uses rust-native types. There would probably need to be significant changes to the implementation to use a single backing buffer, which you understandably might not be interested in, for only the prospect of future FFI potentials. Any thoughts?

criterion library required even for production build

Trying to integrate cavalier_contours in FreeCAD it is currently required to install criterion with all its dependencies for the build. Unfortunately the CI system FreeCAD uses has no online access and the criterion packages are not available for Ubuntu 22.04 and 20.04 - both are build targets for FreeCAD.

It would be really great if static_aabb2d_index could be built without requiring criterion which would never be used in this use case.

neighbors support?

Is it possible to port the neighbors method from flatbush? As far as I understand, it's currently not ported / not exposed via the API. /cc @mourner

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.