A hybrid-ish nearest neighbour search implemented in rust, tailored towards consistent performance, especially on difficult inputs for KDTrees

Navigation

Verified details

These details have been verified by PyPI
Maintainers
Avatar for ham430 from gravatar.com ham430

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

Author: Hamish Morgan <ham430@gmail.com>

Tags nearest, neighbour, pointcloud

Requires: Python >=3.8

Classifiers

Project description

OxVoxNNS - Oxidised Voxelised Nearest Neighbour Search

PyPI Actions Status

A hybrid-ish nearest neighbour search implemented in rust, tailored towards consistent performance, especially on difficult inputs for KDTrees

Installation

Precompiled (from PyPI, recommended)

pip install ox_vox_nns

Manual

Checkout this repo and enter a virtual environment, then run

maturin develop --release

Usage

Basic usage, query a block of query points in sparse mode:

import numpy as np
from ox_vox_nns.ox_vox_nns import OxVoxNNS

NUM_POINTS = 100_000
TEST_POINTS = np.random.random((NUM_POINTS, 3))

indices, distances = ox_vox_nns.OxVoxNNS(
    search_points=TEST_POINTS,
    max_dist=0.05,
).find_neighbours(
    query_points=TEST_POINTS,
    num_neighbours=1000,
    sparse=True,
)

More complex usage, using a single NNS object for multiple exact mode queries (e.g. to distribute the nns object and perform queries in parallel, or to query from a large number of query points in batches/chunks)

# same imports and test data as above

nns = ox_vox_nns.OxVoxNNS(TEST_POINTS, 0.1)

for query_points_chunk in query_points_chunks:
    chunk_indices, chunk_distances = nns.find_neighbours(
        query_points=query_points_chunk,
        num_neighbours=1,
        sparse=False,
    )

Performance

As a rough heuristic:

  • Open3D will edge out OxVox on easier data, e.g. uniformally distributed points, though OxVox does outperform SciPy and SKLearn's KDTree implementations
  • OxVox in exact mode will outperform even Open3D on harder inputs, e.g. with clusters of very dense points
  • OxVox in sparse mode or with epsilon > 0.0 will dramatically outperform KDTrees too. This is not really a fair comparison, but if you don't strictly need the exact k nearest neighbours it can be very helpful

See performance_test_ox_vox_nns.py for test code.

More thorough tests and interactive visualisations are still being developed to help a prospective user decide quickly if OxVox is worth trying

Project details

Verified details

These details have been verified by PyPI
Maintainers
Avatar for ham430 from gravatar.com ham430

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

Author: Hamish Morgan <ham430@gmail.com>

Tags nearest, neighbour, pointcloud

Requires: Python >=3.8

Classifiers

Release history Release notifications | RSS feed

This version

0.5.0

0.4.0

0.3.0

0.2.0

0.1.0

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

ox_vox_nns-0.5.0.tar.gz (19.8 kB view hashes)

Uploaded Source

Built Distributions

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-pp310-pypy310_pp73-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-pp39-pypy39_pp73-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-pp38-pypy38_pp73-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded PyPy manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-cp313-cp313-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp313-cp313-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp313-cp313-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp313-cp313-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.13 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp312-none-win_amd64.whl (270.4 kB view hashes)

Uploaded CPython 3.12 Windows x86-64

ox_vox_nns-0.5.0-cp312-none-win32.whl (263.3 kB view hashes)

Uploaded CPython 3.12 Windows x86

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp312-cp312-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-cp312-cp312-macosx_11_0_arm64.whl (412.1 kB view hashes)

Uploaded CPython 3.12 macOS 11.0+ ARM64

ox_vox_nns-0.5.0-cp312-cp312-macosx_10_12_x86_64.whl (420.2 kB view hashes)

Uploaded CPython 3.12 macOS 10.12+ x86-64

ox_vox_nns-0.5.0-cp311-none-win_amd64.whl (269.8 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

ox_vox_nns-0.5.0-cp311-none-win32.whl (263.3 kB view hashes)

Uploaded CPython 3.11 Windows x86

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp311-cp311-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-cp311-cp311-macosx_11_0_arm64.whl (411.4 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

ox_vox_nns-0.5.0-cp311-cp311-macosx_10_12_x86_64.whl (419.1 kB view hashes)

Uploaded CPython 3.11 macOS 10.12+ x86-64

ox_vox_nns-0.5.0-cp310-none-win_amd64.whl (269.8 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

ox_vox_nns-0.5.0-cp310-none-win32.whl (263.3 kB view hashes)

Uploaded CPython 3.10 Windows x86

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp310-cp310-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-cp310-cp310-macosx_11_0_arm64.whl (411.4 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

ox_vox_nns-0.5.0-cp310-cp310-macosx_10_12_x86_64.whl (419.1 kB view hashes)

Uploaded CPython 3.10 macOS 10.12+ x86-64

ox_vox_nns-0.5.0-cp39-none-win_amd64.whl (269.9 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

ox_vox_nns-0.5.0-cp39-none-win32.whl (263.6 kB view hashes)

Uploaded CPython 3.9 Windows x86

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp39-cp39-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.12+ i686

ox_vox_nns-0.5.0-cp38-none-win_amd64.whl (269.8 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

ox_vox_nns-0.5.0-cp38-none-win32.whl (262.2 kB view hashes)

Uploaded CPython 3.8 Windows x86

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.4 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ s390x

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.3 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ppc64le

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARMv7l

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARM64

ox_vox_nns-0.5.0-cp38-cp38-manylinux_2_12_i686.manylinux2010_i686.whl (1.3 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.12+ i686

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page