Numba Celltree
==============
.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square
:target: https://github.com/deltares/numba_celltree/actions?query=workflows%3Aci
.. image:: https://img.shields.io/codecov/c/github/deltares/numba_celltree.svg?style=flat-square
:target: https://app.codecov.io/gh/deltares/numba_celltree
.. image:: https://img.shields.io/badge/code%20style-black-000000.svg?style=flat-square
:target: https://github.com/psf/black
Finding your way around in an unstructured meshes is difficult. Numba Celltree
provides methods for searching for points, lines, boxes, and cells (convex
polygons) in a two dimensional unstructured mesh.
.. code:: python
import numpy as np
from numba_celltree import CellTree2d
vertices, faces = demo.generate_disk(5, 5)
vertices += 1.0
vertices *= 5.0
tree = CellTree2d(vertices, faces, -1)
# Intersection with two triangles
triangle_vertices = np.array(
[
[5.0, 3.0],
[7.0, 3.0],
[7.0, 5.0],
[0.0, 6.0],
[4.0, 4.0],
[6.0, 10.0],
]
)
triangles = np.array([[0, 1, 2], [3, 4, 5]])
tri_i, cell_i, area = tree.intersect_faces(triangle_vertices, triangles, -1)
# Intersection with two lines
edge_coords = np.array(
[
[[0.0, 0.0], [10.0, 10.0]],
[[0.0, 10.0], [10.0, 0.0]],
]
)
edge_i, cell_i, intersections = tree.intersect_edges(edge_coords)
.. image:: https://raw.githubusercontent.com/Deltares/numba_celltree/main/docs/_static/intersection-example.svg
:target: https://github.com/deltares/numba_celltree
Installation
------------
.. code:: console
pip install numba_celltree
Documentation
-------------
.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/docs.yml?style=flat-square
:target: https://deltares.github.io/numba_celltree/
Background
----------
This package provides the cell tree data structure described in:
Garth, C., & Joy, K. I. (2010). Fast, memory-efficient cell location in
unstructured grids for visualization. IEEE Transactions on Visualization and
Computer Graphics, 16(6), 1541-1550.
This paper can be read `here
<https://escholarship.org/content/qt0vq7q87f/qt0vq7q87f.pdf>`_.
The tree building code is a direction translation of the (public domain) `C++
code
<https://github.com/NOAA-ORR-ERD/cell_tree2d/blob/master/src/cell_tree2d.cpp>`_
by Jay Hennen, which is available in the `cell_tree2d
<https://github.com/NOAA-ORR-ERD/cell_tree2d>`_ python package. This
implementation is currently specialized for two spatial dimensions, but
extension to three dimensions is relatively straightforward. Another (BSD
licensed) implementation which supports three dimensions can be found in VTK's
`CellTreeLocator
<https://vtk.org/doc/nightly/html/classvtkCellTreeLocator.html>`_.
The cell tree of the ``cell_tree2d`` currently only locates points. I've added
additional methods for locating and clipping lines and convex polygons.
Just-In-Time Compilation: Numba
-------------------------------
This package relies on `Numba <https://numba.pydata.org/>`_ to just-in-time
compile Python code into fast machine code. This has the benefit of keeping
this package a "pure" Python package, albeit with a dependency on Numba.
With regards to performance:
* Building the tree is marginally faster compared to the C++ implementation
(~15%).
* Serial point queries are somewhat slower (~50%), but Numba's automatic
parallellization speeds things up significantly (down to 20% runtime on my 4
core laptop). (Of course the C++ code can be parallellized in the same manner
with ``pragma omp parallel for``.)
* The other queries have not been compared, as the C++ code lacks the
functionality.
* In traversing the tree, recursion in Numba appears to be less performant than
maintaining a stack of nodes to traverse. The VTK implementation also uses
a stack rather than recursion.
* Numba (like its `LLVM JIT sister Julia <https://julialang.org/>`_) does not
allocate small arrays on the stack automatically, like C++ and Fortran
compilers do. However, it can be done `manually
<https://github.com/numba/numba/issues/5084>`_. This cuts down runtimes by
at least a factor 2, more so in parallel. However, these stack allocated
arrays work only in the context of Numba. They must be disabled when running
in uncompiled Python -- there is some code in ``numba_celltree.utils`` which
takes care of this.
* All methods have been carefully written to keep heap allocations to a
minimum. This also helps in parallellization, as at the time of writing
Numba's lists are `not thread safe
<https://github.com/numba/numba/issues/5878>`_. Unfortunately, this means we
have to query twice when the number of answers is unknown: once to count,
after which we can allocate, then another time to store the answers. Since
parallelization results in speedups over a factor 2, this still results in a
net gain.
To debug, set the environmental variable ``NUMBA_DISABLE_JIT=1``. Re-enable by
setting ``NUMBA_DISABLE_JIT=0``.
.. code:: bash
export NUMBA_DISABLE_JIT=1
In Windows Command Prompt:
.. code:: console
set NUMBA_DISABLE_JIT=1
In Windows Powershell:
.. code:: console
$env:NUMBA_DISABLE_JIT=1
In Python itself:
.. code:: python
import os
os.environ["NUMBA_DISABLE_JIT"] = "1"
This must be done before importing the package to have effect.
Raw data
{
"_id": null,
"home_page": "",
"name": "numba-celltree",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "Huite Bootsma <huite.bootsma@deltares.nl>",
"keywords": "mesh,spatial index,ugrid,unstructured grid",
"author": "",
"author_email": "",
"download_url": "https://files.pythonhosted.org/packages/bc/82/6aaf4441b35c6aef25435e64d6ffd4919c794114849a687807f555cb5c9c/numba_celltree-0.1.6.tar.gz",
"platform": null,
"description": "Numba Celltree\r\n==============\r\n\r\n.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/ci.yml?style=flat-square\r\n :target: https://github.com/deltares/numba_celltree/actions?query=workflows%3Aci\r\n.. image:: https://img.shields.io/codecov/c/github/deltares/numba_celltree.svg?style=flat-square\r\n :target: https://app.codecov.io/gh/deltares/numba_celltree\r\n.. image:: https://img.shields.io/badge/code%20style-black-000000.svg?style=flat-square\r\n :target: https://github.com/psf/black\r\n\r\nFinding your way around in an unstructured meshes is difficult. Numba Celltree\r\nprovides methods for searching for points, lines, boxes, and cells (convex\r\npolygons) in a two dimensional unstructured mesh.\r\n\r\n.. code:: python\r\n\r\n import numpy as np\r\n from numba_celltree import CellTree2d\r\n\r\n\r\n vertices, faces = demo.generate_disk(5, 5)\r\n vertices += 1.0\r\n vertices *= 5.0\r\n tree = CellTree2d(vertices, faces, -1)\r\n\r\n # Intersection with two triangles\r\n triangle_vertices = np.array(\r\n [\r\n [5.0, 3.0],\r\n [7.0, 3.0],\r\n [7.0, 5.0],\r\n [0.0, 6.0],\r\n [4.0, 4.0],\r\n [6.0, 10.0],\r\n ]\r\n )\r\n triangles = np.array([[0, 1, 2], [3, 4, 5]])\r\n tri_i, cell_i, area = tree.intersect_faces(triangle_vertices, triangles, -1)\r\n\r\n # Intersection with two lines\r\n edge_coords = np.array(\r\n [\r\n [[0.0, 0.0], [10.0, 10.0]],\r\n [[0.0, 10.0], [10.0, 0.0]],\r\n ]\r\n )\r\n edge_i, cell_i, intersections = tree.intersect_edges(edge_coords)\r\n\r\n.. image:: https://raw.githubusercontent.com/Deltares/numba_celltree/main/docs/_static/intersection-example.svg\r\n :target: https://github.com/deltares/numba_celltree\r\n\r\nInstallation\r\n------------\r\n\r\n.. code:: console\r\n\r\n pip install numba_celltree\r\n \r\nDocumentation\r\n-------------\r\n\r\n.. image:: https://img.shields.io/github/actions/workflow/status/deltares/numba_celltree/docs.yml?style=flat-square\r\n :target: https://deltares.github.io/numba_celltree/\r\n\r\nBackground\r\n----------\r\n\r\nThis package provides the cell tree data structure described in:\r\n\r\nGarth, C., & Joy, K. I. (2010). Fast, memory-efficient cell location in\r\nunstructured grids for visualization. IEEE Transactions on Visualization and\r\nComputer Graphics, 16(6), 1541-1550.\r\n\r\nThis paper can be read `here\r\n<https://escholarship.org/content/qt0vq7q87f/qt0vq7q87f.pdf>`_.\r\n\r\nThe tree building code is a direction translation of the (public domain) `C++\r\ncode\r\n<https://github.com/NOAA-ORR-ERD/cell_tree2d/blob/master/src/cell_tree2d.cpp>`_\r\nby Jay Hennen, which is available in the `cell_tree2d\r\n<https://github.com/NOAA-ORR-ERD/cell_tree2d>`_ python package. This\r\nimplementation is currently specialized for two spatial dimensions, but\r\nextension to three dimensions is relatively straightforward. Another (BSD\r\nlicensed) implementation which supports three dimensions can be found in VTK's\r\n`CellTreeLocator\r\n<https://vtk.org/doc/nightly/html/classvtkCellTreeLocator.html>`_.\r\n\r\nThe cell tree of the ``cell_tree2d`` currently only locates points. I've added\r\nadditional methods for locating and clipping lines and convex polygons.\r\n\r\nJust-In-Time Compilation: Numba\r\n-------------------------------\r\n\r\nThis package relies on `Numba <https://numba.pydata.org/>`_ to just-in-time\r\ncompile Python code into fast machine code. This has the benefit of keeping\r\nthis package a \"pure\" Python package, albeit with a dependency on Numba.\r\n\r\nWith regards to performance:\r\n\r\n* Building the tree is marginally faster compared to the C++ implementation\r\n (~15%).\r\n* Serial point queries are somewhat slower (~50%), but Numba's automatic\r\n parallellization speeds things up significantly (down to 20% runtime on my 4\r\n core laptop). (Of course the C++ code can be parallellized in the same manner\r\n with ``pragma omp parallel for``.)\r\n* The other queries have not been compared, as the C++ code lacks the\r\n functionality.\r\n* In traversing the tree, recursion in Numba appears to be less performant than\r\n maintaining a stack of nodes to traverse. The VTK implementation also uses\r\n a stack rather than recursion.\r\n* Numba (like its `LLVM JIT sister Julia <https://julialang.org/>`_) does not\r\n allocate small arrays on the stack automatically, like C++ and Fortran\r\n compilers do. However, it can be done `manually\r\n <https://github.com/numba/numba/issues/5084>`_. This cuts down runtimes by\r\n at least a factor 2, more so in parallel. However, these stack allocated\r\n arrays work only in the context of Numba. They must be disabled when running\r\n in uncompiled Python -- there is some code in ``numba_celltree.utils`` which\r\n takes care of this.\r\n* All methods have been carefully written to keep heap allocations to a\r\n minimum. This also helps in parallellization, as at the time of writing\r\n Numba's lists are `not thread safe\r\n <https://github.com/numba/numba/issues/5878>`_. Unfortunately, this means we\r\n have to query twice when the number of answers is unknown: once to count,\r\n after which we can allocate, then another time to store the answers. Since\r\n parallelization results in speedups over a factor 2, this still results in a\r\n net gain.\r\n\r\nTo debug, set the environmental variable ``NUMBA_DISABLE_JIT=1``. Re-enable by\r\nsetting ``NUMBA_DISABLE_JIT=0``.\r\n\r\n.. code:: bash\r\n\r\n export NUMBA_DISABLE_JIT=1\r\n\r\nIn Windows Command Prompt:\r\n\r\n.. code:: console\r\n\r\n set NUMBA_DISABLE_JIT=1\r\n\r\nIn Windows Powershell:\r\n\r\n.. code:: console\r\n\r\n $env:NUMBA_DISABLE_JIT=1\r\n\r\nIn Python itself:\r\n\r\n.. code:: python\r\n\r\n import os\r\n\r\n os.environ[\"NUMBA_DISABLE_JIT\"] = \"1\"\r\n\r\nThis must be done before importing the package to have effect. \r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Cell Tree Spatial Index",
"version": "0.1.6",
"split_keywords": [
"mesh",
"spatial index",
"ugrid",
"unstructured grid"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "bc826aaf4441b35c6aef25435e64d6ffd4919c794114849a687807f555cb5c9c",
"md5": "c91c8b930988ae5ae923d05a07e54d01",
"sha256": "2bfc722e0e039e73ac04c3cd7151309c12f57f1d7d9b68fbc206aeb0d0ce665b"
},
"downloads": -1,
"filename": "numba_celltree-0.1.6.tar.gz",
"has_sig": false,
"md5_digest": "c91c8b930988ae5ae923d05a07e54d01",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 30461,
"upload_time": "2023-01-03T17:50:36",
"upload_time_iso_8601": "2023-01-03T17:50:36.800488Z",
"url": "https://files.pythonhosted.org/packages/bc/82/6aaf4441b35c6aef25435e64d6ffd4919c794114849a687807f555cb5c9c/numba_celltree-0.1.6.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-03 17:50:36",
"github": false,
"gitlab": false,
"bitbucket": false,
"lcname": "numba-celltree"
}
JSON