# rportion - data structure and operations for rectilinear polygons
[](https://pypi.org/project/rportion/)
[](https://github.com/tilmann-bartsch/portion/actions/workflows/test.yaml)
[](https://coveralls.io/github/tilmann-bartsch/rportion?branch=master)
[](https://opensource.org/licenses/MIT)
[](https://github.com/tilmann-bartsch/rportion/commits/master)
The `rportion` library provides data structure to represent
2D [rectilinear polygons](https://en.wikipedia.org/wiki/Rectilinear_polygon) (unions of 2D-intervals) in Python 3.9+.
It is built upon the library [`portion`](https://github.com/AlexandreDecan/portion) and follows its concepts.
The following features are provided:
- 2D-Intervals (rectangles) which can be open/closed and finite/infinite at every boundary
- intersection, union, complement and difference of rectilinear polygons
- iterator over all maximum rectangles inside and outside a given polygon
In the case of integers/floats it can be used to keep track of the area resulting
from the union/difference of rectangles:
<p align="center">
<img width="65%" src="https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_solid.gif">
</p>
Internally the library uses an [interval tree](https://en.wikipedia.org/wiki/Interval_tree) to represent a polygon.
## Table of contents
* [Installation](#installation)
* [Documentation & usage](#documentation--usage)
* [Polygon creation](#polygon-creation)
* [Polygon bounds & attributes](#polygon-bounds--attributes)
* [Polygon operations](#polygon-operations)
* [Rectangle partitioning iterator](#rectangle-partitioning-iterator)
* [Maximum rectangle iterator](#maximum-rectangle-iterator)
* [Boundary](#boundary)
* [Internal data structure](#internal-data-structure)
* [Changelog](#changelog)
* [Contributions](#contributions)
* [License](#license)
## Installation
`rportion` can be installed from [PyPi](https://pypi.org/project/rportion/) with `pip` using
```bash
pip install rportion
```
Alternatively, clone the repository and run
```bash
pip install -e ".[test]"
python -m unittest discover -s tests
```
Note that `python
## Documentation & usage
### Polygon creation
Atomic polygons (rectangles) can be created by one of the following:
```python
>>> import rportion as rp
>>> rp.ropen(0, 2, 0, 1)
(x=(0,2), y=(0,1))
>>> rp.rclosed(0, 2, 0, 1)
(x=[0,2], y=[0,1])
>>> rp.ropenclosed(0, 2, 0, 1)
(x=(0,2], y=(0,1])
>>> rp.rclosedopen(0, 2, 0, 1)
(x=[0,2), y=[0,1))
>>> rp.rsingleton(0, 1)
(x=[0], y=[1])
>>> rp.rempty()
(x=(), y=())
```
Polygons can also be created by using two intervals of the underlying library
[`portion`](https://github.com/AlexandreDecan/portion):
```python
>>> import portion as P
>>> import rportion as rp
>>> rp.RPolygon.from_interval_product(P.openclosed(0, 2), P.closedopen(0, 1))
(x=(0,2], y=[0,1))
```
[↑ back to top](#table-of-contents)
### Polygon bounds & attributes
An `RPolygon` defines the following properties
- `empty` is true if the polygon is empty.
```python
>>> rp.rclosed(0, 2, 1, 2).empty
False
>>> rp.rempty().empty
True
```
- `atomic` is true if the polygon can be expressed by a single rectangle.
```python
>>> rp.rempty().atomic
True
>>> rp.rclosedopen(0, 2, 1, 2).atomic
True
>>> (rp.rclosed(0, 2, 1, 2) | rp.rclosed(0, 2, 1, 3)).atomic
True
>>> (rp.rclosed(0, 2, 1, 2) | rp.rclosed(1, 2, 1, 3)).atomic
False
```
- `enclosure` is the smallest rectangle containing the polygon.
```python
>>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).enclosure
(x=[0,3], y=[0,2])
>>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).enclosure
(x=(-inf,+inf), y=[-3,3])
```
- `enclosure_x_interval` is the smallest rectangle containing the polygon's extension in x-dimension.
```python
>>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).x_enclosure_interval
x=[0,3]
>>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).x_enclosure_interval
(-inf,+inf)
```
- `enclosure_y_interval` is the smallest interval containing the polygon's extension in y-dimension.
```python
>>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).y_enclosure_interval
[0,2]
>>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).y_enclosure_interval
[-3,3]
```
- `x_lower`, `x_upper`, `y_lower` and `y_upper` yield the boundaries of the rectangle enclosing
the polygon.
```python
>>> p = rp.rclosedopen(0, 2, 1, 3)
>>> p.x_lower, p.x_upper, p.y_lower, p.y_upper
(0, 2, 1, 3)
```
- `x_left`, `x_right`, `y_left` and `y_right` yield the type of the boundaries of the rectangle enclosing
the polygon.
```python
>>> p = rp.rclosedopen(0, 2, 1, 3)
>>> p.x_left, p.x_right, p.y_left, p.y_right
(CLOSED, OPEN, CLOSED, OPEN)
```
[↑ back to top](#table-of-contents)
### Polygon operations
`RPolygon` instances support the following operations:
- `p.intersection(other)` and `p & other` return the intersection of two rectilinear polygons.
```python
>>> rp.rclosed(0, 2, 0, 2) & rp.rclosed(1, 3, 0, 1)
(x=[1,2], y=[0,1])
```
- `p.union(other)` and `p | other` return the union of two rectilinear polygons.
```python
>>> rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)
(x=[0,3], y=[0,1]) | (x=[0,2], y=[0,2])
```
Note that the resulting polygon is represented by the union of all maximal rectangles contained in
in the polygon, see [Maximum rectangle iterators](#maximum-rectangle-iterators).
- `p.complement()` and `~p` return the complement of the rectilinear polygon.
```python
>>> ~rp.ropen(-P.inf, 0, -P.inf, P.inf)
((x=[0,+inf), y=(-inf,+inf))
```
- `p.difference(other)` and `p - other` return the difference of two rectilinear polygons.
```python
rp.rclosed(0, 3, 0, 2) - rp.ropen(2, 4, 1, 3)
(x=[0,3], y=[0,1]) | (x=[0,2], y=[0,2])
```
Note that the resulting polygon is represented by the union of all maximal rectangles contained in
in the polygon, see [Maximum rectangle iterators](#maximum-rectangle-iterators).
[↑ back to top](#table-of-contents)
### Rectangle partitioning iterator
The method `rectangle_partitioning` of a `RPolygon` instance returns an iterator
over rectangles contained in the rectilinear polygon which disjunctively cover it. I.e.
```python
>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)
>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)
>>> list(poly.rectangle_partitioning())
[(x=[1,4), y=[2,3)), (x=[2,5), y=[1,2)), (x=[6,8), y=[1,2)), (x=[2,4), y=[3,4)), (x=[7,8), y=[2,3))]
```
which can be visualized as follows:
<p align="center">
<img width="95%" src="https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_partitioning.png">
</p>
**Left:** Simple Rectilinear polygon. The red areas are part of the polygon.<br>
**Right:** Rectangles in the portion are shown with black borderlines. As it is visible
`rectangle_partitioning` prefers rectangles with long x-interval over
rectangles with long y-interval.
[↑ back to top](#table-of-contents)
### Maximum rectangle iterator
The method `maximal_rectangles` of a `RPolygon` instance returns an iterator over all maximal rectangles contained
in the rectilinear polygon.
A maximal rectangle is rectangle in the polygon which is not a real subset of any other rectangle contained in
the rectilinear polygon. I.e.
```python
>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)
>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)
>>> list(poly.maximal_rectangles())
[(x=[1, 4), y = [2, 3)), (x=[2, 5), y = [1, 2)), (x=[6, 8), y = [1, 2)), (x=[2, 4), y = [1, 4)), (x=[7, 8), y = [1, 3))]
```
which can be visualized as follows:
<p align="center">
<img width="95%" src="https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_max-rectangles.png">
</p>
**Left:** Simple Rectilinear polygon. The red areas are part of the polygon.<br>
**Right:** Maximal contained rectangles are drawn above each other transparently.
[↑ back to top](#table-of-contents)
## Boundary
The method `boundary` of a `RPolygon` instance returns another `RPolygon` instance representing the boundary of
the polygon. I.e.
```python
>>> poly = rp.closed(0, 1, 2, 3)
>>> poly.boundary()
(x=[1,2], y=[3]) | (x=[1,2], y=[4]) | (x=[1], y=[3,4]) | (x=[2], y=[3,4])
```
[↑ back to top](#table-of-contents)
## Internal data structure
The polygon is internally stored using an [interval tree](https://en.wikipedia.org/wiki/Interval_tree). Every
node of the tree corresponds to an interval in x-dimension which is representable by boundaries (in x-dimension)
present in the polygon. Each node contains an 1D-interval (by using the library
[`portion`](https://github.com/AlexandreDecan/portion)) in y-dimension. Combining those 1D-intervals
yields a rectangle contained in the polygon.
I.e. for the rectangle `(x=[0, 2), y=[1, 3))` this can be visualized as follows.
```
interval tree with x-interval corresponding y-interval stored in
a lattice-like shape to each node each node
┌─x─┐ ┌─(-∞,+∞)─┐ ┌─()──┐
│ │ │ │ │ │
┌─x─┬─x─┐ ┌─(-∞,2)──┬──[0,+∞)─┐ ┌─()──┬──()─┐
│ │ │ │ │ │ │ │ │
x x x (-∞,0] [0,2) [2,+∞) () [1,3) ()
```
The class `RPolygon` used this model by holding three data structures.
- `_x_boundaries`: Sorted list of necessary boundaries in x-dimension with type (`OPEN` or `CLOSED`)
- `_used_y_ranges`: List of lists in a triangular shape representing the interval tree for the
space occupied by the rectilinear polygon.
- `_free_y_ranges`: List of list in a triangular shape representing the interval tree of
for the space not occupied by the rectilinear polygon.
Note that a separate data structure for the area outside the polygon is kept.
This is done in order to be able to obtain the complement of a polygon efficiently.
For the example shown above this is:
```python
>>> poly = rp.rclosedopen(0, 2, 1, 3)
>>> poly._x_boundaries
SortedList([(-inf, OPEN), (0, OPEN), (2, OPEN), (+inf, OPEN)])
>>> poly._used_y_ranges
[[(), (), ()],
[(), [1,3)],
[()]]
>>> poly._free_y_ranges
[[(-inf,1) | [3,+inf), (-inf,1) | [3,+inf), (-inf,+inf)],
[(-inf,1) | [3,+inf), (-inf,1) | [3,+inf)],
[(-inf,+inf)]]
```
You can use the function `data_tree_to_string` as noted below to print the internal data structure in a tabular format:
```python
>>> poly = rp.rclosedopen(0, 2, 1, 3)
>>> print(data_tree_to_string(poly._x_boundaries, poly._used_y_ranges, 6))
| +inf 2 0
----------------+------------------
-inf (OPEN)| () () ()
0 (CLOSED)| () [1,3)
2 (CLOSED)| ()
```
```python
>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)
>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)
>>> print(data_tree_to_string(poly._x_boundaries, poly._used_y_ranges, 6))
| +inf 8 7 6 5 4 2 1
----------------+------------------------------------------------
-inf (OPEN)| () () () () () () () ()
1 (CLOSED)| () () () () () [2,3) [2,3)
2 (CLOSED)| () () () () [1,2) [1,4)
4 (CLOSED)| () () () () [1,2)
5 (CLOSED)| () () () ()
6 (CLOSED)| () [1,2) [1,2)
7 (CLOSED)| () [1,3)
```
```python
def data_tree_to_string(x_boundaries,
y_intervals,
spacing: int):
col_space = 10
n = len(y_intervals)
msg = " " * (spacing + col_space) + "|"
for x_b in x_boundaries[-1:0:-1]:
msg += f"{str(x_b.val):>{spacing}}"
msg += "\n" + f"-" * (spacing+col_space) + "+"
for i in range(n):
msg += f"-" * spacing
msg += "\n"
for i, row in enumerate(y_intervals):
x_b = x_boundaries[i]
msg += f"{str((~x_b).val) + ' (' + str((~x_b).btype) + ')':>{spacing+ col_space}}|"
for val in row:
msg += f"{str(val):>{spacing}}"
msg += "\n"
return msg
```
[↑ back to top](#table-of-contents)
## Changelog
This library adheres to a [semantic versioning](https://semver.org/) scheme.
See [CHANGELOG.md](https://github.com/tilmann-bartsch/rportion/blob/master/CHANGELOG.md) for the list of changes.
## Contributions
Contributions are very welcome! Feel free to report bugs or suggest new features using GitHub issues and/or pull requests.
## License
Distributed under [MIT License](https://github.com/tilmann-bartsch/rportion/blob/master/LICENSE).
Raw data
{
"_id": null,
"home_page": "https://github.com/tilmann-bartsch/rportion",
"name": "rportion",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "rectangle polygon interval-tree",
"author": "Tilmann Bartsch",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/81/3c/ab8c1ad3c2f4615800a4afe27715350c912da36c92d69dddabbee916cd06/rportion-0.2.0.tar.gz",
"platform": null,
"description": "# rportion - data structure and operations for rectilinear polygons\n\n\n[](https://pypi.org/project/rportion/)\n[](https://github.com/tilmann-bartsch/portion/actions/workflows/test.yaml)\n[](https://coveralls.io/github/tilmann-bartsch/rportion?branch=master)\n[](https://opensource.org/licenses/MIT)\n[](https://github.com/tilmann-bartsch/rportion/commits/master)\n\nThe `rportion` library provides data structure to represent \n2D [rectilinear polygons](https://en.wikipedia.org/wiki/Rectilinear_polygon) (unions of 2D-intervals) in Python 3.9+.\nIt is built upon the library [`portion`](https://github.com/AlexandreDecan/portion) and follows its concepts.\nThe following features are provided:\n\n - 2D-Intervals (rectangles) which can be open/closed and finite/infinite at every boundary\n - intersection, union, complement and difference of rectilinear polygons\n - iterator over all maximum rectangles inside and outside a given polygon\n\nIn the case of integers/floats it can be used to keep track of the area resulting \nfrom the union/difference of rectangles:\n\n<p align=\"center\">\n <img width=\"65%\" src=\"https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_solid.gif\">\n</p>\n\nInternally the library uses an [interval tree](https://en.wikipedia.org/wiki/Interval_tree) to represent a polygon.\n\n## Table of contents\n\n * [Installation](#installation)\n * [Documentation & usage](#documentation--usage)\n * [Polygon creation](#polygon-creation)\n * [Polygon bounds & attributes](#polygon-bounds--attributes)\n * [Polygon operations](#polygon-operations)\n * [Rectangle partitioning iterator](#rectangle-partitioning-iterator)\n * [Maximum rectangle iterator](#maximum-rectangle-iterator)\n * [Boundary](#boundary)\n * [Internal data structure](#internal-data-structure)\n * [Changelog](#changelog)\n * [Contributions](#contributions)\n * [License](#license)\n\n## Installation\n\n`rportion` can be installed from [PyPi](https://pypi.org/project/rportion/) with `pip` using \n\n```bash\npip install rportion\n```\n\nAlternatively, clone the repository and run\n\n```bash\npip install -e \".[test]\"\npython -m unittest discover -s tests\n```\n\nNote that `python\n\n## Documentation & usage\n\n### Polygon creation\n\nAtomic polygons (rectangles) can be created by one of the following:\n```python\n>>> import rportion as rp\n>>> rp.ropen(0, 2, 0, 1)\n(x=(0,2), y=(0,1))\n>>> rp.rclosed(0, 2, 0, 1)\n(x=[0,2], y=[0,1])\n>>> rp.ropenclosed(0, 2, 0, 1)\n(x=(0,2], y=(0,1])\n>>> rp.rclosedopen(0, 2, 0, 1)\n(x=[0,2), y=[0,1))\n>>> rp.rsingleton(0, 1)\n(x=[0], y=[1])\n>>> rp.rempty()\n(x=(), y=())\n```\n\nPolygons can also be created by using two intervals of the underlying library \n[`portion`](https://github.com/AlexandreDecan/portion):\n```python\n>>> import portion as P\n>>> import rportion as rp\n>>> rp.RPolygon.from_interval_product(P.openclosed(0, 2), P.closedopen(0, 1))\n(x=(0,2], y=[0,1))\n```\n\n[↑ back to top](#table-of-contents)\n### Polygon bounds & attributes\n\nAn `RPolygon` defines the following properties\n - `empty` is true if the polygon is empty.\n ```python\n >>> rp.rclosed(0, 2, 1, 2).empty\n False\n >>> rp.rempty().empty\n True\n ```\n - `atomic` is true if the polygon can be expressed by a single rectangle.\n ```python\n >>> rp.rempty().atomic\n True\n >>> rp.rclosedopen(0, 2, 1, 2).atomic\n True\n >>> (rp.rclosed(0, 2, 1, 2) | rp.rclosed(0, 2, 1, 3)).atomic\n True\n >>> (rp.rclosed(0, 2, 1, 2) | rp.rclosed(1, 2, 1, 3)).atomic\n False\n ```\n - `enclosure` is the smallest rectangle containing the polygon.\n ```python\n >>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).enclosure\n (x=[0,3], y=[0,2])\n >>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).enclosure\n (x=(-inf,+inf), y=[-3,3])\n ```\n - `enclosure_x_interval` is the smallest rectangle containing the polygon's extension in x-dimension.\n ```python\n >>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).x_enclosure_interval\n x=[0,3]\n >>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).x_enclosure_interval\n (-inf,+inf)\n ```\n - `enclosure_y_interval` is the smallest interval containing the polygon's extension in y-dimension.\n ```python\n >>> (rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)).y_enclosure_interval\n [0,2]\n >>> (rp.rclosed(0, 1, -3, 3) | rp.rclosed(-P.inf, P.inf, -1, 1)).y_enclosure_interval\n [-3,3]\n ```\n - `x_lower`, `x_upper`, `y_lower` and `y_upper` yield the boundaries of the rectangle enclosing\n the polygon.\n ```python\n >>> p = rp.rclosedopen(0, 2, 1, 3)\n >>> p.x_lower, p.x_upper, p.y_lower, p.y_upper\n (0, 2, 1, 3)\n ```\n - `x_left`, `x_right`, `y_left` and `y_right` yield the type of the boundaries of the rectangle enclosing\n the polygon.\n ```python\n >>> p = rp.rclosedopen(0, 2, 1, 3)\n >>> p.x_left, p.x_right, p.y_left, p.y_right\n (CLOSED, OPEN, CLOSED, OPEN)\n ```\n\n\n[↑ back to top](#table-of-contents)\n### Polygon operations\n\n`RPolygon` instances support the following operations:\n - `p.intersection(other)` and `p & other` return the intersection of two rectilinear polygons.\n ```python\n >>> rp.rclosed(0, 2, 0, 2) & rp.rclosed(1, 3, 0, 1)\n (x=[1,2], y=[0,1])\n ```\n - `p.union(other)` and `p | other` return the union of two rectilinear polygons.\n ```python\n >>> rp.rclosed(0, 2, 0, 2) | rp.rclosed(1, 3, 0, 1)\n (x=[0,3], y=[0,1]) | (x=[0,2], y=[0,2])\n ```\n Note that the resulting polygon is represented by the union of all maximal rectangles contained in\n in the polygon, see [Maximum rectangle iterators](#maximum-rectangle-iterators).\n - `p.complement()` and `~p` return the complement of the rectilinear polygon.\n ```python\n >>> ~rp.ropen(-P.inf, 0, -P.inf, P.inf)\n ((x=[0,+inf), y=(-inf,+inf))\n ```\n - `p.difference(other)` and `p - other` return the difference of two rectilinear polygons.\n ```python\n rp.rclosed(0, 3, 0, 2) - rp.ropen(2, 4, 1, 3)\n (x=[0,3], y=[0,1]) | (x=[0,2], y=[0,2])\n ```\n Note that the resulting polygon is represented by the union of all maximal rectangles contained in\n in the polygon, see [Maximum rectangle iterators](#maximum-rectangle-iterators).\n\n[↑ back to top](#table-of-contents)\n### Rectangle partitioning iterator\n\nThe method `rectangle_partitioning` of a `RPolygon` instance returns an iterator\nover rectangles contained in the rectilinear polygon which disjunctively cover it. I.e.\n\n```python\n>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)\n>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)\n>>> list(poly.rectangle_partitioning())\n[(x=[1,4), y=[2,3)), (x=[2,5), y=[1,2)), (x=[6,8), y=[1,2)), (x=[2,4), y=[3,4)), (x=[7,8), y=[2,3))]\n```\n\nwhich can be visualized as follows:\n<p align=\"center\">\n <img width=\"95%\" src=\"https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_partitioning.png\">\n</p>\n\n**Left:** Simple Rectilinear polygon. The red areas are part of the polygon.<br>\n**Right:** Rectangles in the portion are shown with black borderlines. As it is visible \n `rectangle_partitioning` prefers rectangles with long x-interval over \n rectangles with long y-interval.\n \n\n\n[↑ back to top](#table-of-contents)\n### Maximum rectangle iterator\n\nThe method `maximal_rectangles` of a `RPolygon` instance returns an iterator over all maximal rectangles contained\nin the rectilinear polygon.\n\nA maximal rectangle is rectangle in the polygon which is not a real subset of any other rectangle contained in\nthe rectilinear polygon. I.e. \n\n```python\n>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)\n>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)\n>>> list(poly.maximal_rectangles())\n[(x=[1, 4), y = [2, 3)), (x=[2, 5), y = [1, 2)), (x=[6, 8), y = [1, 2)), (x=[2, 4), y = [1, 4)), (x=[7, 8), y = [1, 3))]\n```\nwhich can be visualized as follows:\n<p align=\"center\">\n <img width=\"95%\" src=\"https://github.com/tilmann-bartsch/rportion/raw/master/docu/simple-example_max-rectangles.png\">\n</p>\n\n**Left:** Simple Rectilinear polygon. The red areas are part of the polygon.<br>\n**Right:** Maximal contained rectangles are drawn above each other transparently.\n\n[↑ back to top](#table-of-contents)\n## Boundary\n\nThe method `boundary` of a `RPolygon` instance returns another `RPolygon` instance representing the boundary of\nthe polygon. I.e.\n\n```python\n>>> poly = rp.closed(0, 1, 2, 3)\n>>> poly.boundary()\n(x=[1,2], y=[3]) | (x=[1,2], y=[4]) | (x=[1], y=[3,4]) | (x=[2], y=[3,4])\n```\n\n[↑ back to top](#table-of-contents)\n## Internal data structure\n\nThe polygon is internally stored using an [interval tree](https://en.wikipedia.org/wiki/Interval_tree). Every\nnode of the tree corresponds to an interval in x-dimension which is representable by boundaries (in x-dimension) \npresent in the polygon. Each node contains an 1D-interval (by using the library\n[`portion`](https://github.com/AlexandreDecan/portion)) in y-dimension. Combining those 1D-intervals\nyields a rectangle contained in the polygon.\n\nI.e. for the rectangle `(x=[0, 2), y=[1, 3))` this can be visualized as follows.\n```\n interval tree with x-interval corresponding y-interval stored in\n a lattice-like shape to each node each node\n \u250c\u2500x\u2500\u2510 \u250c\u2500(-\u221e,+\u221e)\u2500\u2510 \u250c\u2500()\u2500\u2500\u2510\n \u2502 \u2502 \u2502 \u2502 \u2502 \u2502\n \u250c\u2500x\u2500\u252c\u2500x\u2500\u2510 \u250c\u2500(-\u221e,2)\u2500\u2500\u252c\u2500\u2500[0,+\u221e)\u2500\u2510 \u250c\u2500()\u2500\u2500\u252c\u2500\u2500()\u2500\u2510\n \u2502 \u2502 \u2502 \u2502 \u2502 \u2502 \u2502 \u2502 \u2502\n x x x (-\u221e,0] [0,2) [2,+\u221e) () [1,3) ()\n```\nThe class `RPolygon` used this model by holding three data structures.\n - `_x_boundaries`: Sorted list of necessary boundaries in x-dimension with type (`OPEN` or `CLOSED`)\n - `_used_y_ranges`: List of lists in a triangular shape representing the interval tree for the\n space occupied by the rectilinear polygon.\n - `_free_y_ranges`: List of list in a triangular shape representing the interval tree of\n for the space not occupied by the rectilinear polygon.\n\nNote that a separate data structure for the area outside the polygon is kept.\nThis is done in order to be able to obtain the complement of a polygon efficiently.\n\nFor the example shown above this is:\n```python\n>>> poly = rp.rclosedopen(0, 2, 1, 3)\n>>> poly._x_boundaries\nSortedList([(-inf, OPEN), (0, OPEN), (2, OPEN), (+inf, OPEN)])\n>>> poly._used_y_ranges\n[[(), (), ()], \n [(), [1,3)], \n [()]]\n>>> poly._free_y_ranges\n[[(-inf,1) | [3,+inf), (-inf,1) | [3,+inf), (-inf,+inf)], \n [(-inf,1) | [3,+inf), (-inf,1) | [3,+inf)], \n [(-inf,+inf)]]\n```\n\nYou can use the function `data_tree_to_string` as noted below to print the internal data structure in a tabular format:\n\n```python\n>>> poly = rp.rclosedopen(0, 2, 1, 3)\n>>> print(data_tree_to_string(poly._x_boundaries, poly._used_y_ranges, 6))\n | +inf 2 0\n----------------+------------------\n -inf (OPEN)| () () ()\n 0 (CLOSED)| () [1,3)\n 2 (CLOSED)| ()\n```\n\n```python\n>>> poly = rp.rclosedopen(2, 5, 1, 4) | rp.rclosedopen(1, 8, 2, 3) | rp.rclosedopen(6, 8, 1, 3)\n>>> poly = poly - rp.rclosedopen(4, 7, 2, 4)\n>>> print(data_tree_to_string(poly._x_boundaries, poly._used_y_ranges, 6))\n | +inf 8 7 6 5 4 2 1\n----------------+------------------------------------------------\n -inf (OPEN)| () () () () () () () ()\n 1 (CLOSED)| () () () () () [2,3) [2,3)\n 2 (CLOSED)| () () () () [1,2) [1,4)\n 4 (CLOSED)| () () () () [1,2)\n 5 (CLOSED)| () () () ()\n 6 (CLOSED)| () [1,2) [1,2)\n 7 (CLOSED)| () [1,3)\n```\n\n```python\ndef data_tree_to_string(x_boundaries,\n y_intervals,\n spacing: int):\n col_space = 10\n n = len(y_intervals)\n msg = \" \" * (spacing + col_space) + \"|\"\n for x_b in x_boundaries[-1:0:-1]:\n msg += f\"{str(x_b.val):>{spacing}}\"\n msg += \"\\n\" + f\"-\" * (spacing+col_space) + \"+\"\n for i in range(n):\n msg += f\"-\" * spacing\n msg += \"\\n\"\n for i, row in enumerate(y_intervals):\n x_b = x_boundaries[i]\n msg += f\"{str((~x_b).val) + ' (' + str((~x_b).btype) + ')':>{spacing+ col_space}}|\"\n for val in row:\n msg += f\"{str(val):>{spacing}}\"\n msg += \"\\n\"\n return msg\n```\n\n[↑ back to top](#table-of-contents)\n## Changelog\nThis library adheres to a [semantic versioning](https://semver.org/) scheme.\nSee [CHANGELOG.md](https://github.com/tilmann-bartsch/rportion/blob/master/CHANGELOG.md) for the list of changes.\n\n## Contributions\nContributions are very welcome! Feel free to report bugs or suggest new features using GitHub issues and/or pull requests.\n\n## License\nDistributed under [MIT License](https://github.com/tilmann-bartsch/rportion/blob/master/LICENSE).\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Python data structure and operations for 2-dimensional rectilinear polygons",
"version": "0.2.0",
"project_urls": {
"Homepage": "https://github.com/tilmann-bartsch/rportion"
},
"split_keywords": [
"rectangle",
"polygon",
"interval-tree"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "e6bba87d3cdaec835f4fe71b70dadeffa85f4b82e833449bcbc32c412c37cff6",
"md5": "bfe8e9941b1b14c2832c9d96e8e8dfbc",
"sha256": "f68ea45bfeac8ba1a655dcdf2d5551f803c140900471f95fcf883e6db1ed6076"
},
"downloads": -1,
"filename": "rportion-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "bfe8e9941b1b14c2832c9d96e8e8dfbc",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 11973,
"upload_time": "2024-04-02T12:25:13",
"upload_time_iso_8601": "2024-04-02T12:25:13.276380Z",
"url": "https://files.pythonhosted.org/packages/e6/bb/a87d3cdaec835f4fe71b70dadeffa85f4b82e833449bcbc32c412c37cff6/rportion-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "813cab8c1ad3c2f4615800a4afe27715350c912da36c92d69dddabbee916cd06",
"md5": "ed8788a4cfbfb19f742d6bffe477667a",
"sha256": "c7fd6c2b46c904fcf38cdb7505b69efdc7c4423ac973149b5eaad51b92ae5848"
},
"downloads": -1,
"filename": "rportion-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "ed8788a4cfbfb19f742d6bffe477667a",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 21090,
"upload_time": "2024-04-02T12:25:14",
"upload_time_iso_8601": "2024-04-02T12:25:14.808345Z",
"url": "https://files.pythonhosted.org/packages/81/3c/ab8c1ad3c2f4615800a4afe27715350c912da36c92d69dddabbee916cd06/rportion-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-02 12:25:14",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "tilmann-bartsch",
"github_project": "rportion",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "rportion"
}
JSON
