Ploc is a Rust library for efficient point location queries.
The implementation is strongly influenced by matplotlib's C++ implementation, but differentiates itself by being able to handle arbitrary planar subdivisions instead of only triangulations, and by leveraging parallelism with rayon to accelerate the queries.
Python bindings will soon be available at ploc-py.
This crate is currently in a pretty early stage, and the code does need some cleanup. Also, it would probably need some more documentation.
The goal is to provide a drop-in replacement for matplotlib's TrapezoidMapTriFinder, but the following items are not done yet:
- Provide Python bindings
- Get peak memory usage to be competitive (currently ploc's peak memory usage is at least 50% higher than that of the mpl implementation)
- Provide full compatibility with the mpl implementation (this will probably not feasible but at least we should document somewhere why that is)
However, we already go a little further in a few respects and there are other things coming:
- Generalize the implementation to arbitrary planar subdivisions
- Get better single-threaded performance
- Accelerate the queries with parallelism
- Provide richer output for edge/corner cases (literally, when a query point lies on an edge or is a vertex of the planar subdivision, it would be nice to report that)
- Make it work
f32in addition tof64for the point coordinates - Add a quadtree implementation (initial tests show that it is much simpler to implement and it performs really well for large meshes, but not so much for small ones)
Contributions are welcome!
Feel free to open an issue or a PR if you find a bug or want something to be improved.
This work has been greatly influenced by the following:
matplotlib's C++ implementation: this is where I first learned about this algorithm, and the present project is very much indebted to this implementation. There was a comment that mentioned the De Berg book which I mention below.- De Berg, M. (2000). Computational geometry: algorithms and applications. Springer Science & Business Media.: a really good book on computational geometry. The chapter on the trapezoidal map explains everything really well.