[Git][debian-gis-team/pykdtree][upstream] New upstream version 1.3.1+ds
Bas Couwenberg
gitlab at salsa.debian.org
Tue Oct 13 16:32:03 BST 2020
Bas Couwenberg pushed to branch upstream at Debian GIS Project / pykdtree
Commits:
bd55ef68 by Bas Couwenberg at 2020-10-13T17:05:56+02:00
New upstream version 1.3.1+ds
- - - - -
19 changed files:
- + .travis.yml
- − PKG-INFO
- − README
- + README
- + README.rst
- + appveyor.yml
- + appveyor/install.ps1
- + appveyor/missing-headers.ps1
- + appveyor/run_with_compiler.cmd
- − pykdtree.egg-info/PKG-INFO
- − pykdtree.egg-info/SOURCES.txt
- − pykdtree.egg-info/dependency_links.txt
- − pykdtree.egg-info/not-zip-safe
- − pykdtree.egg-info/requires.txt
- − pykdtree.egg-info/top_level.txt
- + pykdtree/_kdtree_core.c.mako
- + pykdtree/kdtree.pyx
- + pykdtree/render_template.py
- setup.cfg
Changes:
=====================================
.travis.yml
=====================================
@@ -0,0 +1,16 @@
+language: python
+python:
+- '2.7'
+- '3.6'
+
+env:
+- USE_OMP=0
+- USE_OMP=1 OMP_NUM_THREADS=4
+
+before_install:
+- sudo apt-get install python-dev
+
+install:
+- python setup.py install
+
+script: python setup.py test
=====================================
PKG-INFO deleted
=====================================
@@ -1,17 +0,0 @@
-Metadata-Version: 1.2
-Name: pykdtree
-Version: 1.3.1
-Summary: Fast kd-tree implementation with OpenMP-enabled queries
-Home-page: UNKNOWN
-Author: Esben S. Nielsen
-Author-email: storpipfugl at gmail.com
-License: UNKNOWN
-Description: UNKNOWN
-Platform: UNKNOWN
-Classifier: Development Status :: 5 - Production/Stable
-Classifier: License :: OSI Approved :: GNU General Public License v3 (GPLv3)
-Classifier: Programming Language :: Python
-Classifier: Operating System :: OS Independent
-Classifier: Intended Audience :: Science/Research
-Classifier: Topic :: Scientific/Engineering
-Requires-Python: >=2.7,!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*
=====================================
README deleted
=====================================
@@ -1,148 +0,0 @@
-.. image:: https://travis-ci.org/storpipfugl/pykdtree.svg?branch=master
- :target: https://travis-ci.org/storpipfugl/pykdtree
-.. image:: https://ci.appveyor.com/api/projects/status/ubo92368ktt2d25g/branch/master
- :target: https://ci.appveyor.com/project/storpipfugl/pykdtree
-
-========
-pykdtree
-========
-
-Objective
----------
-pykdtree is a kd-tree implementation for fast nearest neighbour search in Python.
-The aim is to be the fastest implementation around for common use cases (low dimensions and low number of neighbours) for both tree construction and queries.
-
-The implementation is based on scipy.spatial.cKDTree and libANN by combining the best features from both and focus on implementation efficiency.
-
-The interface is similar to that of scipy.spatial.cKDTree except only Euclidean distance measure is supported.
-
-Queries are optionally multithreaded using OpenMP.
-
-Installation
-------------
-Default build of pykdtree with OpenMP enabled queries using libgomp
-
-.. code-block:: bash
-
- $ cd <pykdtree_dir>
- $ python setup.py install
-
-If it fails with undefined compiler flags or you want to use another OpenMP implementation please modify setup.py at the indicated point to match your system.
-
-Building without OpenMP support is controlled by the USE_OMP environment variable
-
-.. code-block:: bash
-
- $ cd <pykdtree_dir>
- $ export USE_OMP=0
- $ python setup.py install
-
-Note evironment variables are by default not exported when using sudo so in this case do
-
-.. code-block:: bash
-
- $ USE_OMP=0 sudo -E python setup.py install
-
-Usage
------
-The usage of pykdtree is similar to scipy.spatial.cKDTree so for now refer to its documentation
-
- >>> from pykdtree.kdtree import KDTree
- >>> kd_tree = KDTree(data_pts)
- >>> dist, idx = kd_tree.query(query_pts, k=8)
-
-The number of threads to be used in OpenMP enabled queries can be controlled with the standard OpenMP environment variable OMP_NUM_THREADS.
-
-The **leafsize** argument (number of data points per leaf) for the tree creation can be used to control the memory overhead of the kd-tree. pykdtree uses a default **leafsize=16**.
-Increasing **leafsize** will reduce the memory overhead and construction time but increase query time.
-
-pykdtree accepts data in double precision (numpy.float64) or single precision (numpy.float32) floating point. If data of another type is used an internal copy in double precision is made resulting in a memory overhead. If the kd-tree is constructed on single precision data the query points must be single precision as well.
-
-Benchmarks
-----------
-Comparison with scipy.spatial.cKDTree and libANN. This benchmark is on geospatial 3D data with 10053632 data points and 4276224 query points. The results are indexed relative to the construction time of scipy.spatial.cKDTree. A leafsize of 10 (scipy.spatial.cKDTree default) is used.
-
-Note: libANN is *not* thread safe. In this benchmark libANN is compiled with "-O3 -funroll-loops -ffast-math -fprefetch-loop-arrays" in order to achieve optimum performance.
-
-================== ===================== ====== ======== ==================
-Operation scipy.spatial.cKDTree libANN pykdtree pykdtree 4 threads
------------------- --------------------- ------ -------- ------------------
-
-Construction 100 304 96 96
-
-query 1 neighbour 1267 294 223 70
-
-Total 1 neighbour 1367 598 319 166
-
-query 8 neighbours 2193 625 449 143
-
-Total 8 neighbours 2293 929 545 293
-================== ===================== ====== ======== ==================
-
-Looking at the combined construction and query this gives the following performance improvement relative to scipy.spatial.cKDTree
-
-========== ====== ======== ==================
-Neighbours libANN pykdtree pykdtree 4 threads
----------- ------ -------- ------------------
-1 129% 329% 723%
-
-8 147% 320% 682%
-========== ====== ======== ==================
-
-Note: mileage will vary with the dataset at hand and computer architecture.
-
-Test
-----
-Run the unit tests using nosetest
-
-.. code-block:: bash
-
- $ cd <pykdtree_dir>
- $ python setup.py nosetests
-
-Installing on AppVeyor
-----------------------
-
-Pykdtree requires the "stdint.h" header file which is not available on certain
-versions of Windows or certain Windows compilers including those on the
-continuous integration platform AppVeyor. To get around this the header file(s)
-can be downloaded and placed in the correct "include" directory. This can
-be done by adding the `anaconda/missing-headers.ps1` script to your repository
-and running it the install step of `appveyor.yml`:
-
- # install missing headers that aren't included with MSVC 2008
- # https://github.com/omnia-md/conda-recipes/pull/524
- - "powershell ./appveyor/missing-headers.ps1"
-
-In addition to this, AppVeyor does not support OpenMP so this feature must be
-turned off by adding the following to `appveyor.yml` in the
-`environment` section:
-
- environment:
- global:
- # Don't build with openmp because it isn't supported in appveyor's compilers
- USE_OMP: "0"
-
-Changelog
----------
-v1.3.1 : Fix masking in the "query" method introduced in 1.3.0
-
-v1.3.0 : Keyword argument "mask" added to "query" method. OpenMP compilation now works for MS Visual Studio compiler
-
-v1.2.2 : Build process fixes
-
-v1.2.1 : Fixed OpenMP thread safety issue introduced in v1.2.0
-
-v1.2.0 : 64 and 32 bit MSVC Windows support added
-
-v1.1.1 : Same as v1.1 release due to incorrect pypi release
-
-v1.1 : Build process improvements. Add data attribute to kdtree class for scipy interface compatibility
-
-v1.0 : Switched license from GPLv3 to LGPLv3
-
-v0.3 : Avoid zipping of installed egg
-
-v0.2 : Reduced memory footprint. Can now handle single precision data internally avoiding copy conversion to double precision. Default leafsize changed from 10 to 16 as this reduces the memory footprint and makes it a cache line multiplum (negligible if any query performance observed in benchmarks). Reduced memory allocation for leaf nodes. Applied patch for building on OS X.
-
-v0.1 : Initial version.
=====================================
README
=====================================
@@ -0,0 +1 @@
+README.rst
\ No newline at end of file
=====================================
README.rst
=====================================
@@ -0,0 +1,148 @@
+.. image:: https://travis-ci.org/storpipfugl/pykdtree.svg?branch=master
+ :target: https://travis-ci.org/storpipfugl/pykdtree
+.. image:: https://ci.appveyor.com/api/projects/status/ubo92368ktt2d25g/branch/master
+ :target: https://ci.appveyor.com/project/storpipfugl/pykdtree
+
+========
+pykdtree
+========
+
+Objective
+---------
+pykdtree is a kd-tree implementation for fast nearest neighbour search in Python.
+The aim is to be the fastest implementation around for common use cases (low dimensions and low number of neighbours) for both tree construction and queries.
+
+The implementation is based on scipy.spatial.cKDTree and libANN by combining the best features from both and focus on implementation efficiency.
+
+The interface is similar to that of scipy.spatial.cKDTree except only Euclidean distance measure is supported.
+
+Queries are optionally multithreaded using OpenMP.
+
+Installation
+------------
+Default build of pykdtree with OpenMP enabled queries using libgomp
+
+.. code-block:: bash
+
+ $ cd <pykdtree_dir>
+ $ python setup.py install
+
+If it fails with undefined compiler flags or you want to use another OpenMP implementation please modify setup.py at the indicated point to match your system.
+
+Building without OpenMP support is controlled by the USE_OMP environment variable
+
+.. code-block:: bash
+
+ $ cd <pykdtree_dir>
+ $ export USE_OMP=0
+ $ python setup.py install
+
+Note evironment variables are by default not exported when using sudo so in this case do
+
+.. code-block:: bash
+
+ $ USE_OMP=0 sudo -E python setup.py install
+
+Usage
+-----
+The usage of pykdtree is similar to scipy.spatial.cKDTree so for now refer to its documentation
+
+ >>> from pykdtree.kdtree import KDTree
+ >>> kd_tree = KDTree(data_pts)
+ >>> dist, idx = kd_tree.query(query_pts, k=8)
+
+The number of threads to be used in OpenMP enabled queries can be controlled with the standard OpenMP environment variable OMP_NUM_THREADS.
+
+The **leafsize** argument (number of data points per leaf) for the tree creation can be used to control the memory overhead of the kd-tree. pykdtree uses a default **leafsize=16**.
+Increasing **leafsize** will reduce the memory overhead and construction time but increase query time.
+
+pykdtree accepts data in double precision (numpy.float64) or single precision (numpy.float32) floating point. If data of another type is used an internal copy in double precision is made resulting in a memory overhead. If the kd-tree is constructed on single precision data the query points must be single precision as well.
+
+Benchmarks
+----------
+Comparison with scipy.spatial.cKDTree and libANN. This benchmark is on geospatial 3D data with 10053632 data points and 4276224 query points. The results are indexed relative to the construction time of scipy.spatial.cKDTree. A leafsize of 10 (scipy.spatial.cKDTree default) is used.
+
+Note: libANN is *not* thread safe. In this benchmark libANN is compiled with "-O3 -funroll-loops -ffast-math -fprefetch-loop-arrays" in order to achieve optimum performance.
+
+================== ===================== ====== ======== ==================
+Operation scipy.spatial.cKDTree libANN pykdtree pykdtree 4 threads
+------------------ --------------------- ------ -------- ------------------
+
+Construction 100 304 96 96
+
+query 1 neighbour 1267 294 223 70
+
+Total 1 neighbour 1367 598 319 166
+
+query 8 neighbours 2193 625 449 143
+
+Total 8 neighbours 2293 929 545 293
+================== ===================== ====== ======== ==================
+
+Looking at the combined construction and query this gives the following performance improvement relative to scipy.spatial.cKDTree
+
+========== ====== ======== ==================
+Neighbours libANN pykdtree pykdtree 4 threads
+---------- ------ -------- ------------------
+1 129% 329% 723%
+
+8 147% 320% 682%
+========== ====== ======== ==================
+
+Note: mileage will vary with the dataset at hand and computer architecture.
+
+Test
+----
+Run the unit tests using nosetest
+
+.. code-block:: bash
+
+ $ cd <pykdtree_dir>
+ $ python setup.py nosetests
+
+Installing on AppVeyor
+----------------------
+
+Pykdtree requires the "stdint.h" header file which is not available on certain
+versions of Windows or certain Windows compilers including those on the
+continuous integration platform AppVeyor. To get around this the header file(s)
+can be downloaded and placed in the correct "include" directory. This can
+be done by adding the `anaconda/missing-headers.ps1` script to your repository
+and running it the install step of `appveyor.yml`:
+
+ # install missing headers that aren't included with MSVC 2008
+ # https://github.com/omnia-md/conda-recipes/pull/524
+ - "powershell ./appveyor/missing-headers.ps1"
+
+In addition to this, AppVeyor does not support OpenMP so this feature must be
+turned off by adding the following to `appveyor.yml` in the
+`environment` section:
+
+ environment:
+ global:
+ # Don't build with openmp because it isn't supported in appveyor's compilers
+ USE_OMP: "0"
+
+Changelog
+---------
+v1.3.1 : Fix masking in the "query" method introduced in 1.3.0
+
+v1.3.0 : Keyword argument "mask" added to "query" method. OpenMP compilation now works for MS Visual Studio compiler
+
+v1.2.2 : Build process fixes
+
+v1.2.1 : Fixed OpenMP thread safety issue introduced in v1.2.0
+
+v1.2.0 : 64 and 32 bit MSVC Windows support added
+
+v1.1.1 : Same as v1.1 release due to incorrect pypi release
+
+v1.1 : Build process improvements. Add data attribute to kdtree class for scipy interface compatibility
+
+v1.0 : Switched license from GPLv3 to LGPLv3
+
+v0.3 : Avoid zipping of installed egg
+
+v0.2 : Reduced memory footprint. Can now handle single precision data internally avoiding copy conversion to double precision. Default leafsize changed from 10 to 16 as this reduces the memory footprint and makes it a cache line multiplum (negligible if any query performance observed in benchmarks). Reduced memory allocation for leaf nodes. Applied patch for building on OS X.
+
+v0.1 : Initial version.
=====================================
appveyor.yml
=====================================
@@ -0,0 +1,98 @@
+environment:
+ global:
+ # SDK v7.0 MSVC Express 2008's SetEnv.cmd script will fail if the
+ # /E:ON and /V:ON options are not enabled in the batch script intepreter
+ # See: http://stackoverflow.com/a/13751649/163740
+ CMD_IN_ENV: "cmd /E:ON /V:ON /C .\\appveyor\\run_with_compiler.cmd"
+ # Don't build with openmp because it isn't supported in appveyor's compilers
+ USE_OMP: "0"
+
+ matrix:
+ - PYTHON: "C:\\Python27_32"
+ PYTHON_VERSION: "2.7.8"
+ PYTHON_ARCH: "32"
+ MINICONDA_VERSION: "2"
+
+ - PYTHON: "C:\\Python27_64"
+ PYTHON_VERSION: "2.7.8"
+ PYTHON_ARCH: "64"
+ MINICONDA_VERSION: "2"
+
+ - PYTHON: "C:\\Python36_32"
+ PYTHON_VERSION: "3.6"
+ PYTHON_ARCH: "32"
+ MINICONDA_VERSION: "3"
+ USE_OMP: "0"
+
+ - PYTHON: "C:\\Python36_64"
+ PYTHON_VERSION: "3.6"
+ PYTHON_ARCH: "64"
+ MINICONDA_VERSION: "3"
+ USE_OMP: "0"
+
+ - PYTHON: "C:\\Python36_32"
+ PYTHON_VERSION: "3.6"
+ PYTHON_ARCH: "32"
+ MINICONDA_VERSION: "3"
+ USE_OMP: "1"
+ OMP_NUM_THREADS: "4"
+
+ - PYTHON: "C:\\Python36_64"
+ PYTHON_VERSION: "3.6"
+ PYTHON_ARCH: "64"
+ MINICONDA_VERSION: "3"
+ USE_OMP: "1"
+ OMP_NUM_THREADS: "4"
+
+install:
+ - "git submodule update --init --recursive"
+ - ECHO "Filesystem root:"
+ - ps: "ls \"C:/\""
+
+ - ECHO "Installed SDKs:"
+ - ps: "ls \"C:/Program Files/Microsoft SDKs/Windows\""
+
+ # install miniconda with the powershell script install.ps1
+ - "powershell ./appveyor/install.ps1"
+ # install missing headers that aren't included with MSVC 2008
+ # https://github.com/omnia-md/conda-recipes/pull/524
+ - "powershell ./appveyor/missing-headers.ps1"
+
+ # Prepend newly installed Python to the PATH of this build (this cannot be
+ # done from inside the powershell script as it would require to restart
+ # the parent CMD process).
+ - "SET PATH=%PYTHON%;%PYTHON%\\Scripts;%PATH%"
+
+ # Check that we have the expected version and architecture for Python
+ - "python --version"
+ - "python -c \"import struct; print(struct.calcsize('P') * 8)\""
+
+ # Install the build dependencies of the project. If some dependencies contain
+ # compiled extensions and are not provided as pre-built wheel packages,
+ # pip will build them from source using the MSVC compiler matching the
+ # target Python version and architecture
+ - "conda update --yes conda"
+ - "conda config --add channels conda-forge"
+ - "conda create -q --yes -n test python=%PYTHON_VERSION% numpy nose"
+ - "activate test"
+ - "pip install coveralls"
+ - "where python"
+
+build: false # Not a C# project, build stuff at the test step instead.
+
+test_script:
+ # Build the compiled extension and run the project tests
+ - "%CMD_IN_ENV% python setup.py test"
+
+after_test:
+ # If tests are successful, create a whl package for the project.
+ - "%CMD_IN_ENV% python setup.py bdist_wheel bdist_wininst"
+ - ps: "ls dist"
+
+artifacts:
+ # Archive the generated wheel package in the ci.appveyor.com build report.
+ - path: dist\*
+
+#on_success:
+# - TODO: upload the content of dist/*.whl to a public wheelhouse
+#
=====================================
appveyor/install.ps1
=====================================
@@ -0,0 +1,71 @@
+# Sample script to install anaconda under windows
+# Authors: Stuart Mumford
+# Borrwed from: Olivier Grisel and Kyle Kastner
+# License: BSD 3 clause
+
+$MINICONDA_URL = "http://repo.continuum.io/miniconda/"
+
+function DownloadMiniconda ($miniconda_version, $platform_suffix) {
+ $webclient = New-Object System.Net.WebClient
+ $filename = "Miniconda" + $miniconda_version + "-latest" + "-Windows-" + $platform_suffix + ".exe"
+
+ $url = $MINICONDA_URL + $filename
+
+ $basedir = $pwd.Path + "\"
+ $filepath = $basedir + $filename
+ if (Test-Path $filename) {
+ Write-Host "Reusing" $filepath
+ return $filepath
+ }
+
+ # Download and retry up to 3 times in case of network transient errors.
+ Write-Host "Downloading" $filename "from" $url
+ $retry_attempts = 2
+ for($i=0; $i -lt $retry_attempts; $i++){
+ try {
+ $webclient.DownloadFile($url, $filepath)
+ break
+ }
+ Catch [Exception]{
+ Start-Sleep 1
+ }
+ }
+ if (Test-Path $filepath) {
+ Write-Host "File saved at" $filepath
+ } else {
+ # Retry once to get the error message if any at the last try
+ $webclient.DownloadFile($url, $filepath)
+ }
+ return $filepath
+}
+
+function InstallMiniconda ($miniconda_version, $architecture, $python_home) {
+ Write-Host "Installing miniconda" $miniconda_version "for" $architecture "bit architecture to" $python_home
+ if (Test-Path $python_home) {
+ Write-Host $python_home "already exists, skipping."
+ return $false
+ }
+ if ($architecture -eq "32") {
+ $platform_suffix = "x86"
+ } else {
+ $platform_suffix = "x86_64"
+ }
+ $filepath = DownloadMiniconda $miniconda_version $platform_suffix
+ Write-Host "Installing" $filepath "to" $python_home
+ $args = "/InstallationType=AllUsers /S /AddToPath=1 /RegisterPython=1 /D=" + $python_home
+ Write-Host $filepath $args
+ Start-Process -FilePath $filepath -ArgumentList $args -Wait -Passthru
+ #Start-Sleep -s 15
+ if (Test-Path $python_home) {
+ Write-Host "Miniconda $miniconda_version ($architecture) installation complete"
+ } else {
+ Write-Host "Failed to install Python in $python_home"
+ Exit 1
+ }
+}
+
+function main () {
+ InstallMiniconda $env:MINICONDA_VERSION $env:PYTHON_ARCH $env:PYTHON
+}
+
+main
=====================================
appveyor/missing-headers.ps1
=====================================
@@ -0,0 +1,53 @@
+function InstallMissingHeaders () {
+ # Visual Studio 2008 is missing stdint.h, but you can just download one
+ # from the web.
+ # http://stackoverflow.com/questions/126279/c99-stdint-h-header-and-ms-visual-studio
+ $webclient = New-Object System.Net.WebClient
+
+ $include_dirs = @("C:\Program Files\Microsoft SDKs\Windows\v7.0\Include",
+ "C:\Program Files\Microsoft SDKs\Windows\v7.1\Include",
+ "C:\Users\appveyor\AppData\Local\Programs\Common\Microsoft\Visual C++ for Python\9.0\VC\include",
+ "C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\include",
+ "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include")
+
+ Foreach ($include_dir in $include_dirs) {
+ $urls = @(@("https://raw.githubusercontent.com/chemeris/msinttypes/master/stdint.h", "stdint.h"),
+ @("https://raw.githubusercontent.com/chemeris/msinttypes/master/inttypes.h", "inttypes.h"))
+
+ Foreach ($i in $urls) {
+ $url = $i[0]
+ $filename = $i[1]
+
+ $filepath = "$include_dir\$filename"
+ if (Test-Path $filepath) {
+ Write-Host $filename "already exists in" $include_dir
+ continue
+ }
+
+ Write-Host "Downloading remedial " $filename " from" $url "to" $filepath
+ $retry_attempts = 2
+ for($i=0; $i -lt $retry_attempts; $i++){
+ try {
+ $webclient.DownloadFile($url, $filepath)
+ break
+ }
+ Catch [Exception]{
+ Start-Sleep 1
+ }
+ }
+
+ if (Test-Path $filepath) {
+ Write-Host "File saved at" $filepath
+ } else {
+ # Retry once to get the error message if any at the last try
+ $webclient.DownloadFile($url, $filepath)
+ }
+ }
+ }
+}
+
+function main() {
+ InstallMissingHeaders
+}
+
+main
=====================================
appveyor/run_with_compiler.cmd
=====================================
@@ -0,0 +1,60 @@
+:: To build extensions for 64 bit Python 3, we need to configure environment
+:: variables to use the MSVC 2010 C++ compilers from GRMSDKX_EN_DVD.iso of:
+:: MS Windows SDK for Windows 7 and .NET Framework 4 (SDK v7.1)
+::
+:: To build extensions for 64 bit Python 2, we need to configure environment
+:: variables to use the MSVC 2008 C++ compilers from GRMSDKX_EN_DVD.iso of:
+:: MS Windows SDK for Windows 7 and .NET Framework 3.5 (SDK v7.0)
+::
+:: 32 bit builds do not require specific environment configurations.
+::
+:: Note: this script needs to be run with the /E:ON and /V:ON flags for the
+:: cmd interpreter, at least for (SDK v7.0)
+::
+:: More details at:
+:: https://github.com/cython/cython/wiki/64BitCythonExtensionsOnWindows
+:: http://stackoverflow.com/a/13751649/163740
+::
+:: Author: Olivier Grisel
+:: License: CC0 1.0 Universal: http://creativecommons.org/publicdomain/zero/1.0/
+ at ECHO OFF
+
+SET COMMAND_TO_RUN=%*
+SET WIN_SDK_ROOT=C:\Program Files\Microsoft SDKs\Windows
+
+SET MAJOR_PYTHON_VERSION="%PYTHON_VERSION:~0,1%"
+SET MINOR_PYTHON_VERSION=%PYTHON_VERSION:~2,1%
+IF %MAJOR_PYTHON_VERSION% == "2" (
+ SET WINDOWS_SDK_VERSION="v7.0"
+ SET SET_SDK_64=Y
+) ELSE IF %MAJOR_PYTHON_VERSION% == "3" (
+ SET WINDOWS_SDK_VERSION="v7.1"
+ IF %MINOR_PYTHON_VERSION% LEQ 4 (
+ SET SET_SDK_64=Y
+ ) ELSE (
+ SET SET_SDK_64=N
+ )
+) ELSE (
+ ECHO Unsupported Python version: "%MAJOR_PYTHON_VERSION%"
+ EXIT 1
+)
+
+IF "%PYTHON_ARCH%"=="64" (
+ IF %SET_SDK_64% == Y (
+ ECHO Configuring Windows SDK %WINDOWS_SDK_VERSION% for Python %MAJOR_PYTHON_VERSION% on a 64 bit architecture
+ SET DISTUTILS_USE_SDK=1
+ SET MSSdk=1
+ "%WIN_SDK_ROOT%\%WINDOWS_SDK_VERSION%\Setup\WindowsSdkVer.exe" -q -version:%WINDOWS_SDK_VERSION%
+ "%WIN_SDK_ROOT%\%WINDOWS_SDK_VERSION%\Bin\SetEnv.cmd" /x64 /release
+ ECHO Executing: %COMMAND_TO_RUN%
+ call %COMMAND_TO_RUN% || EXIT 1
+ ) ELSE (
+ ECHO Using default MSVC build environment for 64 bit architecture
+ ECHO Executing: %COMMAND_TO_RUN%
+ call %COMMAND_TO_RUN% || EXIT 1
+ )
+ ) ELSE (
+ ECHO Using default MSVC build environment for 32 bit architecture
+ ECHO Executing: %COMMAND_TO_RUN%
+ call %COMMAND_TO_RUN% || EXIT 1
+)
=====================================
pykdtree.egg-info/PKG-INFO deleted
=====================================
@@ -1,17 +0,0 @@
-Metadata-Version: 1.2
-Name: pykdtree
-Version: 1.3.1
-Summary: Fast kd-tree implementation with OpenMP-enabled queries
-Home-page: UNKNOWN
-Author: Esben S. Nielsen
-Author-email: storpipfugl at gmail.com
-License: UNKNOWN
-Description: UNKNOWN
-Platform: UNKNOWN
-Classifier: Development Status :: 5 - Production/Stable
-Classifier: License :: OSI Approved :: GNU General Public License v3 (GPLv3)
-Classifier: Programming Language :: Python
-Classifier: Operating System :: OS Independent
-Classifier: Intended Audience :: Science/Research
-Classifier: Topic :: Scientific/Engineering
-Requires-Python: >=2.7,!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*
=====================================
pykdtree.egg-info/SOURCES.txt deleted
=====================================
@@ -1,15 +0,0 @@
-LICENSE.txt
-MANIFEST.in
-README
-setup.cfg
-setup.py
-pykdtree/__init__.py
-pykdtree/_kdtree_core.c
-pykdtree/kdtree.c
-pykdtree/test_tree.py
-pykdtree.egg-info/PKG-INFO
-pykdtree.egg-info/SOURCES.txt
-pykdtree.egg-info/dependency_links.txt
-pykdtree.egg-info/not-zip-safe
-pykdtree.egg-info/requires.txt
-pykdtree.egg-info/top_level.txt
\ No newline at end of file
=====================================
pykdtree.egg-info/dependency_links.txt deleted
=====================================
@@ -1 +0,0 @@
-
=====================================
pykdtree.egg-info/not-zip-safe deleted
=====================================
@@ -1 +0,0 @@
-
=====================================
pykdtree.egg-info/requires.txt deleted
=====================================
@@ -1 +0,0 @@
-numpy
=====================================
pykdtree.egg-info/top_level.txt deleted
=====================================
@@ -1 +0,0 @@
-pykdtree
=====================================
pykdtree/_kdtree_core.c.mako
=====================================
@@ -0,0 +1,734 @@
+/*
+pykdtree, Fast kd-tree implementation with OpenMP-enabled queries
+
+Copyright (C) 2013 - present Esben S. Nielsen
+
+This program is free software: you can redistribute it and/or modify it under
+the terms of the GNU Lesser General Public License as published by the Free
+Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
+details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+This kd-tree implementation is based on the scipy.spatial.cKDTree by
+Anne M. Archibald and libANN by David M. Mount and Sunil Arya.
+*/
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <float.h>
+
+#define PA(i,d) (pa[no_dims * pidx[i] + d])
+#define PASWAP(a,b) { uint32_t tmp = pidx[a]; pidx[a] = pidx[b]; pidx[b] = tmp; }
+
+#ifdef _MSC_VER
+#define restrict __restrict
+#endif
+
+% for DTYPE in ['float', 'double']:
+
+typedef struct
+{
+ ${DTYPE} cut_val;
+ int8_t cut_dim;
+ uint32_t start_idx;
+ uint32_t n;
+ ${DTYPE} cut_bounds_lv;
+ ${DTYPE} cut_bounds_hv;
+ struct Node_${DTYPE} *left_child;
+ struct Node_${DTYPE} *right_child;
+} Node_${DTYPE};
+
+typedef struct
+{
+ ${DTYPE} *bbox;
+ int8_t no_dims;
+ uint32_t *pidx;
+ struct Node_${DTYPE} *root;
+} Tree_${DTYPE};
+
+% endfor
+
+% for DTYPE in ['float', 'double']:
+
+void insert_point_${DTYPE}(uint32_t *closest_idx, ${DTYPE} *closest_dist, uint32_t pidx, ${DTYPE} cur_dist, uint32_t k);
+void get_bounding_box_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t n, ${DTYPE} *bbox);
+int partition_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *bbox, int8_t *cut_dim,
+ ${DTYPE} *cut_val, uint32_t *n_lo);
+Tree_${DTYPE}* construct_tree_${DTYPE}(${DTYPE} *pa, int8_t no_dims, uint32_t n, uint32_t bsp);
+Node_${DTYPE}* construct_subtree_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, uint32_t bsp, ${DTYPE} *bbox);
+Node_${DTYPE} * create_node_${DTYPE}(uint32_t start_idx, uint32_t n, int is_leaf);
+void delete_subtree_${DTYPE}(Node_${DTYPE} *root);
+void delete_tree_${DTYPE}(Tree_${DTYPE} *tree);
+void print_tree_${DTYPE}(Node_${DTYPE} *root, int level);
+${DTYPE} calc_dist_${DTYPE}(${DTYPE} *point1_coord, ${DTYPE} *point2_coord, int8_t no_dims);
+${DTYPE} get_cube_offset_${DTYPE}(int8_t dim, ${DTYPE} *point_coord, ${DTYPE} *bbox);
+${DTYPE} get_min_dist_${DTYPE}(${DTYPE} *point_coord, int8_t no_dims, ${DTYPE} *bbox);
+void search_leaf_${DTYPE}(${DTYPE} *restrict pa, uint32_t *restrict pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *restrict point_coord,
+ uint32_t k, uint32_t *restrict closest_idx, ${DTYPE} *restrict closest_dist);
+void search_leaf_${DTYPE}_mask(${DTYPE} *restrict pa, uint32_t *restrict pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *restrict point_coord,
+ uint32_t k, uint8_t *restrict mask, uint32_t *restrict closest_idx, ${DTYPE} *restrict closest_dist);
+void search_splitnode_${DTYPE}(Node_${DTYPE} *root, ${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, ${DTYPE} *point_coord,
+ ${DTYPE} min_dist, uint32_t k, ${DTYPE} distance_upper_bound, ${DTYPE} eps_fac, uint8_t *mask, uint32_t * closest_idx, ${DTYPE} *closest_dist);
+void search_tree_${DTYPE}(Tree_${DTYPE} *tree, ${DTYPE} *pa, ${DTYPE} *point_coords,
+ uint32_t num_points, uint32_t k, ${DTYPE} distance_upper_bound,
+ ${DTYPE} eps, uint8_t *mask, uint32_t *closest_idxs, ${DTYPE} *closest_dists);
+
+% endfor
+
+% for DTYPE in ['float', 'double']:
+
+/************************************************
+Insert point into priority queue
+Params:
+ closest_idx : index queue
+ closest_dist : distance queue
+ pidx : permutation index of data points
+ cur_dist : distance to point inserted
+ k : number of neighbours
+************************************************/
+void insert_point_${DTYPE}(uint32_t *closest_idx, ${DTYPE} *closest_dist, uint32_t pidx, ${DTYPE} cur_dist, uint32_t k)
+{
+ int i;
+ for (i = k - 1; i > 0; i--)
+ {
+ if (closest_dist[i - 1] > cur_dist)
+ {
+ closest_dist[i] = closest_dist[i - 1];
+ closest_idx[i] = closest_idx[i - 1];
+ }
+ else
+ {
+ break;
+ }
+ }
+ closest_idx[i] = pidx;
+ closest_dist[i] = cur_dist;
+}
+
+/************************************************
+Get the bounding box of a set of points
+Params:
+ pa : data points
+ pidx : permutation index of data points
+ no_dims: number of dimensions
+ n : number of points
+ bbox : bounding box (return)
+************************************************/
+void get_bounding_box_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t n, ${DTYPE} *bbox)
+{
+ ${DTYPE} cur;
+ int8_t bbox_idx, i, j;
+ uint32_t i2;
+
+ /* Use first data point to initialize */
+ for (i = 0; i < no_dims; i++)
+ {
+ bbox[2 * i] = bbox[2 * i + 1] = PA(0, i);
+ }
+
+ /* Update using rest of data points */
+ for (i2 = 1; i2 < n; i2++)
+ {
+ for (j = 0; j < no_dims; j++)
+ {
+ bbox_idx = 2 * j;
+ cur = PA(i2, j);
+ if (cur < bbox[bbox_idx])
+ {
+ bbox[bbox_idx] = cur;
+ }
+ else if (cur > bbox[bbox_idx + 1])
+ {
+ bbox[bbox_idx + 1] = cur;
+ }
+ }
+ }
+}
+
+/************************************************
+Partition a range of data points by manipulation the permutation index.
+The sliding midpoint rule is used for the partitioning.
+Params:
+ pa : data points
+ pidx : permutation index of data points
+ no_dims: number of dimensions
+ start_idx : index of first data point to use
+ n : number of data points
+ bbox : bounding box of data points
+ cut_dim : dimension used for partition (return)
+ cut_val : value of cutting point (return)
+ n_lo : number of point below cutting plane (return)
+************************************************/
+int partition_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *bbox, int8_t *cut_dim, ${DTYPE} *cut_val, uint32_t *n_lo)
+{
+ int8_t dim = 0, i;
+ uint32_t p, q, i2;
+ ${DTYPE} size = 0, min_val, max_val, split, side_len, cur_val;
+ uint32_t end_idx = start_idx + n - 1;
+
+ /* Find largest bounding box side */
+ for (i = 0; i < no_dims; i++)
+ {
+ side_len = bbox[2 * i + 1] - bbox[2 * i];
+ if (side_len > size)
+ {
+ dim = i;
+ size = side_len;
+ }
+ }
+
+ min_val = bbox[2 * dim];
+ max_val = bbox[2 * dim + 1];
+
+ /* Check for zero length or inconsistent */
+ if (min_val >= max_val)
+ return 1;
+
+ /* Use middle for splitting */
+ split = (min_val + max_val) / 2;
+
+ /* Partition all data points around middle */
+ p = start_idx;
+ q = end_idx;
+ while (p <= q)
+ {
+ if (PA(p, dim) < split)
+ {
+ p++;
+ }
+ else if (PA(q, dim) >= split)
+ {
+ /* Guard for underflow */
+ if (q > 0)
+ {
+ q--;
+ }
+ else
+ {
+ break;
+ }
+ }
+ else
+ {
+ PASWAP(p, q);
+ p++;
+ q--;
+ }
+ }
+
+ /* Check for empty splits */
+ if (p == start_idx)
+ {
+ /* No points less than split.
+ Split at lowest point instead.
+ Minimum 1 point will be in lower box.
+ */
+
+ uint32_t j = start_idx;
+ split = PA(j, dim);
+ for (i2 = start_idx + 1; i2 <= end_idx; i2++)
+ {
+ /* Find lowest point */
+ cur_val = PA(i2, dim);
+ if (cur_val < split)
+ {
+ j = i2;
+ split = cur_val;
+ }
+ }
+ PASWAP(j, start_idx);
+ p = start_idx + 1;
+ }
+ else if (p == end_idx + 1)
+ {
+ /* No points greater than split.
+ Split at highest point instead.
+ Minimum 1 point will be in higher box.
+ */
+
+ uint32_t j = end_idx;
+ split = PA(j, dim);
+ for (i2 = start_idx; i2 < end_idx; i2++)
+ {
+ /* Find highest point */
+ cur_val = PA(i2, dim);
+ if (cur_val > split)
+ {
+ j = i2;
+ split = cur_val;
+ }
+ }
+ PASWAP(j, end_idx);
+ p = end_idx;
+ }
+
+ /* Set return values */
+ *cut_dim = dim;
+ *cut_val = split;
+ *n_lo = p - start_idx;
+ return 0;
+}
+
+/************************************************
+Construct a sub tree over a range of data points.
+Params:
+ pa : data points
+ pidx : permutation index of data points
+ no_dims: number of dimensions
+ start_idx : index of first data point to use
+ n : number of data points
+ bsp : number of points per leaf
+ bbox : bounding box of set of data points
+************************************************/
+Node_${DTYPE}* construct_subtree_${DTYPE}(${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, uint32_t bsp, ${DTYPE} *bbox)
+{
+ /* Create new node */
+ int is_leaf = (n <= bsp);
+ Node_${DTYPE} *root = create_node_${DTYPE}(start_idx, n, is_leaf);
+ int rval;
+ int8_t cut_dim;
+ uint32_t n_lo;
+ ${DTYPE} cut_val, lv, hv;
+ if (is_leaf)
+ {
+ /* Make leaf node */
+ root->cut_dim = -1;
+ }
+ else
+ {
+ /* Make split node */
+ /* Partition data set and set node info */
+ rval = partition_${DTYPE}(pa, pidx, no_dims, start_idx, n, bbox, &cut_dim, &cut_val, &n_lo);
+ if (rval == 1)
+ {
+ root->cut_dim = -1;
+ return root;
+ }
+ root->cut_val = cut_val;
+ root->cut_dim = cut_dim;
+
+ /* Recurse on both subsets */
+ lv = bbox[2 * cut_dim];
+ hv = bbox[2 * cut_dim + 1];
+
+ /* Set bounds for cut dimension */
+ root->cut_bounds_lv = lv;
+ root->cut_bounds_hv = hv;
+
+ /* Update bounding box before call to lower subset and restore after */
+ bbox[2 * cut_dim + 1] = cut_val;
+ root->left_child = (struct Node_${DTYPE} *)construct_subtree_${DTYPE}(pa, pidx, no_dims, start_idx, n_lo, bsp, bbox);
+ bbox[2 * cut_dim + 1] = hv;
+
+ /* Update bounding box before call to higher subset and restore after */
+ bbox[2 * cut_dim] = cut_val;
+ root->right_child = (struct Node_${DTYPE} *)construct_subtree_${DTYPE}(pa, pidx, no_dims, start_idx + n_lo, n - n_lo, bsp, bbox);
+ bbox[2 * cut_dim] = lv;
+ }
+ return root;
+}
+
+/************************************************
+Construct a tree over data points.
+Params:
+ pa : data points
+ no_dims: number of dimensions
+ n : number of data points
+ bsp : number of points per leaf
+************************************************/
+Tree_${DTYPE}* construct_tree_${DTYPE}(${DTYPE} *pa, int8_t no_dims, uint32_t n, uint32_t bsp)
+{
+ Tree_${DTYPE} *tree = (Tree_${DTYPE} *)malloc(sizeof(Tree_${DTYPE}));
+ uint32_t i;
+ uint32_t *pidx;
+ ${DTYPE} *bbox;
+
+ tree->no_dims = no_dims;
+
+ /* Initialize permutation array */
+ pidx = (uint32_t *)malloc(sizeof(uint32_t) * n);
+ for (i = 0; i < n; i++)
+ {
+ pidx[i] = i;
+ }
+
+ bbox = (${DTYPE} *)malloc(2 * sizeof(${DTYPE}) * no_dims);
+ get_bounding_box_${DTYPE}(pa, pidx, no_dims, n, bbox);
+ tree->bbox = bbox;
+
+ /* Construct subtree on full dataset */
+ tree->root = (struct Node_${DTYPE} *)construct_subtree_${DTYPE}(pa, pidx, no_dims, 0, n, bsp, bbox);
+
+ tree->pidx = pidx;
+ return tree;
+}
+
+/************************************************
+Create a tree node.
+Params:
+ start_idx : index of first data point to use
+ n : number of data points
+************************************************/
+Node_${DTYPE}* create_node_${DTYPE}(uint32_t start_idx, uint32_t n, int is_leaf)
+{
+ Node_${DTYPE} *new_node;
+ if (is_leaf)
+ {
+ /*
+ Allocate only the part of the struct that will be used in a leaf node.
+ This relies on the C99 specification of struct layout conservation and padding and
+ that dereferencing is never attempted for the node pointers in a leaf.
+ */
+ new_node = (Node_${DTYPE} *)malloc(sizeof(Node_${DTYPE}) - 2 * sizeof(Node_${DTYPE} *));
+ }
+ else
+ {
+ new_node = (Node_${DTYPE} *)malloc(sizeof(Node_${DTYPE}));
+ }
+ new_node->n = n;
+ new_node->start_idx = start_idx;
+ return new_node;
+}
+
+/************************************************
+Delete subtree
+Params:
+ root : root node of subtree to delete
+************************************************/
+void delete_subtree_${DTYPE}(Node_${DTYPE} *root)
+{
+ if (root->cut_dim != -1)
+ {
+ delete_subtree_${DTYPE}((Node_${DTYPE} *)root->left_child);
+ delete_subtree_${DTYPE}((Node_${DTYPE} *)root->right_child);
+ }
+ free(root);
+}
+
+/************************************************
+Delete tree
+Params:
+ tree : Tree struct of kd tree
+************************************************/
+void delete_tree_${DTYPE}(Tree_${DTYPE} *tree)
+{
+ delete_subtree_${DTYPE}((Node_${DTYPE} *)tree->root);
+ free(tree->bbox);
+ free(tree->pidx);
+ free(tree);
+}
+
+/************************************************
+Print
+************************************************/
+void print_tree_${DTYPE}(Node_${DTYPE} *root, int level)
+{
+ int i;
+ for (i = 0; i < level; i++)
+ {
+ printf(" ");
+ }
+ printf("(cut_val: %f, cut_dim: %i)\n", root->cut_val, root->cut_dim);
+ if (root->cut_dim != -1)
+ print_tree_${DTYPE}((Node_${DTYPE} *)root->left_child, level + 1);
+ if (root->cut_dim != -1)
+ print_tree_${DTYPE}((Node_${DTYPE} *)root->right_child, level + 1);
+}
+
+/************************************************
+Calculate squared cartesian distance between points
+Params:
+ point1_coord : point 1
+ point2_coord : point 2
+************************************************/
+${DTYPE} calc_dist_${DTYPE}(${DTYPE} *point1_coord, ${DTYPE} *point2_coord, int8_t no_dims)
+{
+ /* Calculate squared distance */
+ ${DTYPE} dist = 0, dim_dist;
+ int8_t i;
+ for (i = 0; i < no_dims; i++)
+ {
+ dim_dist = point2_coord[i] - point1_coord[i];
+ dist += dim_dist * dim_dist;
+ }
+ return dist;
+}
+
+/************************************************
+Get squared distance from point to cube in specified dimension
+Params:
+ dim : dimension
+ point_coord : cartesian coordinates of point
+ bbox : cube
+************************************************/
+${DTYPE} get_cube_offset_${DTYPE}(int8_t dim, ${DTYPE} *point_coord, ${DTYPE} *bbox)
+{
+ ${DTYPE} dim_coord = point_coord[dim];
+
+ if (dim_coord < bbox[2 * dim])
+ {
+ /* Left of cube in dimension */
+ return dim_coord - bbox[2 * dim];
+ }
+ else if (dim_coord > bbox[2 * dim + 1])
+ {
+ /* Right of cube in dimension */
+ return dim_coord - bbox[2 * dim + 1];
+ }
+ else
+ {
+ /* Inside cube in dimension */
+ return 0.;
+ }
+}
+
+/************************************************
+Get minimum squared distance between point and cube.
+Params:
+ point_coord : cartesian coordinates of point
+ no_dims : number of dimensions
+ bbox : cube
+************************************************/
+${DTYPE} get_min_dist_${DTYPE}(${DTYPE} *point_coord, int8_t no_dims, ${DTYPE} *bbox)
+{
+ ${DTYPE} cube_offset = 0, cube_offset_dim;
+ int8_t i;
+
+ for (i = 0; i < no_dims; i++)
+ {
+ cube_offset_dim = get_cube_offset_${DTYPE}(i, point_coord, bbox);
+ cube_offset += cube_offset_dim * cube_offset_dim;
+ }
+
+ return cube_offset;
+}
+
+/************************************************
+Search a leaf node for closest point
+Params:
+ pa : data points
+ pidx : permutation index of data points
+ no_dims : number of dimensions
+ start_idx : index of first data point to use
+ size : number of data points
+ point_coord : query point
+ closest_idx : index of closest data point found (return)
+ closest_dist : distance to closest point (return)
+************************************************/
+void search_leaf_${DTYPE}(${DTYPE} *restrict pa, uint32_t *restrict pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *restrict point_coord,
+ uint32_t k, uint32_t *restrict closest_idx, ${DTYPE} *restrict closest_dist)
+{
+ ${DTYPE} cur_dist;
+ uint32_t i;
+ /* Loop through all points in leaf */
+ for (i = 0; i < n; i++)
+ {
+ /* Get distance to query point */
+ cur_dist = calc_dist_${DTYPE}(&PA(start_idx + i, 0), point_coord, no_dims);
+ /* Update closest info if new point is closest so far*/
+ if (cur_dist < closest_dist[k - 1])
+ {
+ insert_point_${DTYPE}(closest_idx, closest_dist, pidx[start_idx + i], cur_dist, k);
+ }
+ }
+}
+
+
+/************************************************
+Search a leaf node for closest point with data point mask
+Params:
+ pa : data points
+ pidx : permutation index of data points
+ no_dims : number of dimensions
+ start_idx : index of first data point to use
+ size : number of data points
+ point_coord : query point
+ mask : boolean array of invalid (True) and valid (False) data points
+ closest_idx : index of closest data point found (return)
+ closest_dist : distance to closest point (return)
+************************************************/
+void search_leaf_${DTYPE}_mask(${DTYPE} *restrict pa, uint32_t *restrict pidx, int8_t no_dims, uint32_t start_idx, uint32_t n, ${DTYPE} *restrict point_coord,
+ uint32_t k, uint8_t *mask, uint32_t *restrict closest_idx, ${DTYPE} *restrict closest_dist)
+{
+ ${DTYPE} cur_dist;
+ uint32_t i;
+ /* Loop through all points in leaf */
+ for (i = 0; i < n; i++)
+ {
+ /* Is this point masked out? */
+ if (mask[pidx[start_idx + i]])
+ {
+ continue;
+ }
+ /* Get distance to query point */
+ cur_dist = calc_dist_${DTYPE}(&PA(start_idx + i, 0), point_coord, no_dims);
+ /* Update closest info if new point is closest so far*/
+ if (cur_dist < closest_dist[k - 1])
+ {
+ insert_point_${DTYPE}(closest_idx, closest_dist, pidx[start_idx + i], cur_dist, k);
+ }
+ }
+}
+
+/************************************************
+Search subtree for nearest to query point
+Params:
+ root : root node of subtree
+ pa : data points
+ pidx : permutation index of data points
+ no_dims : number of dimensions
+ point_coord : query point
+ min_dist : minumum distance to nearest neighbour
+ mask : boolean array of invalid (True) and valid (False) data points
+ closest_idx : index of closest data point found (return)
+ closest_dist : distance to closest point (return)
+************************************************/
+void search_splitnode_${DTYPE}(Node_${DTYPE} *root, ${DTYPE} *pa, uint32_t *pidx, int8_t no_dims, ${DTYPE} *point_coord,
+ ${DTYPE} min_dist, uint32_t k, ${DTYPE} distance_upper_bound, ${DTYPE} eps_fac, uint8_t *mask,
+ uint32_t *closest_idx, ${DTYPE} *closest_dist)
+{
+ int8_t dim;
+ ${DTYPE} dist_left, dist_right;
+ ${DTYPE} new_offset;
+ ${DTYPE} box_diff;
+
+ /* Skip if distance bound exeeded */
+ if (min_dist > distance_upper_bound)
+ {
+ return;
+ }
+
+ dim = root->cut_dim;
+
+ /* Handle leaf node */
+ if (dim == -1)
+ {
+ if (mask)
+ {
+ search_leaf_${DTYPE}_mask(pa, pidx, no_dims, root->start_idx, root->n, point_coord, k, mask, closest_idx, closest_dist);
+ }
+ else
+ {
+ search_leaf_${DTYPE}(pa, pidx, no_dims, root->start_idx, root->n, point_coord, k, closest_idx, closest_dist);
+ }
+ return;
+ }
+
+ /* Get distance to cutting plane */
+ new_offset = point_coord[dim] - root->cut_val;
+
+ if (new_offset < 0)
+ {
+ /* Left of cutting plane */
+ dist_left = min_dist;
+ if (dist_left < closest_dist[k - 1] * eps_fac)
+ {
+ /* Search left subtree if minimum distance is below limit */
+ search_splitnode_${DTYPE}((Node_${DTYPE} *)root->left_child, pa, pidx, no_dims, point_coord, dist_left, k, distance_upper_bound, eps_fac, mask, closest_idx, closest_dist);
+ }
+
+ /* Right of cutting plane. Update minimum distance.
+ See Algorithms for Fast Vector Quantization
+ Sunil Arya and David M. Mount. */
+ box_diff = root->cut_bounds_lv - point_coord[dim];
+ if (box_diff < 0)
+ {
+ box_diff = 0;
+ }
+ dist_right = min_dist - box_diff * box_diff + new_offset * new_offset;
+ if (dist_right < closest_dist[k - 1] * eps_fac)
+ {
+ /* Search right subtree if minimum distance is below limit*/
+ search_splitnode_${DTYPE}((Node_${DTYPE} *)root->right_child, pa, pidx, no_dims, point_coord, dist_right, k, distance_upper_bound, eps_fac, mask, closest_idx, closest_dist);
+ }
+ }
+ else
+ {
+ /* Right of cutting plane */
+ dist_right = min_dist;
+ if (dist_right < closest_dist[k - 1] * eps_fac)
+ {
+ /* Search right subtree if minimum distance is below limit*/
+ search_splitnode_${DTYPE}((Node_${DTYPE} *)root->right_child, pa, pidx, no_dims, point_coord, dist_right, k, distance_upper_bound, eps_fac, mask, closest_idx, closest_dist);
+ }
+
+ /* Left of cutting plane. Update minimum distance.
+ See Algorithms for Fast Vector Quantization
+ Sunil Arya and David M. Mount. */
+ box_diff = point_coord[dim] - root->cut_bounds_hv;
+ if (box_diff < 0)
+ {
+ box_diff = 0;
+ }
+ dist_left = min_dist - box_diff * box_diff + new_offset * new_offset;
+ if (dist_left < closest_dist[k - 1] * eps_fac)
+ {
+ /* Search left subtree if minimum distance is below limit*/
+ search_splitnode_${DTYPE}((Node_${DTYPE} *)root->left_child, pa, pidx, no_dims, point_coord, dist_left, k, distance_upper_bound, eps_fac, mask, closest_idx, closest_dist);
+ }
+ }
+}
+
+/************************************************
+Search for nearest neighbour for a set of query points
+Params:
+ tree : Tree struct of kd tree
+ pa : data points
+ pidx : permutation index of data points
+ point_coords : query points
+ num_points : number of query points
+ mask : boolean array of invalid (True) and valid (False) data points
+ closest_idx : index of closest data point found (return)
+ closest_dist : distance to closest point (return)
+************************************************/
+void search_tree_${DTYPE}(Tree_${DTYPE} *tree, ${DTYPE} *pa, ${DTYPE} *point_coords,
+ uint32_t num_points, uint32_t k, ${DTYPE} distance_upper_bound,
+ ${DTYPE} eps, uint8_t *mask, uint32_t *closest_idxs, ${DTYPE} *closest_dists)
+{
+ ${DTYPE} min_dist;
+ ${DTYPE} eps_fac = 1 / ((1 + eps) * (1 + eps));
+ int8_t no_dims = tree->no_dims;
+ ${DTYPE} *bbox = tree->bbox;
+ uint32_t *pidx = tree->pidx;
+ uint32_t j = 0;
+#if defined(_MSC_VER) && defined(_OPENMP)
+ int32_t i = 0;
+ int32_t local_num_points = (int32_t) num_points;
+#else
+ uint32_t i;
+ uint32_t local_num_points = num_points;
+#endif
+ Node_${DTYPE} *root = (Node_${DTYPE} *)tree->root;
+
+ /* Queries are OpenMP enabled */
+ #pragma omp parallel
+ {
+ /* The low chunk size is important to avoid L2 cache trashing
+ for spatial coherent query datasets
+ */
+ #pragma omp for private(i, j) schedule(static, 100) nowait
+ for (i = 0; i < local_num_points; i++)
+ {
+ for (j = 0; j < k; j++)
+ {
+ closest_idxs[i * k + j] = UINT32_MAX;
+ closest_dists[i * k + j] = DBL_MAX;
+ }
+ min_dist = get_min_dist_${DTYPE}(point_coords + no_dims * i, no_dims, bbox);
+ search_splitnode_${DTYPE}(root, pa, pidx, no_dims, point_coords + no_dims * i, min_dist,
+ k, distance_upper_bound, eps_fac, mask, &closest_idxs[i * k], &closest_dists[i * k]);
+ }
+ }
+}
+% endfor
=====================================
pykdtree/kdtree.pyx
=====================================
@@ -0,0 +1,280 @@
+#pykdtree, Fast kd-tree implementation with OpenMP-enabled queries
+#
+#Copyright (C) 2013 - present Esben S. Nielsen
+#
+# This program is free software: you can redistribute it and/or modify it under
+# the terms of the GNU Lesser General Public License as published by the Free
+# Software Foundation, either version 3 of the License, or
+#(at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+# FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
+# details.
+#
+# You should have received a copy of the GNU Lesser General Public License along
+# with this program. If not, see <http://www.gnu.org/licenses/>.
+
+import numpy as np
+cimport numpy as np
+from libc.stdint cimport uint32_t, int8_t, uint8_t
+cimport cython
+
+
+# Node structure
+cdef struct node_float:
+ float cut_val
+ int8_t cut_dim
+ uint32_t start_idx
+ uint32_t n
+ float cut_bounds_lv
+ float cut_bounds_hv
+ node_float *left_child
+ node_float *right_child
+
+cdef struct tree_float:
+ float *bbox
+ int8_t no_dims
+ uint32_t *pidx
+ node_float *root
+
+cdef struct node_double:
+ double cut_val
+ int8_t cut_dim
+ uint32_t start_idx
+ uint32_t n
+ double cut_bounds_lv
+ double cut_bounds_hv
+ node_double *left_child
+ node_double *right_child
+
+cdef struct tree_double:
+ double *bbox
+ int8_t no_dims
+ uint32_t *pidx
+ node_double *root
+
+cdef extern tree_float* construct_tree_float(float *pa, int8_t no_dims, uint32_t n, uint32_t bsp) nogil
+cdef extern void search_tree_float(tree_float *kdtree, float *pa, float *point_coords, uint32_t num_points, uint32_t k, float distance_upper_bound, float eps_fac, uint8_t *mask, uint32_t *closest_idxs, float *closest_dists) nogil
+cdef extern void delete_tree_float(tree_float *kdtree)
+
+cdef extern tree_double* construct_tree_double(double *pa, int8_t no_dims, uint32_t n, uint32_t bsp) nogil
+cdef extern void search_tree_double(tree_double *kdtree, double *pa, double *point_coords, uint32_t num_points, uint32_t k, double distance_upper_bound, double eps_fac, uint8_t *mask, uint32_t *closest_idxs, double *closest_dists) nogil
+cdef extern void delete_tree_double(tree_double *kdtree)
+
+cdef class KDTree:
+ """kd-tree for fast nearest-neighbour lookup.
+ The interface is made to resemble the scipy.spatial kd-tree except
+ only Euclidean distance measure is supported.
+
+ :Parameters:
+ data_pts : numpy array
+ Data points with shape (n , dims)
+ leafsize : int, optional
+ Maximum number of data points in tree leaf
+ """
+
+ cdef tree_float *_kdtree_float
+ cdef tree_double *_kdtree_double
+ cdef readonly np.ndarray data_pts
+ cdef readonly np.ndarray data
+ cdef float *_data_pts_data_float
+ cdef double *_data_pts_data_double
+ cdef readonly uint32_t n
+ cdef readonly int8_t ndim
+ cdef readonly uint32_t leafsize
+
+ def __cinit__(KDTree self):
+ self._kdtree_float = NULL
+ self._kdtree_double = NULL
+
+ def __init__(KDTree self, np.ndarray data_pts not None, int leafsize=16):
+
+ # Check arguments
+ if leafsize < 1:
+ raise ValueError('leafsize must be greater than zero')
+
+ # Get data content
+ cdef np.ndarray[float, ndim=1] data_array_float
+ cdef np.ndarray[double, ndim=1] data_array_double
+
+ if data_pts.dtype == np.float32:
+ data_array_float = np.ascontiguousarray(data_pts.ravel(), dtype=np.float32)
+ self._data_pts_data_float = <float *>data_array_float.data
+ self.data_pts = data_array_float
+ else:
+ data_array_double = np.ascontiguousarray(data_pts.ravel(), dtype=np.float64)
+ self._data_pts_data_double = <double *>data_array_double.data
+ self.data_pts = data_array_double
+
+ # scipy interface compatibility
+ self.data = self.data_pts
+
+ # Get tree info
+ self.n = <uint32_t>data_pts.shape[0]
+ self.leafsize = <uint32_t>leafsize
+ if data_pts.ndim == 1:
+ self.ndim = 1
+ else:
+ self.ndim = <int8_t>data_pts.shape[1]
+
+ # Release GIL and construct tree
+ if data_pts.dtype == np.float32:
+ with nogil:
+ self._kdtree_float = construct_tree_float(self._data_pts_data_float, self.ndim,
+ self.n, self.leafsize)
+ else:
+ with nogil:
+ self._kdtree_double = construct_tree_double(self._data_pts_data_double, self.ndim,
+ self.n, self.leafsize)
+
+
+ def query(KDTree self, np.ndarray query_pts not None, k=1, eps=0,
+ distance_upper_bound=None, sqr_dists=False, mask=None):
+ """Query the kd-tree for nearest neighbors
+
+ :Parameters:
+ query_pts : numpy array
+ Query points with shape (n , dims)
+ k : int
+ The number of nearest neighbours to return
+ eps : non-negative float
+ Return approximate nearest neighbours; the k-th returned value
+ is guaranteed to be no further than (1 + eps) times the distance
+ to the real k-th nearest neighbour
+ distance_upper_bound : non-negative float
+ Return only neighbors within this distance.
+ This is used to prune tree searches.
+ sqr_dists : bool, optional
+ Internally pykdtree works with squared distances.
+ Determines if the squared or Euclidean distances are returned.
+ mask : numpy array, optional
+ Array of booleans where neighbors are considered invalid and
+ should not be returned. A mask value of True represents an
+ invalid pixel. Mask should have shape (n,). By default all
+ points are considered valid.
+
+ """
+
+ # Check arguments
+ if k < 1:
+ raise ValueError('Number of neighbours must be greater than zero')
+ elif eps < 0:
+ raise ValueError('eps must be non-negative')
+ elif distance_upper_bound is not None:
+ if distance_upper_bound < 0:
+ raise ValueError('distance_upper_bound must be non negative')
+
+ # Check dimensions
+ if query_pts.ndim == 1:
+ q_ndim = 1
+ else:
+ q_ndim = query_pts.shape[1]
+
+ if self.ndim != q_ndim:
+ raise ValueError('Data and query points must have same dimensions')
+
+ if self.data_pts.dtype == np.float32 and query_pts.dtype != np.float32:
+ raise TypeError('Type mismatch. query points must be of type float32 when data points are of type float32')
+
+ # Get query info
+ cdef uint32_t num_qpoints = query_pts.shape[0]
+ cdef uint32_t num_n = k
+ cdef np.ndarray[uint32_t, ndim=1] closest_idxs = np.empty(num_qpoints * k, dtype=np.uint32)
+ cdef np.ndarray[float, ndim=1] closest_dists_float
+ cdef np.ndarray[double, ndim=1] closest_dists_double
+
+
+ # Set up return arrays
+ cdef uint32_t *closest_idxs_data = <uint32_t *>closest_idxs.data
+ cdef float *closest_dists_data_float
+ cdef double *closest_dists_data_double
+
+ # Get query points data
+ cdef np.ndarray[float, ndim=1] query_array_float
+ cdef np.ndarray[double, ndim=1] query_array_double
+ cdef float *query_array_data_float
+ cdef double *query_array_data_double
+ cdef np.ndarray[np.uint8_t, ndim=1] query_mask
+ cdef np.uint8_t *query_mask_data
+
+ if mask is not None and mask.size != self.n:
+ raise ValueError('Mask must have the same size as data points')
+ elif mask is not None:
+ query_mask = np.ascontiguousarray(mask.ravel(), dtype=np.uint8)
+ query_mask_data = <uint8_t *>query_mask.data
+ else:
+ query_mask_data = NULL
+
+
+ if query_pts.dtype == np.float32 and self.data_pts.dtype == np.float32:
+ closest_dists_float = np.empty(num_qpoints * k, dtype=np.float32)
+ closest_dists = closest_dists_float
+ closest_dists_data_float = <float *>closest_dists_float.data
+ query_array_float = np.ascontiguousarray(query_pts.ravel(), dtype=np.float32)
+ query_array_data_float = <float *>query_array_float.data
+ else:
+ closest_dists_double = np.empty(num_qpoints * k, dtype=np.float64)
+ closest_dists = closest_dists_double
+ closest_dists_data_double = <double *>closest_dists_double.data
+ query_array_double = np.ascontiguousarray(query_pts.ravel(), dtype=np.float64)
+ query_array_data_double = <double *>query_array_double.data
+
+ # Setup distance_upper_bound
+ cdef float dub_float
+ cdef double dub_double
+ if distance_upper_bound is None:
+ if self.data_pts.dtype == np.float32:
+ dub_float = <float>np.finfo(np.float32).max
+ else:
+ dub_double = <double>np.finfo(np.float64).max
+ else:
+ if self.data_pts.dtype == np.float32:
+ dub_float = <float>(distance_upper_bound * distance_upper_bound)
+ else:
+ dub_double = <double>(distance_upper_bound * distance_upper_bound)
+
+ # Set epsilon
+ cdef double epsilon_float = <float>eps
+ cdef double epsilon_double = <double>eps
+
+ # Release GIL and query tree
+ if self.data_pts.dtype == np.float32:
+ with nogil:
+ search_tree_float(self._kdtree_float, self._data_pts_data_float,
+ query_array_data_float, num_qpoints, num_n, dub_float, epsilon_float,
+ query_mask_data, closest_idxs_data, closest_dists_data_float)
+
+ else:
+ with nogil:
+ search_tree_double(self._kdtree_double, self._data_pts_data_double,
+ query_array_data_double, num_qpoints, num_n, dub_double, epsilon_double,
+ query_mask_data, closest_idxs_data, closest_dists_data_double)
+
+ # Shape result
+ if k > 1:
+ closest_dists_res = closest_dists.reshape(num_qpoints, k)
+ closest_idxs_res = closest_idxs.reshape(num_qpoints, k)
+ else:
+ closest_dists_res = closest_dists
+ closest_idxs_res = closest_idxs
+
+ if distance_upper_bound is not None: # Mark out of bounds results
+ if self.data_pts.dtype == np.float32:
+ idx_out = (closest_dists_res >= dub_float)
+ else:
+ idx_out = (closest_dists_res >= dub_double)
+
+ closest_dists_res[idx_out] = np.Inf
+ closest_idxs_res[idx_out] = self.n
+
+ if not sqr_dists: # Return actual cartesian distances
+ closest_dists_res = np.sqrt(closest_dists_res)
+
+ return closest_dists_res, closest_idxs_res
+
+ def __dealloc__(KDTree self):
+ if self._kdtree_float != NULL:
+ delete_tree_float(self._kdtree_float)
+ elif self._kdtree_double != NULL:
+ delete_tree_double(self._kdtree_double)
=====================================
pykdtree/render_template.py
=====================================
@@ -0,0 +1,7 @@
+#!/usr/bin/env python
+
+from mako.template import Template
+
+mytemplate = Template(filename='_kdtree_core.c.mako')
+with open('_kdtree_core.c', 'w') as fp:
+ fp.write(mytemplate.render())
=====================================
setup.cfg
=====================================
@@ -1,8 +1,5 @@
[bdist_rpm]
-requires = numpy
-release = 1
+requires=numpy
+release=1
-[egg_info]
-tag_build =
-tag_date = 0
View it on GitLab: https://salsa.debian.org/debian-gis-team/pykdtree/-/commit/bd55ef6812b6190f33b18b732982e21c3cf0bdfe
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/pykdtree/-/commit/bd55ef6812b6190f33b18b732982e21c3cf0bdfe
You're receiving this email because of your account on salsa.debian.org.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://alioth-lists.debian.net/pipermail/pkg-grass-devel/attachments/20201013/5846cd36/attachment-0001.html>
More information about the Pkg-grass-devel
mailing list