| Name | py_straight_skeleton JSON |
| Version |
0.1.0
JSON |
| download |
| home_page | None |
| Summary | Compute the straight skeleton of a polygon and its resulting polygonal faces. |
| upload_time | 2024-12-20 23:29:32 |
| maintainer | None |
| docs_url | None |
| author | Raul Sampedro |
| requires_python | <4.0,>=3.10 |
| license | 3-Clause BSD |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# py_straight_skeleton
Implementation of [Straight Skeleton](https://en.wikipedia.org/wiki/Straight_skeleton) computation, with minimal
dependencies.
To the best of our knowledge, our **results compete or surpass** some of the top libraries to compute straight skeletons
of simple polygons. By "surpassing" we mean that, in our tests, our library can properly support polygons that other
libraries can not.
Please note, however, that the code is designed for readability and ease of use, and not necessarily for
runtime **performance**.
Our implementation uses a novel modification of _Felkel, Petr & Obdržálek, Štěpán (1998)_ algorithm, to address some shortcomings found during its evaluation, which failed to compute proper skeletons for several of our test cases.
Input | Result
:---------------------------------------:|:---------------------------------------:
 | 
## Usage
```text
📝 Note: We use (+X right, +Y up) axes as our coordinate system.
```
```python
# Define your polygon (counter-clockwise) with optional holes (clockwise).
TEST_EXTERIOR = [[0, 0], [4, 0], [4, -2], [6, -2], [6, 0], [10, 0], [10, 10], [0, 10]]
TEST_HOLES = [[[4, 6], [6, 6], [6, 4], [4, 4]]]
from py_straight_skeleton import compute_skeleton
skeleton = compute_skeleton(exterior=TEST_EXTERIOR, holes=TEST_HOLES)
```
Check [examples/demo.ipynb](examples/demo.ipynb) for a full example with plotting and skeleton parsing.
Skeleton parsing is generally done via three methods:
```python
#
# @property
# nodes(self) -> list[SkeletonNode]:
#
print(skeleton.nodes)
[SKN(0, 0.000, 0.000, 0.00000), SKN(1, 4.000, 0.000, 0.00000), SKN(2, 4.000, -2.000, 0.00000), SKN(3, 6.000, -2.000, 0.00000), SKN(4, 6.000, 0.000, 0.00000), SKN(5, 10.000, 0.000, 0.00000), SKN(6, 10.000, 10.000, 0.00000), SKN(7, 0.000, 10.000, 0.00000), SKN(8, 4.000, 6.000, 0.00000), SKN(9, 6.000, 6.000, 0.00000), SKN(10, 6.000, 4.000, 0.00000), SKN(11, 4.000, 4.000, 0.00000), SKN(12, 5.000, -1.000, 1.00000), SKN(13, 5.000, 1.000, 1.00000), SKN(14, 2.000, 8.000, 2.00000), SKN(15, 8.000, 8.000, 2.00000), SKN(16, 8.000, 2.000, 2.00000), SKN(17, 2.000, 2.000, 2.00000), SKN(18, 5.000, 2.000, 2.00000)]
#
# get_faces(self) -> list[SkeletonFace]
#
for face_idx, face in enumerate(skeleton.get_faces()):
nodes_pos = [skeleton.nodes[v_idx].position for v_idx in face]
print(f"face {face_idx} -> {nodes_pos}")
face 0 -> [Vector2(0.000, 0.000), Vector2(4.000, 0.000), ...]
face 1 -> [Vector2(4.000, 0.000), Vector2(4.000, -2.000), ...]
face 2 -> [Vector2(4.000, -2.000), Vector2(6.000, -2.000), ...]
face 3 -> [Vector2(6.000, -2.000), ...]
...
face 11 -> [Vector2(4.000, 4.000), Vector2(4.000, 6.000), ...]
#
# arc_iterator(self) -> Iterator[tuple[SkeletonNode, SkeletonNode]]
#
for skv1, skv2 in skeleton.arc_iterator():
print(f"{skv1.position} -> {skv2.position}")
Vector2(4.000, -2.000) -> Vector2(5.000, -1.000)
Vector2(6.000, -2.000) -> Vector2(5.000, -1.000)
Vector2(6.000, 0.000) -> Vector2(5.000, 1.000)
...
Vector2(8.000, 2.000) -> Vector2(5.000, 2.000)
Vector2(2.000, 2.000) -> Vector2(5.000, 2.000)
```
## Visualization
The [plotting module](src/py_straight_skeleton/plotting.py) provides several utilities to plot results and intermediate
steps of the algorithm for debugging and verification.
Eg:
```python
# skeleton = ...
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(4, 4))
ax.set_aspect("equal")
from py_straight_skeleton.plotting import Utils
Utils.plot_skeleton(skeleton, ax=ax, show_vertex_info=True)
fig.savefig("output.png")
```
## Debugging
The [plotting module](src/py_straight_skeleton/plotting.py) also provides a `PlotTracer` that can help debug steps,
although we encourage opening issues in the repository for help if necessary.
```python
import logging
from py_straight_skeleton import compute_skeleton
from py_straight_skeleton.algorithm import set_global_algorithm_tracer
from py_straight_skeleton.plotting import PlotTracer
# Define your polygon (counter-clockwise) with optional holes (clockwise).
TEST_EXTERIOR = [[0, 0], [4, 0], [4, -2], [6, -2], [6, 0], [10, 0], [10, 10], [0, 10]]
TEST_HOLES = [[[4, 6], [6, 6], [6, 4], [4, 4]]]
# Set plot tracer to be notified by the algorithm steps and output to a folder.
plot_tracer = PlotTracer(
fig_cs=2.5,
step_fig_ncols=3,
step_fig_nrows=3,
log_level=logging.INFO,
output_dir="examples/plot_tracer_output/",
)
set_global_algorithm_tracer(plot_tracer)
skeleton = compute_skeleton(exterior=TEST_EXTERIOR, holes=TEST_HOLES)
```
Raw data
{
"_id": null,
"home_page": null,
"name": "py_straight_skeleton",
"maintainer": null,
"docs_url": null,
"requires_python": "<4.0,>=3.10",
"maintainer_email": null,
"keywords": null,
"author": "Raul Sampedro",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/a6/4f/294a289ff07f22df4c10e6408adf4af1532620d77bce2063faa19b342e70/py_straight_skeleton-0.1.0.tar.gz",
"platform": null,
"description": "# py_straight_skeleton\n\nImplementation of [Straight Skeleton](https://en.wikipedia.org/wiki/Straight_skeleton) computation, with minimal\ndependencies.\n\nTo the best of our knowledge, our **results compete or surpass** some of the top libraries to compute straight skeletons\nof simple polygons. By \"surpassing\" we mean that, in our tests, our library can properly support polygons that other\nlibraries can not.\n\nPlease note, however, that the code is designed for readability and ease of use, and not necessarily for\nruntime **performance**.\n\nOur implementation uses a novel modification of _Felkel, Petr & Obdr\u017e\u00e1lek, \u0160t\u011bp\u00e1n (1998)_ algorithm, to address some shortcomings found during its evaluation, which failed to compute proper skeletons for several of our test cases.\n\nInput | Result\n:---------------------------------------:|:---------------------------------------:\n | \n\n## Usage\n\n```text\n \ud83d\udcdd Note: We use (+X right, +Y up) axes as our coordinate system.\n```\n\n \n\n```python\n# Define your polygon (counter-clockwise) with optional holes (clockwise).\nTEST_EXTERIOR = [[0, 0], [4, 0], [4, -2], [6, -2], [6, 0], [10, 0], [10, 10], [0, 10]]\nTEST_HOLES = [[[4, 6], [6, 6], [6, 4], [4, 4]]]\n\nfrom py_straight_skeleton import compute_skeleton\nskeleton = compute_skeleton(exterior=TEST_EXTERIOR, holes=TEST_HOLES)\n```\n\nCheck [examples/demo.ipynb](examples/demo.ipynb) for a full example with plotting and skeleton parsing.\n\nSkeleton parsing is generally done via three methods:\n\n```python\n# \n# @property\n# nodes(self) -> list[SkeletonNode]:\n# \nprint(skeleton.nodes)\n\n[SKN(0, 0.000, 0.000, 0.00000), SKN(1, 4.000, 0.000, 0.00000), SKN(2, 4.000, -2.000, 0.00000), SKN(3, 6.000, -2.000, 0.00000), SKN(4, 6.000, 0.000, 0.00000), SKN(5, 10.000, 0.000, 0.00000), SKN(6, 10.000, 10.000, 0.00000), SKN(7, 0.000, 10.000, 0.00000), SKN(8, 4.000, 6.000, 0.00000), SKN(9, 6.000, 6.000, 0.00000), SKN(10, 6.000, 4.000, 0.00000), SKN(11, 4.000, 4.000, 0.00000), SKN(12, 5.000, -1.000, 1.00000), SKN(13, 5.000, 1.000, 1.00000), SKN(14, 2.000, 8.000, 2.00000), SKN(15, 8.000, 8.000, 2.00000), SKN(16, 8.000, 2.000, 2.00000), SKN(17, 2.000, 2.000, 2.00000), SKN(18, 5.000, 2.000, 2.00000)]\n\n# \n# get_faces(self) -> list[SkeletonFace]\n# \nfor face_idx, face in enumerate(skeleton.get_faces()):\n nodes_pos = [skeleton.nodes[v_idx].position for v_idx in face]\n print(f\"face {face_idx} -> {nodes_pos}\")\n\nface 0 -> [Vector2(0.000, 0.000), Vector2(4.000, 0.000), ...]\nface 1 -> [Vector2(4.000, 0.000), Vector2(4.000, -2.000), ...]\nface 2 -> [Vector2(4.000, -2.000), Vector2(6.000, -2.000), ...]\nface 3 -> [Vector2(6.000, -2.000), ...]\n...\nface 11 -> [Vector2(4.000, 4.000), Vector2(4.000, 6.000), ...]\n\n# \n# arc_iterator(self) -> Iterator[tuple[SkeletonNode, SkeletonNode]]\n# \nfor skv1, skv2 in skeleton.arc_iterator():\n print(f\"{skv1.position} -> {skv2.position}\")\n\nVector2(4.000, -2.000) -> Vector2(5.000, -1.000)\nVector2(6.000, -2.000) -> Vector2(5.000, -1.000)\nVector2(6.000, 0.000) -> Vector2(5.000, 1.000)\n...\nVector2(8.000, 2.000) -> Vector2(5.000, 2.000)\nVector2(2.000, 2.000) -> Vector2(5.000, 2.000)\n```\n\n## Visualization\n\nThe [plotting module](src/py_straight_skeleton/plotting.py) provides several utilities to plot results and intermediate\nsteps of the algorithm for debugging and verification.\n\nEg:\n\n```python\n# skeleton = ...\n\nimport matplotlib.pyplot as plt\nfig, ax = plt.subplots(figsize=(4, 4))\nax.set_aspect(\"equal\")\n\nfrom py_straight_skeleton.plotting import Utils\nUtils.plot_skeleton(skeleton, ax=ax, show_vertex_info=True)\n\nfig.savefig(\"output.png\")\n```\n\n\n\n## Debugging\n\nThe [plotting module](src/py_straight_skeleton/plotting.py) also provides a `PlotTracer` that can help debug steps,\nalthough we encourage opening issues in the repository for help if necessary.\n\n```python\nimport logging\nfrom py_straight_skeleton import compute_skeleton\nfrom py_straight_skeleton.algorithm import set_global_algorithm_tracer\nfrom py_straight_skeleton.plotting import PlotTracer\n\n# Define your polygon (counter-clockwise) with optional holes (clockwise).\nTEST_EXTERIOR = [[0, 0], [4, 0], [4, -2], [6, -2], [6, 0], [10, 0], [10, 10], [0, 10]]\nTEST_HOLES = [[[4, 6], [6, 6], [6, 4], [4, 4]]]\n\n# Set plot tracer to be notified by the algorithm steps and output to a folder.\nplot_tracer = PlotTracer(\n fig_cs=2.5, \n step_fig_ncols=3, \n step_fig_nrows=3, \n log_level=logging.INFO, \n output_dir=\"examples/plot_tracer_output/\",\n)\nset_global_algorithm_tracer(plot_tracer)\n\nskeleton = compute_skeleton(exterior=TEST_EXTERIOR, holes=TEST_HOLES)\n```\n\n\n\n",
"bugtrack_url": null,
"license": "3-Clause BSD",
"summary": "Compute the straight skeleton of a polygon and its resulting polygonal faces.",
"version": "0.1.0",
"project_urls": null,
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "db02eabf98188445e1864e1589b1c8fdc658de688fff92b7ddb77550ef4aa281",
"md5": "2a362b2fb044e6c3043f9ac3fd59623c",
"sha256": "f9602b88d09147bf69551ec81e209281eca3e295a40b7d6e26ee0921b8c8d317"
},
"downloads": -1,
"filename": "py_straight_skeleton-0.1.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "2a362b2fb044e6c3043f9ac3fd59623c",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<4.0,>=3.10",
"size": 39039,
"upload_time": "2024-12-20T23:29:31",
"upload_time_iso_8601": "2024-12-20T23:29:31.107686Z",
"url": "https://files.pythonhosted.org/packages/db/02/eabf98188445e1864e1589b1c8fdc658de688fff92b7ddb77550ef4aa281/py_straight_skeleton-0.1.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a64f294a289ff07f22df4c10e6408adf4af1532620d77bce2063faa19b342e70",
"md5": "d25a9837da4f5facdde2ab8dbff2fe37",
"sha256": "4d7a178a5d070d3dc798ad159fa50fe37d67fa95fdd271dd8e02695a523b9593"
},
"downloads": -1,
"filename": "py_straight_skeleton-0.1.0.tar.gz",
"has_sig": false,
"md5_digest": "d25a9837da4f5facdde2ab8dbff2fe37",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<4.0,>=3.10",
"size": 36863,
"upload_time": "2024-12-20T23:29:32",
"upload_time_iso_8601": "2024-12-20T23:29:32.360981Z",
"url": "https://files.pythonhosted.org/packages/a6/4f/294a289ff07f22df4c10e6408adf4af1532620d77bce2063faa19b342e70/py_straight_skeleton-0.1.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-20 23:29:32",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "py_straight_skeleton"
}
