Skip to content

Assess alternative implementations for calculating distance #13

@sgoodm

Description

@sgoodm

Currently using SciPy's cKDTree along with a Haversine calculation for accurate distance metrics. cKDTree is now the same as KDTree as of SciPy 1.6.0 (See #12 ), but KDTree was previously slower.

https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html
https://en.wikipedia.org/wiki/Haversine_formula

SciPy's Ball Tree had been tested initially and was slower
http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html

Another SciPy approach is using distance_transform_edt. It is unclear if this could return indexes of nearest cells in order to calculate Haversine distance rather than only Euclidean.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_edt.html

Finally, while gdal_proximity was determined to be insufficient and drove the need for this package, it would be worth doing creating some comparable tests and seeing if their implementation could help improve this package in some way.
https://gdal.org/programs/gdal_proximity.html
https://github.com/OSGeo/gdal/blob/fec15b146f8a750c23c5e765cac12ed5fc9c2b85/gdal/alg/gdalproximity.cpp

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions