| Name | cgshop2025-pyutils JSON |
| Version |
0.0.10
JSON |
| download |
| home_page | None |
| Summary | Utilities for verifying solutions of the CG:SHOP 2025 Competition. |
| upload_time | 2024-12-14 17:25:34 |
| maintainer | None |
| docs_url | None |
| author | Dominik Krupke |
| requires_python | >=3.10 |
| license | LICENSE |
| keywords |
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# CG:SHOP - Official pyutils25 for the 2025 Challenge on Non-Obtuse Triangulation
Utilities for verifying solutions of the CG:SHOP 2025 Competition. Feel free to
use the code, but it is optimized for _exact_ verification not for sampling or
other purposes.
## Installation
You can install the utilities via pip:
```bash
pip install cgshop2025-pyutils
```
Alternatively, you can install this package via source:
```bash
pip install --verbose .
```
You can also install it without the need to clone the repository:
```bash
pip install --verbose git+https://github.com/CG-SHOP/pyutils25
```
During the installation, CGAL and other dependencies will be downloaded and
compiled. This can take a while but should happen mostly automatic. You need to
have a C++ compiler (and the Python development environment) installed. Most
systems will come with all dependencies preinstalled. Otherwise, you can for
example install them on Ubuntu with the following command
```bash
sudo apt install build-essential python3-dev
```
You can test the installation with
```bash
pytest -s tests
```
> Please check for updates of the utils frequently as we are still working on
> them.
## Usage
You can use the utilities to verify solutions of the CG:SHOP 2025 Competition.
1. **Instance Database**: Utilize the instance database to iterate over all
instances in the benchmark effortlessly.
2. **Naive Solver**: Compute a solution for each instance using the naive
solver, which performs a constrained Delaunay triangulation without using
Steiner points.
3. **ZipWriter**: Use the ZipWriter to create a valid submission file easily.
4. **SolutionChecker**: Verify the validity of the solution using the
SolutionChecker.
```python
from pathlib import Path
from cgshop2025_pyutils import (
DelaunayBasedSolver,
InstanceDatabase,
ZipSolutionIterator,
ZipWriter,
verify,
)
# Load the instances from the example_instances folder. Instead of referring to the folder,
# you can also give a path to a zip file.
idb = InstanceDatabase("example_instances/")
# If the solution zip file already exists, delete it
if Path("example_solutions.zip").exists():
Path("example_solutions.zip").unlink()
# Compute solutions for all instances using the provided (naive) solver
solutions = []
for instance in idb:
solver = DelaunayBasedSolver(instance)
solution = solver.solve()
solutions.append(solution)
# Write the solutions to a new zip file
with ZipWriter("example_solutions.zip") as zw:
for solution in solutions:
zw.add_solution(solution)
# Verify the solutions
for solution in ZipSolutionIterator("example_solutions.zip"):
instance = idb[solution.instance_uid]
result = verify(instance, solution)
print(f"{solution.instance_uid}: {result}")
assert not result.errors, "Expect no errors."
```
## Additional Features
The utils also expose a number of additional features that may be useful for
developing your own solvers, as you will need to use exact arithmetic as
provided by CGAL. However, if you want to use Python, we recommend to actually
just fork this repository and adapt/extend the provided code to your needs.
Check out the test cases (in `./tests/`) for some examples. We may provide some
further utilities in the near future, but for now, you can use the following
classes:
#### `FieldNumber`
Represents an exact number (rational or floating-point) for precise arithmetic
operations. If you are not sure about exact arithmetic, this single class will
save you a lot of time. Just use it for all your arithmetic operations and you
will be fine. For extracting the exact representation of the number, use the
`exact()` method, which returns a string that is an exact representation and
accepted by our verifier.
- `FieldNumber(value: int | float | str)`: Initialize with an integer, float, or
string.
- `exact() -> str`: Returns the exact representation of the number as a string.
- Supports `+`, `-`, `*`, `/` arithmetic and comparison operators (`<`, `>`,
`==`, `!=`).
#### `Point`
Represents a 2D point with exact coordinates.
- `Point(x: FieldNumber, y: FieldNumber)`: Initialize a point with two
`FieldNumber` coordinates.
- `x() -> FieldNumber`: Returns the x-coordinate.
- `y() -> FieldNumber`: Returns the y-coordinate.
- `scale(factor: FieldNumber) -> Point`: Returns a new point scaled by the given
factor.
- Supports `+`, `-` operators for point arithmetic.
#### `Segment`
Represents a 2D segment between two `Point` objects.
- `Segment(source: Point, target: Point)`: Initialize a segment with source and
target points.
- `source() -> Point`: Returns the source point of the segment.
- `target() -> Point`: Returns the target point of the segment.
- `squared_length() -> FieldNumber`: Returns the squared length of the segment.
- `does_intersect(other: Segment) -> bool`: Checks if the segment intersects
with another segment.
#### `Polygon`
Represents a simple polygon.
- `Polygon(points: List[Point])`: Initialize a polygon with a list of points.
- `is_simple() -> bool`: Checks if the polygon is simple (no
self-intersections).
- `contains(point: Point) -> bool`: Checks if the polygon contains the given
point.
- `on_boundary(point: Point) -> bool`: Checks if the point is on the polygon
boundary.
- `area() -> FieldNumber`: Returns the area of the polygon.
#### `VerificationGeometryHelper`
Verifies geometric structures, detecting non-triangular faces, bad edges, and
isolated points.
- `VerificationGeometryHelper()`: Initialize the geometry helper.
- `add_point(point: Point) -> int`: Adds a point to the geometry and returns its
index.
- `add_segment(index1: int, index2: int)`: Adds a segment between two points by
their indices.
- `get_num_points() -> int`: Returns the number of points in the geometry.
- `search_for_non_triangular_faces() -> Optional[Point]`: Searches for any
non-triangular faces.
- `search_for_bad_edges() -> Optional[Segment]`: Searches for edges with the
same face on both sides.
- `search_for_isolated_points() -> List[Point]`: Returns a list of isolated
points.
- `count_obtuse_triangles() -> int`: Counts the number of obtuse triangles in
the geometry.
#### `ConstrainedTriangulation`
Handles 2D constrained Delaunay triangulation.
- `ConstrainedTriangulation()`: Initialize the triangulation.
- `add_point(point: Point) -> int`: Adds a point and returns its index.
- `add_boundary(indices: List[int])`: Adds a polygon boundary defined by the
point indices.
- `add_segment(index1: int, index2: int)`: Adds a segment between two points by
their indices.
- `get_triangulation_edges() -> List[Tuple[int, int]]`: Returns a list of edges
as tuples of point indices.
#### `compute_convex_hull`
Computes the convex hull of a set of points.
- `compute_convex_hull(points: List[Point]) -> List[int]`: Returns the indices
of points on the convex hull.
#### `intersection_point`
Finds the intersection point of two segments, if they intersect.
- `intersection_point(seg1: Segment, seg2: Segment) -> Optional[Point]`: Returns
the intersection point or `None`.
## License
Our code is licensed under the MIT License. However, the code depends on CGAL,
which can have implications for non-academic users. Please check the CGAL
license for more information.
## Reporting Issues
If you encounter any issues, please report them in the issue tracker. We will
try to fix them as soon as possible.
## Changelog
- `0.0.10`: Fixed adding the instances segments to the verification geometry
helper. This was a serious issue that could lead to accepting invalid
solutions.
- `0.0.9`: Better bounds checking for segment endpoint indices in `verify`
- `0.0.8`: Adding file information to exceptions of `ZipSolutionIterator`
- `0.0.7`: Fix for only accepting `.solution.json` (there was a `,` missing)
- `0.0.6`: Fix for CGAL 6
- `0.0.5`: Improved error messages for isolated points. Only accepting
`.solution.json` as solution file extension.
- `0.0.4`: Fixed bug with negative numbers in FieldNumber with string input
- `0.0.3`: Allows negative Steiner points and ensure coordinates are converted
to FieldNumber before Point construction
Raw data
{
"_id": null,
"home_page": null,
"name": "cgshop2025-pyutils",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": null,
"author": "Dominik Krupke",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/35/00/1f9d5a1bc4735d9a023d2c7f22a23b243ec73f80598f74bd5251530a9dd5/cgshop2025_pyutils-0.0.10.tar.gz",
"platform": null,
"description": "# CG:SHOP - Official pyutils25 for the 2025 Challenge on Non-Obtuse Triangulation\n\nUtilities for verifying solutions of the CG:SHOP 2025 Competition. Feel free to\nuse the code, but it is optimized for _exact_ verification not for sampling or\nother purposes.\n\n## Installation\n\nYou can install the utilities via pip:\n\n```bash\npip install cgshop2025-pyutils\n```\n\nAlternatively, you can install this package via source:\n\n```bash\npip install --verbose .\n```\n\nYou can also install it without the need to clone the repository:\n\n```bash\npip install --verbose git+https://github.com/CG-SHOP/pyutils25\n```\n\nDuring the installation, CGAL and other dependencies will be downloaded and\ncompiled. This can take a while but should happen mostly automatic. You need to\nhave a C++ compiler (and the Python development environment) installed. Most\nsystems will come with all dependencies preinstalled. Otherwise, you can for\nexample install them on Ubuntu with the following command\n\n```bash\nsudo apt install build-essential python3-dev\n```\n\nYou can test the installation with\n\n```bash\npytest -s tests\n```\n\n> Please check for updates of the utils frequently as we are still working on\n> them.\n\n## Usage\n\nYou can use the utilities to verify solutions of the CG:SHOP 2025 Competition.\n\n1. **Instance Database**: Utilize the instance database to iterate over all\n instances in the benchmark effortlessly.\n2. **Naive Solver**: Compute a solution for each instance using the naive\n solver, which performs a constrained Delaunay triangulation without using\n Steiner points.\n3. **ZipWriter**: Use the ZipWriter to create a valid submission file easily.\n4. **SolutionChecker**: Verify the validity of the solution using the\n SolutionChecker.\n\n```python\nfrom pathlib import Path\n\nfrom cgshop2025_pyutils import (\n DelaunayBasedSolver,\n InstanceDatabase,\n ZipSolutionIterator,\n ZipWriter,\n verify,\n)\n\n# Load the instances from the example_instances folder. Instead of referring to the folder,\n# you can also give a path to a zip file.\nidb = InstanceDatabase(\"example_instances/\")\n\n# If the solution zip file already exists, delete it\nif Path(\"example_solutions.zip\").exists():\n Path(\"example_solutions.zip\").unlink()\n\n# Compute solutions for all instances using the provided (naive) solver\nsolutions = []\nfor instance in idb:\n solver = DelaunayBasedSolver(instance)\n solution = solver.solve()\n solutions.append(solution)\n\n# Write the solutions to a new zip file\nwith ZipWriter(\"example_solutions.zip\") as zw:\n for solution in solutions:\n zw.add_solution(solution)\n\n# Verify the solutions\nfor solution in ZipSolutionIterator(\"example_solutions.zip\"):\n instance = idb[solution.instance_uid]\n result = verify(instance, solution)\n print(f\"{solution.instance_uid}: {result}\")\n assert not result.errors, \"Expect no errors.\"\n```\n\n## Additional Features\n\nThe utils also expose a number of additional features that may be useful for\ndeveloping your own solvers, as you will need to use exact arithmetic as\nprovided by CGAL. However, if you want to use Python, we recommend to actually\njust fork this repository and adapt/extend the provided code to your needs.\nCheck out the test cases (in `./tests/`) for some examples. We may provide some\nfurther utilities in the near future, but for now, you can use the following\nclasses:\n\n#### `FieldNumber`\n\nRepresents an exact number (rational or floating-point) for precise arithmetic\noperations. If you are not sure about exact arithmetic, this single class will\nsave you a lot of time. Just use it for all your arithmetic operations and you\nwill be fine. For extracting the exact representation of the number, use the\n`exact()` method, which returns a string that is an exact representation and\naccepted by our verifier.\n\n- `FieldNumber(value: int | float | str)`: Initialize with an integer, float, or\n string.\n- `exact() -> str`: Returns the exact representation of the number as a string.\n- Supports `+`, `-`, `*`, `/` arithmetic and comparison operators (`<`, `>`,\n `==`, `!=`).\n\n#### `Point`\n\nRepresents a 2D point with exact coordinates.\n\n- `Point(x: FieldNumber, y: FieldNumber)`: Initialize a point with two\n `FieldNumber` coordinates.\n- `x() -> FieldNumber`: Returns the x-coordinate.\n- `y() -> FieldNumber`: Returns the y-coordinate.\n- `scale(factor: FieldNumber) -> Point`: Returns a new point scaled by the given\n factor.\n- Supports `+`, `-` operators for point arithmetic.\n\n#### `Segment`\n\nRepresents a 2D segment between two `Point` objects.\n\n- `Segment(source: Point, target: Point)`: Initialize a segment with source and\n target points.\n- `source() -> Point`: Returns the source point of the segment.\n- `target() -> Point`: Returns the target point of the segment.\n- `squared_length() -> FieldNumber`: Returns the squared length of the segment.\n- `does_intersect(other: Segment) -> bool`: Checks if the segment intersects\n with another segment.\n\n#### `Polygon`\n\nRepresents a simple polygon.\n\n- `Polygon(points: List[Point])`: Initialize a polygon with a list of points.\n- `is_simple() -> bool`: Checks if the polygon is simple (no\n self-intersections).\n- `contains(point: Point) -> bool`: Checks if the polygon contains the given\n point.\n- `on_boundary(point: Point) -> bool`: Checks if the point is on the polygon\n boundary.\n- `area() -> FieldNumber`: Returns the area of the polygon.\n\n#### `VerificationGeometryHelper`\n\nVerifies geometric structures, detecting non-triangular faces, bad edges, and\nisolated points.\n\n- `VerificationGeometryHelper()`: Initialize the geometry helper.\n- `add_point(point: Point) -> int`: Adds a point to the geometry and returns its\n index.\n- `add_segment(index1: int, index2: int)`: Adds a segment between two points by\n their indices.\n- `get_num_points() -> int`: Returns the number of points in the geometry.\n- `search_for_non_triangular_faces() -> Optional[Point]`: Searches for any\n non-triangular faces.\n- `search_for_bad_edges() -> Optional[Segment]`: Searches for edges with the\n same face on both sides.\n- `search_for_isolated_points() -> List[Point]`: Returns a list of isolated\n points.\n- `count_obtuse_triangles() -> int`: Counts the number of obtuse triangles in\n the geometry.\n\n#### `ConstrainedTriangulation`\n\nHandles 2D constrained Delaunay triangulation.\n\n- `ConstrainedTriangulation()`: Initialize the triangulation.\n- `add_point(point: Point) -> int`: Adds a point and returns its index.\n- `add_boundary(indices: List[int])`: Adds a polygon boundary defined by the\n point indices.\n- `add_segment(index1: int, index2: int)`: Adds a segment between two points by\n their indices.\n- `get_triangulation_edges() -> List[Tuple[int, int]]`: Returns a list of edges\n as tuples of point indices.\n\n#### `compute_convex_hull`\n\nComputes the convex hull of a set of points.\n\n- `compute_convex_hull(points: List[Point]) -> List[int]`: Returns the indices\n of points on the convex hull.\n\n#### `intersection_point`\n\nFinds the intersection point of two segments, if they intersect.\n\n- `intersection_point(seg1: Segment, seg2: Segment) -> Optional[Point]`: Returns\n the intersection point or `None`.\n\n## License\n\nOur code is licensed under the MIT License. However, the code depends on CGAL,\nwhich can have implications for non-academic users. Please check the CGAL\nlicense for more information.\n\n## Reporting Issues\n\nIf you encounter any issues, please report them in the issue tracker. We will\ntry to fix them as soon as possible.\n\n## Changelog\n\n- `0.0.10`: Fixed adding the instances segments to the verification geometry\n helper. This was a serious issue that could lead to accepting invalid\n solutions.\n- `0.0.9`: Better bounds checking for segment endpoint indices in `verify`\n- `0.0.8`: Adding file information to exceptions of `ZipSolutionIterator`\n- `0.0.7`: Fix for only accepting `.solution.json` (there was a `,` missing)\n- `0.0.6`: Fix for CGAL 6\n- `0.0.5`: Improved error messages for isolated points. Only accepting\n `.solution.json` as solution file extension.\n- `0.0.4`: Fixed bug with negative numbers in FieldNumber with string input\n- `0.0.3`: Allows negative Steiner points and ensure coordinates are converted\n to FieldNumber before Point construction\n",
"bugtrack_url": null,
"license": "LICENSE",
"summary": "Utilities for verifying solutions of the CG:SHOP 2025 Competition.",
"version": "0.0.10",
"project_urls": null,
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "35001f9d5a1bc4735d9a023d2c7f22a23b243ec73f80598f74bd5251530a9dd5",
"md5": "51b9420dcf0b10e68793d46c94b80fd1",
"sha256": "adcc501a3533394ec896a4d53c54cd8791e3d834cd3a8407acfa0f50933de3c5"
},
"downloads": -1,
"filename": "cgshop2025_pyutils-0.0.10.tar.gz",
"has_sig": false,
"md5_digest": "51b9420dcf0b10e68793d46c94b80fd1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 46282,
"upload_time": "2024-12-14T17:25:34",
"upload_time_iso_8601": "2024-12-14T17:25:34.789455Z",
"url": "https://files.pythonhosted.org/packages/35/00/1f9d5a1bc4735d9a023d2c7f22a23b243ec73f80598f74bd5251530a9dd5/cgshop2025_pyutils-0.0.10.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-14 17:25:34",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "cgshop2025-pyutils"
}
