| Name | pyvispoly JSON |
| Version |
0.3.0
JSON |
| download |
| home_page | |
| Summary | CGAL's visibility polygons in Python |
| upload_time | 2024-02-24 16:16:35 |
| maintainer | |
| docs_url | None |
| author | Dominik Krupke |
| requires_python | >=3.7 |
| license | LICENSE |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# pyvispoly
This package provides a Python interface to the [CGAL](https://www.cgal.org/)
library for computing visibility polygons. It is exact, but not necessarily
efficient.
**Motivation:** This package was developed in the context of implementing an
exact solver for the dispersive Art Gallery Problem
([see here](https://github.com/d-krupke/dispersive_agp_solver)). Because the
problem is difficult and only reasonably small instances can be solved, the
focus of this package is on correctness and not on efficiency.
## Installation
You can install the package using pip:
```bash
pip install --verbose .
```
or directly via PyPI:
```bash
pip install --verbose pyvispoly
```
During installation, it will download and install CGAL and its dependencies.
This may take a while. This requires a C++-compiler to be installed on your
system.
> :info: On installation problems, please first check out
> [skbuild-conan's troubleshooting guide](https://github.com/d-krupke/skbuild-conan#common-problems).
> It is likely that the automatic C++-compilation fails.
## Addressing the Complexity of Visibility Polygon Computation
Computing visibility polygons demands precise arithmetic; imprecise calculations
often yield incorrect results. This package leverages the robustness of the CGAL
library for accurate visibility polygon computation. Note that it is essential
to convert your coordinates to CGAL's exact number type. Failure to use the
correct types may result in exceptions.
This package explicitly avoids duck typing and automatic type conversion. While
these features could simplify usage, they risk obscuring underlying errors in
your code. In geometric computations, precision is paramount; thus, Python's
native floating-point numbers are unsuitable.
## Usage
```python
# import elements from pyvispoly
from pyvispoly import (
FieldNumber,
Point,
Polygon,
PolygonWithHoles,
VisibilityPolygonCalculator,
plot_polygon,
)
import matplotlib.pyplot as plt
```
```python
# exact number type
a = FieldNumber(100)
b = FieldNumber(200)
c = a + b
assert isinstance(c, FieldNumber)
print("c:", c)
print("float(c):", float(c))
assert float(c) == 300.0
```
c: 300.000000
float(c): 300.0
```python
# point type
p1 = Point(FieldNumber(0), FieldNumber(0))
assert p1.x() == FieldNumber(0) and p1.y() == FieldNumber(0)
p2 = Point(2, 3)
p3 = Point(4.0, 5.0)
print("p1:", p1)
print("p2:", p2)
print("p3:", p3)
```
p1: (0, 0)
p2: (2, 3)
p3: (4, 5)
```python
# Polygon
poly1 = Polygon([Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)])
assert poly1.is_simple()
assert poly1.area() == FieldNumber(1)
assert float(poly1.area()) == 1.0
```
```python
# The ccw order of the points is important
poly1 = Polygon([Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)][::-1])
assert poly1.is_simple()
assert poly1.area() == FieldNumber(-1)
assert float(poly1.area()) == -1.0
```
```python
# Polygon with holes
poly2 = PolygonWithHoles(
[Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)],
[
[Point(0.25, 0.25), Point(0.75, 0.25), Point(0.75, 0.75), Point(0.25, 0.75)][
::-1
]
],
)
# boundary is counter-clockwise
assert poly2.outer_boundary().area() >= FieldNumber(0)
for hole in poly2.holes():
# holes are clockwise
assert hole.area() <= FieldNumber(0)
fig, ax = plt.subplots()
ax.set_aspect("equal")
plot_polygon(poly2, ax=ax)
plt.show()
```
```python
# set operations on polygons
poly3 = PolygonWithHoles([Point(0, 0), Point(0.1, 0), Point(0.1, 0.1), Point(0, 0.1)])
poly4_list = poly2.difference(poly3)
assert len(poly4_list) == 1, "Expect a single polygon"
poly4 = poly4_list[0]
fig, ax = plt.subplots()
ax.set_aspect("equal")
plot_polygon(poly4, ax=ax)
plt.show()
```
```python
# compute visibility polygon
visp_poly_calc = VisibilityPolygonCalculator(poly4)
vis_poly = visp_poly_calc.compute_visibility_polygon(Point(0.2, 0.0))
fig, ax = plt.subplots()
ax.set_aspect("equal")
plt.title("Visibility Polygon")
plot_polygon(poly4, ax=ax, color="lightgrey")
plot_polygon(vis_poly, ax=ax, color="red", alpha=0.5)
plt.plot([0.2], [0.0], "x", color="black")
plt.savefig("../docs/figures/visibility_polygon.png")
plt.show()
```
```python
# getting some interior points
fig, ax = plt.subplots()
ax.set_aspect("equal")
plt.title("Sample points in the interior")
plot_polygon(poly4, ax=ax, color="lightgrey")
plot_polygon(vis_poly, ax=ax, color="red", alpha=0.5)
plt.plot([0.2], [0.0], "x", color="black")
interior_points = vis_poly.interior_sample_points()
for p in interior_points:
assert vis_poly.contains(p), "all points should be inside the visibility polygon"
plt.plot(
[p.x() for p in interior_points],
[p.y() for p in interior_points],
"+",
color="black",
)
plt.show()
```
> :warning: The library may segfault if you pass bad polygons. For example, if
> holes intersect the outer boundary, the library may crash. One could probably
> catch these errors, but I have not implemented this yet (feel free to do so
> and submit a pull request).
## License
This library incorporates components from the CGAL library through static
linking, which are subject to the terms of the GNU General Public License (GPL).
Consequently, the use and distribution of this library are also governed by the
GPL.
However, if you possess a specialized (commercial) license for CGAL (or replace
CGAL), then the portions of this library excluding the CGAL component are
available under the more permissive MIT license, consistent with the licensing
of my other code.
Please ensure you understand the implications of these licenses before using or
distributing this library.
## Changelog
- **0.3.0** Added `do_intersect`.
- **0.2.0** Made the library more robust and added a `repair`-method as the
boolean operations are not always guaranteed to produce valid polygons. Note
that this is just kind of a hack and may not always work.
- **0.1.3:** (2023-11-29) Workaround to bug in CGAL.
Raw data
{
"_id": null,
"home_page": "",
"name": "pyvispoly",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "",
"author": "Dominik Krupke",
"author_email": "",
"download_url": "https://files.pythonhosted.org/packages/88/be/a671ef3624870aa77eff19269198968233cac69413404fb23d37f33032d0/pyvispoly-0.3.0.tar.gz",
"platform": null,
"description": "# pyvispoly\n\nThis package provides a Python interface to the [CGAL](https://www.cgal.org/)\nlibrary for computing visibility polygons. It is exact, but not necessarily\nefficient.\n\n**Motivation:** This package was developed in the context of implementing an\nexact solver for the dispersive Art Gallery Problem\n([see here](https://github.com/d-krupke/dispersive_agp_solver)). Because the\nproblem is difficult and only reasonably small instances can be solved, the\nfocus of this package is on correctness and not on efficiency.\n\n\n\n## Installation\n\nYou can install the package using pip:\n\n```bash\npip install --verbose .\n```\n\nor directly via PyPI:\n\n```bash\npip install --verbose pyvispoly\n```\n\nDuring installation, it will download and install CGAL and its dependencies.\nThis may take a while. This requires a C++-compiler to be installed on your\nsystem.\n\n> :info: On installation problems, please first check out\n> [skbuild-conan's troubleshooting guide](https://github.com/d-krupke/skbuild-conan#common-problems).\n> It is likely that the automatic C++-compilation fails.\n\n## Addressing the Complexity of Visibility Polygon Computation\n\nComputing visibility polygons demands precise arithmetic; imprecise calculations\noften yield incorrect results. This package leverages the robustness of the CGAL\nlibrary for accurate visibility polygon computation. Note that it is essential\nto convert your coordinates to CGAL's exact number type. Failure to use the\ncorrect types may result in exceptions.\n\nThis package explicitly avoids duck typing and automatic type conversion. While\nthese features could simplify usage, they risk obscuring underlying errors in\nyour code. In geometric computations, precision is paramount; thus, Python's\nnative floating-point numbers are unsuitable.\n\n## Usage\n\n```python\n# import elements from pyvispoly\nfrom pyvispoly import (\n FieldNumber,\n Point,\n Polygon,\n PolygonWithHoles,\n VisibilityPolygonCalculator,\n plot_polygon,\n)\nimport matplotlib.pyplot as plt\n```\n\n```python\n# exact number type\na = FieldNumber(100)\nb = FieldNumber(200)\nc = a + b\nassert isinstance(c, FieldNumber)\nprint(\"c:\", c)\nprint(\"float(c):\", float(c))\nassert float(c) == 300.0\n```\n\n c: 300.000000\n float(c): 300.0\n\n```python\n# point type\np1 = Point(FieldNumber(0), FieldNumber(0))\nassert p1.x() == FieldNumber(0) and p1.y() == FieldNumber(0)\np2 = Point(2, 3)\np3 = Point(4.0, 5.0)\nprint(\"p1:\", p1)\nprint(\"p2:\", p2)\nprint(\"p3:\", p3)\n```\n\n p1: (0, 0)\n p2: (2, 3)\n p3: (4, 5)\n\n```python\n# Polygon\npoly1 = Polygon([Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)])\nassert poly1.is_simple()\nassert poly1.area() == FieldNumber(1)\nassert float(poly1.area()) == 1.0\n```\n\n```python\n# The ccw order of the points is important\npoly1 = Polygon([Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)][::-1])\nassert poly1.is_simple()\nassert poly1.area() == FieldNumber(-1)\nassert float(poly1.area()) == -1.0\n```\n\n```python\n# Polygon with holes\npoly2 = PolygonWithHoles(\n [Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)],\n [\n [Point(0.25, 0.25), Point(0.75, 0.25), Point(0.75, 0.75), Point(0.25, 0.75)][\n ::-1\n ]\n ],\n)\n# boundary is counter-clockwise\nassert poly2.outer_boundary().area() >= FieldNumber(0)\nfor hole in poly2.holes():\n # holes are clockwise\n assert hole.area() <= FieldNumber(0)\n\nfig, ax = plt.subplots()\nax.set_aspect(\"equal\")\nplot_polygon(poly2, ax=ax)\nplt.show()\n```\n\n\n\n```python\n# set operations on polygons\npoly3 = PolygonWithHoles([Point(0, 0), Point(0.1, 0), Point(0.1, 0.1), Point(0, 0.1)])\npoly4_list = poly2.difference(poly3)\nassert len(poly4_list) == 1, \"Expect a single polygon\"\npoly4 = poly4_list[0]\nfig, ax = plt.subplots()\nax.set_aspect(\"equal\")\nplot_polygon(poly4, ax=ax)\nplt.show()\n```\n\n\n\n```python\n# compute visibility polygon\nvisp_poly_calc = VisibilityPolygonCalculator(poly4)\nvis_poly = visp_poly_calc.compute_visibility_polygon(Point(0.2, 0.0))\n\nfig, ax = plt.subplots()\nax.set_aspect(\"equal\")\nplt.title(\"Visibility Polygon\")\nplot_polygon(poly4, ax=ax, color=\"lightgrey\")\nplot_polygon(vis_poly, ax=ax, color=\"red\", alpha=0.5)\nplt.plot([0.2], [0.0], \"x\", color=\"black\")\nplt.savefig(\"../docs/figures/visibility_polygon.png\")\nplt.show()\n```\n\n\n\n```python\n# getting some interior points\nfig, ax = plt.subplots()\nax.set_aspect(\"equal\")\nplt.title(\"Sample points in the interior\")\nplot_polygon(poly4, ax=ax, color=\"lightgrey\")\nplot_polygon(vis_poly, ax=ax, color=\"red\", alpha=0.5)\nplt.plot([0.2], [0.0], \"x\", color=\"black\")\ninterior_points = vis_poly.interior_sample_points()\nfor p in interior_points:\n assert vis_poly.contains(p), \"all points should be inside the visibility polygon\"\nplt.plot(\n [p.x() for p in interior_points],\n [p.y() for p in interior_points],\n \"+\",\n color=\"black\",\n)\nplt.show()\n```\n\n\n\n> :warning: The library may segfault if you pass bad polygons. For example, if\n> holes intersect the outer boundary, the library may crash. One could probably\n> catch these errors, but I have not implemented this yet (feel free to do so\n> and submit a pull request).\n\n## License\n\nThis library incorporates components from the CGAL library through static\nlinking, which are subject to the terms of the GNU General Public License (GPL).\nConsequently, the use and distribution of this library are also governed by the\nGPL.\n\nHowever, if you possess a specialized (commercial) license for CGAL (or replace\nCGAL), then the portions of this library excluding the CGAL component are\navailable under the more permissive MIT license, consistent with the licensing\nof my other code.\n\nPlease ensure you understand the implications of these licenses before using or\ndistributing this library.\n\n## Changelog\n\n- **0.3.0** Added `do_intersect`.\n- **0.2.0** Made the library more robust and added a `repair`-method as the\n boolean operations are not always guaranteed to produce valid polygons. Note\n that this is just kind of a hack and may not always work.\n- **0.1.3:** (2023-11-29) Workaround to bug in CGAL.\n",
"bugtrack_url": null,
"license": "LICENSE",
"summary": "CGAL's visibility polygons in Python",
"version": "0.3.0",
"project_urls": null,
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "88bea671ef3624870aa77eff19269198968233cac69413404fb23d37f33032d0",
"md5": "3f2659d09c5e2b94274bca8442d420b5",
"sha256": "7a08ce6c3b65532ea7b3b8eee8b013ede1d80e6f0bd9b150c29a07bdf1cd85cf"
},
"downloads": -1,
"filename": "pyvispoly-0.3.0.tar.gz",
"has_sig": false,
"md5_digest": "3f2659d09c5e2b94274bca8442d420b5",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 170721,
"upload_time": "2024-02-24T16:16:35",
"upload_time_iso_8601": "2024-02-24T16:16:35.886247Z",
"url": "https://files.pythonhosted.org/packages/88/be/a671ef3624870aa77eff19269198968233cac69413404fb23d37f33032d0/pyvispoly-0.3.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-02-24 16:16:35",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "pyvispoly"
}
