Metadata-Version: 2.4
Name: polypart
Version: 0.1.1
Summary: Robust polytope partitioning and efficient point classification in Python
Author-email: Sergio Herreros Pérez <sergio.herreros@alu.icai.comillas.edu>, David Alfaya Sánchez <dalfaya@icai.comillas.edu>, Jaime Pizarroso Gonzalo <jpizarroso@comillas.edu>
License: MIT License
        
        Copyright (c) 2025 CIAMOD
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Repository, https://github.com/CIAMOD/polypart
Project-URL: Changelog, https://github.com/CIAMOD/polypart/blob/master/CHANGELOG.md
Keywords: polytope,partition,hyperplane arrangement,point location,decision tree
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development :: Libraries
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24.4
Requires-Dist: pycddlib>=3.0.2
Dynamic: license-file

[![PyPI](https://img.shields.io/pypi/v/polypart.svg)](https://pypi.org/project/polypart/)
[![PyPI Downloads](https://static.pepy.tech/personalized-badge/polypart?period=total&units=INTERNATIONAL_SYSTEM&left_color=GREY&right_color=GREEN&left_text=downloads)](https://pepy.tech/projects/polypart)
[![Python](https://img.shields.io/badge/python-%5E3.10-blue)](https://www.python.org/downloads/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)
[![GitHub Repo](https://img.shields.io/static/v1?message=Repo&logo=github&labelColor=grey&color=black&logoColor=white&label=GitHub)](https://github.com/ciamod/polypart)

<p align="left">
  <img width="470" alt="polypart-logo" src="https://raw.githubusercontent.com/CIAMOD/polypart/develop/images/polypart-logo.png" />
</p>

PolyPart is a Python package for **partitioning d-dimensional convex polytopes** by affine hyperplane arrangements. The algorithm works by iteratively slicing the polytope with hyperplanes and organizing the resulting subdivisions into a **decision tree**, which enables:

- Counting the exact number of regions
- Efficient point classification into the corresponding region

All computations use exact rational arithmetic, which ensures robustness and eliminates floating-point errors. The implementation builds on [`pycddlib`](https://pypi.org/project/pycddlib/) with GMP to provide efficient and reliable polyhedral computations.

## 🚀 Quick Start

### Prerequisites

- Python >= 3.10.6
- numpy >= 1.24.4
- pycddlib >= 3.0.2

### Installation

1. Install the package from PyPI

```sh
pip install polypart
```

2. Import the package in your Python code
```python
import polypart
```

### Basic Usage

```python
from fractions import Fraction
from polypart.geometry import Polytope, Hyperplane
from polypart.ppart import build_partition_tree
from polypart.io import save_tree

# 1. Create initial polytope object in H-representation
# unit square: 0 <= x <= 1, 0 <= y <= 1
A = [[-1, 0], [1, 0], [0, -1], [0, 1]]
b = [0, 1, 0, 1]
square = Polytope(A, b) # expressed as A x <= b
square.extreme()  # compute vertices (Optional)

h1 = Hyperplane.from_coefficients([1, 0, Fraction(1, 3)]) # x = 1/3
h2 = Hyperplane.from_coefficients([0, 1, Fraction(1, 3)]) # y = 1/3

tree, n_parts = build_partition_tree(square, [h1, h2])
save_tree(tree, "data/square_partitions.json")
print("Number of regions:", n_parts)

# Output: 'Number of regions: 4'
```

## 🎯 Examples

Complete Jupyter notebooks providing guided, reproducible demonstrations of how to use PolyPart are available in the [examples folder](https://github.com/ciamod/polypart/examples):

- [**Partitioning_Unit_Square.ipynb**](https://github.com/CIAMOD/polypart/tree/master/examples/Partitioning_Unit_Square.ipynb)
 
  Demonstrates the algorithm on a simple, visual case: partitioning the unit square with three hyperplanes. Includes a plot of the resulting regions and new random points classified into their respective regions using the partition tree.

- [**Moduli_Stability_Chambers.ipynb**](https://github.com/CIAMOD/polypart/tree/master/examples/Moduli_Stability_Chambers.ipynb)
  A higher-dimensional research application on moduli spaces of parabolic vector bundles.


## 📜 License

This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.

## 👥 Authors

- ***Sergio Herreros Pérez***, Institute for Research in Technology, ICAI, Comillas Pontifical University
- ***José Portela González***, Department of Quantitative Methods, ICADE, Comillas Pontifical University and Institute for Research in Technology, IIT, Comillas Pontifical University
- ***David Alfaya Sánchez***, Department of Applied Mathematics and Institute for Research in Technology, ICAI, Comillas Pontifical University
- ***Jaime Pizarroso Gonzalo***, Department of Telematics and Computing and Institute for Research in Technology, ICAI, Comillas Pontifical University, and Santalucía Chair of Analytics for Education.

## 🙌 Acknowledgments

This research was supported by project CIAMOD (Applications of computational methods and artificial intelligence to the study of moduli spaces, project PP2023_9) funded by Convocatoria de Financiación de Proyectos de Investigación Propios 2023, Universidad Pontificia Comillas, and by grants PID2022-142024NB-I00 and RED2022-134463-T funded by MCIN/AEI/10.13039/501100011033.

Find more about the CIAMOD project in the [project webpage](https://ciamod.github.io/) and the [IIT proyect webpage](https://www.iit.comillas.edu/publicacion/proyecto/en/CIAMOD/Aplicaciones_de_m%c3%a9todos_computacionales_y_de_inteligencia_artificial_al_estudio_de_espacios_de_moduli).

Special thanks to everyone who contributed to the project:

- David Alfaya Sánchez (PI), Department of Applied Mathematics and Institute for Research in Technology, ICAI, Comillas Pontifical University
- Javier Rodrigo Hitos, Department of Applied Mathematics, ICAI, Comillas Pontifical University
- Luis Ángel Calvo Pascual, Department of Quantitative Methods, ICADE, Comillas Pontifical University
- Anitha Srinivasan, Department of Quantitative Methods, ICADE, Comillas Pontifical University
- José Portela González, Department of Quantitative Methods, ICADE, IIT, Comillas Pontifical University
- Jaime Pizarroso Gonzalo, Department of Telematics and Computing and Institute for Research in Technology, ICAI, Comillas Pontifical University
- Tomás Luis Gómez de Quiroga, Institute of Mathematical Sciences, UAM-UCM-UC3M-CSIC
- Daniel Sánchez Sánchez, Student of the Degree in Mathematical Engineering and Artificial Intelligence, Institute for Research in Technology, ICAI, Comillas Pontifical University
- Alejandro Martínez de Guinea García, Student of the Degree in Mathematical Engineering and Artificial Intelligence, Institute for Research in Technology, ICAI, Comillas Pontifical University
- Sergio Herreros Pérez, Student of the Degree in Mathematical Engineering and Artificial Intelligence, Institute for Research in Technology, ICAI, Comillas Pontifical University

## 📚 References

- *David Alfaya, Sergio Herreros, Jaime Pizarroso, José Portela, and Javier Rodrigo*, **"A Computational Analysis of Ismorphism Classes of Moduli Spaces of Parabolic Vector Bundles"**, *in preparation*, 2025.
- *David Alfaya, Sergio Herreros, Jaime Pizarroso and José Portela*, **"PolyPart: Exact Partitioning of Convex Polytopes uisng Decision Trees"**, *in preparation*, 2025.
