# pyvoronoi
A wrapper for Boost's Voronoi diagram library. The full documentation of the Boost Voronoi API is available [here](https://www.boost.org/doc/libs/1_75_0/libs/polygon/doc/voronoi_main.htm).
## Install
The installation have been tested on Windows and Linux Ubuntu. If you notice any issue on Mac, reach out to us, we are interested in making sure it works for you.
Windows users will need Microsoft Visual C++ installed on their machine. You can find information about the version needed on [this](https://wiki.python.org/moin/WindowsCompilers) link. Python version from 3.5 to 3.12 rely on Visual C++ 14.x.
### Dependencies
Cython dependency is optional. Cpp sources generated with Cython are available in releases.
Note on using the setup.py:
setup.py operates in 2 modes that are based on the presence of the dev file in the root of the project.
* When dev is **present**, Cython will be used to compile the .pyx sources. This is the development mode (as you get it in the git repository).
* When dev is **absent**, C/C++ compiler will be used to compile the .cpp sources (that were prepared in in the development mode). This is the distribution mode (as you get it on PyPI).
This way the package can be used without or with an incompatible version of Cython.
The idea comes from Matt Shannon's bandmat library.
### From PyPI
Cython not required.
``pip install pyvoronoi``
### From source
Cython required.
Clone the repository:
``git clone https://github.com/fabanc/pyvoronoi.git``
Install the development dependencies:
`pip install -requirements_dev.txt`
Install:
``python setup.py install``
After every modification of .pyx files compile with Cython:
``python setup.py build_ext --inplace``
Note in order to build the wheels, you will need to also install ``wheel``
``pip install wheel``
### Using
Create a new instance, passing the scaling factor into the constructor:
```
import pyvoronoi
pv = pyvoronoi.Pyvoronoi(10)
```
Since the voronoi library uses integer representation for points, the scaling factor chosen must be high enough
to avoid roundoff error when converting from point coordinates to integers.
Add points and segments:
```python
pv.AddPoint([0, 0])
pv.AddSegment([[1,5],[2,2]])
```
Call ``Construct()`` and get the edges and vertices:
```python
pv.Construct()
edges = pv.GetEdges()
vertices = pv.GetVertices()
cells = pv.GetCells()
```
Note that vertices, edges, and cells, can be accessed individually. The methods above are just convenience wrappers around
the following functions:
* GetVertex
* GetEdge
* Get Cell
```python
def GetVertices(self):
count = self.CountVertices()
output = []
for index in range(count):
output.append(self.GetVertex(index))
return output
```
```python
def GetEdges(self):
count = self.CountEdges()
output = []
for index in range(count):
output.append(self.GetEdge(index))
return output
```
```python
def GetCells(self):
count = self.CountCells()
output = []
for index in range(count):
output.append(self.GetCell(index))
return output
```
If you are running python 2.x, you might want to write your own wrappers using xrange. This will be more efficient.
Edges have the following properties:
* ``start, end`` contain the indices of the start and end vertices or ``-1`` if the edge is infinite at that end.
* ``is_primary`` is true if the edge is not coincident with any of the source inputs.
* ``is_linear`` is true if the edge is linear (not curved).
* ``cell`` is the identifier of the cell this segment is part of.
* ``twin`` is the identifier of the twin segment as defined in the boost voronoi API.
Cells have the following properties:
* ``cell_identifier`` is the index of the cell.
* ``site`` is the index of the site which generated this cell (same as site1, site2 on the edges).
* ``contains_point`` is true if the site was generated by a point.
* ``contains_segment`` is true if the site was generated by a segment.
* ``is_open`` is true if any of the cell's edges is infinite.
* ``is_degenerate`` is true if the cell doesn't have an incident edge. Can happen if a few input segments share a common endpoint.
* ``vertices`` contains indices into the vertex array.
* ``edges`` contains indices into the edge array.
```python
pv = pyvoronoi.Pyvoronoi(100)
pv.AddSegment([[0.1,0.8],[0.3,0.6]])
pv.AddSegment([[0.3,0.6],[0.4,0.6]])
pv.AddSegment([[0.4,0.6],[0.4,0.5]])
pv.AddSegment([[0.4,0.6],[0.4,0.7]])
pv.AddSegment([[0.4,0.7],[0.5,0.8]])
pv.AddSegment([[0.4,0.7],[0.5,0.6]])
pv.AddSegment([[0.5,0.6],[0.7,0.7]])
pv.Construct()
edges = pv.GetEdges()
vertices = pv.GetVertices()
cells = pv.GetCells()
print("Cell Count: {0}".format(len(cells)))
for c in cells:
print("Cell contains point: {0}. Contains segment: {1}. Is open: {2}, Site Index: {3}".format(c.contains_point, c.contains_segment, c.is_open, c.site))
print(",".join(map(str,c.vertices)))
for sIndex in c.edges:
print("Start Index: {0}, End Index = {1}".format(edges[sIndex].start, edges[sIndex].end))
```
Note that since version 1.0.4 each of the Get function has an equivalent function that returns an iterator. This is more memory friendly.
|Goal|Return a list|Return an iterator|
| - | - | - |
| Return vertices | GetVertices | IterateVertices |
| Return edges | GetEdges | IterateEdges |
| Return cells | GetCells | IterateCells |
They are functionaly equivalent as defined in this automated test:
```python
def test_iterators(self):
pv = pyvoronoi.Pyvoronoi(1)
pv.AddPoint([5,5])
pv.AddSegment([[0,0],[0,10]])
pv.AddSegment([[0,0],[10,0]])
pv.AddSegment([[0,10],[10,10]])
pv.AddSegment([[10,0],[10,10]])
pv.Construct()
vertices = pv.GetVertices()
vertex_generator = pv.IterateVertices()
for v in vertices:
v_generator = next(vertex_generator)
self.assertEqual(v, v_generator)
edges = pv.GetEdges()
edge_generator = pv.IterateEdges()
for e in edges:
e_generator = next(edge_generator)
self.assertEqual(e, e_generator)
cells = pv.GetCells()
cell_generator = pv.IterateCells()
for c in cells:
c_generator = next(cell_generator)
self.assertEqual(c, c_generator)
```
Some output edges returned by the boost voronoi API are suposed to be curved. In the C++ API, it is up to you to code it. Luckily, you can do it in python using the following the function DiscretizeCurvedEdge.
The sample below shows you how to do that:
```python
for cIndex in range(len(cells)):
cell = cells[cIndex]
if cell.is_open == False:
for i in range(len(cell.edges)):
e = edges[cell.edges[i]]
startVertex = vertices[e.start]
endVertex = vertices[e.end]
max_distance = distance([startVertex.X, startVertex.Y], [endVertex.X, endVertex.Y]) / 10
if startVertex != -1 and endVertex != -1:
if(e.is_linear == True):
array = [[startVertex.X, startVertex.Y],[endVertex.X, endVertex.Y]]
else:
points = pv.DiscretizeCurvedEdge(i, max_distance)
for p in points:
print "{0},{1}".format(p[0], p[1])
```
The curve interpolation code can return 2 exceptions.
* FocusOnDirectixException: this happens when the input point is on the segment side. In that cases, it makes no sense to interpolate a parabola between those two geometries since a parabola equation is supposed to find an equidistant point between the two geometries.
* UnsolvableParabolaEquation: there are cases where the point returned by boost does not fit with the parabola equation (for a same position on the x-axis, we get 2 different points, both equidistant). Understanding this issue is still under investigation. It is possible to mitigate this issue by setting an optional 3rd parameter of the function DiscretizeCurvedEdge). A higher value means more tolerance to this exception. The recommended value would be 1 / Scaling Factor.
# License
- Pyvoronoi is available under `MIT
license <http://opensource.org/licenses/MIT>`__.
- The core Voronoi library is available under `Boost Software
License <http://www.boost.org/LICENSE_1_0.txt>`__. Freeware for both
open source and commercial applications.
Raw data
{
"_id": null,
"home_page": "https://github.com/fabanc/pyvoronoi",
"name": "pyvoronoi",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "voronoi, Boost, polygon",
"author": "Fabien Ancelin / Andrii Sydorchuk, Voxel8",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/fe/4a/5ddc3d025f6806d0b085c713f6940185676425a71b09e7d425b53cbf4449/pyvoronoi-1.1.0.tar.gz",
"platform": null,
"description": "\n# pyvoronoi\n\nA wrapper for Boost's Voronoi diagram library. The full documentation of the Boost Voronoi API is available [here](https://www.boost.org/doc/libs/1_75_0/libs/polygon/doc/voronoi_main.htm).\n\n## Install\n\nThe installation have been tested on Windows and Linux Ubuntu. If you notice any issue on Mac, reach out to us, we are interested in making sure it works for you.\n\nWindows users will need Microsoft Visual C++ installed on their machine. You can find information about the version needed on [this](https://wiki.python.org/moin/WindowsCompilers) link. Python version from 3.5 to 3.12 rely on Visual C++ 14.x.\n\n### Dependencies\n\nCython dependency is optional. Cpp sources generated with Cython are available in releases.\n\nNote on using the setup.py:\n\nsetup.py operates in 2 modes that are based on the presence of the dev file in the root of the project.\n\n* When dev is **present**, Cython will be used to compile the .pyx sources. This is the development mode (as you get it in the git repository).\n\n* When dev is **absent**, C/C++ compiler will be used to compile the .cpp sources (that were prepared in in the development mode). This is the distribution mode (as you get it on PyPI).\n\nThis way the package can be used without or with an incompatible version of Cython.\n\nThe idea comes from Matt Shannon's bandmat library.\n\n### From PyPI\n\n\nCython not required.\n\n``pip install pyvoronoi``\n\n### From source\n\n\nCython required.\n\nClone the repository:\n\n``git clone https://github.com/fabanc/pyvoronoi.git``\n\n\nInstall the development dependencies:\n\n`pip install -requirements_dev.txt`\n\nInstall:\n\n``python setup.py install``\n\nAfter every modification of .pyx files compile with Cython:\n\n``python setup.py build_ext --inplace``\n\nNote in order to build the wheels, you will need to also install ``wheel``\n\n``pip install wheel``\n\n### Using\n\n\nCreate a new instance, passing the scaling factor into the constructor:\n```\nimport pyvoronoi\npv = pyvoronoi.Pyvoronoi(10)\n```\n\nSince the voronoi library uses integer representation for points, the scaling factor chosen must be high enough\nto avoid roundoff error when converting from point coordinates to integers.\n\nAdd points and segments:\n\n```python\npv.AddPoint([0, 0])\npv.AddSegment([[1,5],[2,2]])\n```\n\nCall ``Construct()`` and get the edges and vertices:\n\n\n```python\npv.Construct()\nedges = pv.GetEdges()\nvertices = pv.GetVertices()\ncells = pv.GetCells()\n```\n\nNote that vertices, edges, and cells, can be accessed individually. The methods above are just convenience wrappers around\nthe following functions:\n\n* GetVertex\n\n* GetEdge\n\n* Get Cell\n\n```python\ndef GetVertices(self):\n count = self.CountVertices()\n output = []\n for index in range(count):\n output.append(self.GetVertex(index))\n return output\n```\n\n```python\ndef GetEdges(self):\n count = self.CountEdges()\n output = []\n for index in range(count):\n output.append(self.GetEdge(index))\n return output\n```\n\n```python\ndef GetCells(self):\n count = self.CountCells()\n output = []\n for index in range(count):\n output.append(self.GetCell(index))\n return output\n```\n\nIf you are running python 2.x, you might want to write your own wrappers using xrange. This will be more efficient.\n\nEdges have the following properties:\n\n* ``start, end`` contain the indices of the start and end vertices or ``-1`` if the edge is infinite at that end.\n* ``is_primary`` is true if the edge is not coincident with any of the source inputs.\n* ``is_linear`` is true if the edge is linear (not curved).\n* ``cell`` is the identifier of the cell this segment is part of.\n* ``twin`` is the identifier of the twin segment as defined in the boost voronoi API.\n\nCells have the following properties:\n\n* ``cell_identifier`` is the index of the cell.\n* ``site`` is the index of the site which generated this cell (same as site1, site2 on the edges).\n* ``contains_point`` is true if the site was generated by a point.\n* ``contains_segment`` is true if the site was generated by a segment.\n* ``is_open`` is true if any of the cell's edges is infinite.\n* ``is_degenerate`` is true if the cell doesn't have an incident edge. Can happen if a few input segments share a common endpoint.\n* ``vertices`` contains indices into the vertex array.\n* ``edges`` contains indices into the edge array.\n\n```python\npv = pyvoronoi.Pyvoronoi(100)\npv.AddSegment([[0.1,0.8],[0.3,0.6]])\npv.AddSegment([[0.3,0.6],[0.4,0.6]])\npv.AddSegment([[0.4,0.6],[0.4,0.5]])\npv.AddSegment([[0.4,0.6],[0.4,0.7]])\npv.AddSegment([[0.4,0.7],[0.5,0.8]])\npv.AddSegment([[0.4,0.7],[0.5,0.6]])\npv.AddSegment([[0.5,0.6],[0.7,0.7]])\n\npv.Construct()\nedges = pv.GetEdges()\nvertices = pv.GetVertices()\ncells = pv.GetCells()\nprint(\"Cell Count: {0}\".format(len(cells)))\nfor c in cells:\n print(\"Cell contains point: {0}. Contains segment: {1}. Is open: {2}, Site Index: {3}\".format(c.contains_point, c.contains_segment, c.is_open, c.site))\n print(\",\".join(map(str,c.vertices)))\n for sIndex in c.edges:\n print(\"Start Index: {0}, End Index = {1}\".format(edges[sIndex].start, edges[sIndex].end))\n```\n\nNote that since version 1.0.4 each of the Get function has an equivalent function that returns an iterator. This is more memory friendly.\n\n|Goal|Return a list|Return an iterator|\n| - | - | - |\n| Return vertices | GetVertices | IterateVertices |\n| Return edges | GetEdges | IterateEdges |\n| Return cells | GetCells | IterateCells |\n\nThey are functionaly equivalent as defined in this automated test:\n\n```python\n def test_iterators(self):\n pv = pyvoronoi.Pyvoronoi(1)\n pv.AddPoint([5,5])\n pv.AddSegment([[0,0],[0,10]])\n pv.AddSegment([[0,0],[10,0]])\n pv.AddSegment([[0,10],[10,10]])\n pv.AddSegment([[10,0],[10,10]])\n pv.Construct()\n\n vertices = pv.GetVertices()\n vertex_generator = pv.IterateVertices()\n for v in vertices:\n v_generator = next(vertex_generator)\n self.assertEqual(v, v_generator)\n\n edges = pv.GetEdges()\n edge_generator = pv.IterateEdges()\n for e in edges:\n e_generator = next(edge_generator)\n self.assertEqual(e, e_generator)\n\n cells = pv.GetCells()\n cell_generator = pv.IterateCells()\n for c in cells:\n c_generator = next(cell_generator)\n self.assertEqual(c, c_generator)\n```\n\n\nSome output edges returned by the boost voronoi API are suposed to be curved. In the C++ API, it is up to you to code it. Luckily, you can do it in python using the following the function DiscretizeCurvedEdge.\nThe sample below shows you how to do that:\n\n```python\nfor cIndex in range(len(cells)):\n cell = cells[cIndex]\n if cell.is_open == False:\n for i in range(len(cell.edges)):\n e = edges[cell.edges[i]]\n startVertex = vertices[e.start]\n endVertex = vertices[e.end]\n\n max_distance = distance([startVertex.X, startVertex.Y], [endVertex.X, endVertex.Y]) / 10\n if startVertex != -1 and endVertex != -1:\n if(e.is_linear == True):\n array = [[startVertex.X, startVertex.Y],[endVertex.X, endVertex.Y]]\n else:\n points = pv.DiscretizeCurvedEdge(i, max_distance)\n for p in points:\n print \"{0},{1}\".format(p[0], p[1])\n```\n\nThe curve interpolation code can return 2 exceptions.\n\n* FocusOnDirectixException: this happens when the input point is on the segment side. In that cases, it makes no sense to interpolate a parabola between those two geometries since a parabola equation is supposed to find an equidistant point between the two geometries.\n\n* UnsolvableParabolaEquation: there are cases where the point returned by boost does not fit with the parabola equation (for a same position on the x-axis, we get 2 different points, both equidistant). Understanding this issue is still under investigation. It is possible to mitigate this issue by setting an optional 3rd parameter of the function DiscretizeCurvedEdge). A higher value means more tolerance to this exception. The recommended value would be 1 / Scaling Factor.\n\n# License\n\n- Pyvoronoi is available under `MIT\n license <http://opensource.org/licenses/MIT>`__.\n- The core Voronoi library is available under `Boost Software\n License <http://www.boost.org/LICENSE_1_0.txt>`__. Freeware for both\n open source and commercial applications.\n\n\n",
"bugtrack_url": null,
"license": null,
"summary": "Cython wrapper for the Boost Voronoi library (version 1.59.0)",
"version": "1.1.0",
"project_urls": {
"Homepage": "https://github.com/fabanc/pyvoronoi"
},
"split_keywords": [
"voronoi",
" boost",
" polygon"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "fe4a5ddc3d025f6806d0b085c713f6940185676425a71b09e7d425b53cbf4449",
"md5": "1b8d5d48c0bef2e48c538adef3f7f7b3",
"sha256": "001debb47b9dcf8c6a2eecf7512991575d113ed236aeccce742b06a099543717"
},
"downloads": -1,
"filename": "pyvoronoi-1.1.0.tar.gz",
"has_sig": false,
"md5_digest": "1b8d5d48c0bef2e48c538adef3f7f7b3",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 195112,
"upload_time": "2024-04-18T23:40:21",
"upload_time_iso_8601": "2024-04-18T23:40:21.304954Z",
"url": "https://files.pythonhosted.org/packages/fe/4a/5ddc3d025f6806d0b085c713f6940185676425a71b09e7d425b53cbf4449/pyvoronoi-1.1.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-18 23:40:21",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "fabanc",
"github_project": "pyvoronoi",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "setuptools",
"specs": []
}
],
"lcname": "pyvoronoi"
}
JSON
