KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#dsh #dsh-plugin #ai-agent #developer-tools #codex #typescript #cli #deepseek-harness #claude-code #ai-agents #mcp #rust

pydecomp

★ 33 Open GitHub ↗

A Python based implementation for fast convex decomposition of obstacle-free spaces.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

![Logo](https://github.com/jonarriza96/pydecomp/raw/main/docs/logo/logo.png)
**pydecomp — A Python implementation of <a href="https://github.com/sikang/DecompUtil/tree/master">DecompUtil<sup></sup></a> for fast convex decomposition of obstacle-free spaces.**

[![PyPI version](https://badge.fury.io/py/pydecomp.svg)](https://badge.fury.io/py/pydecomp)
![PyPI - Python Version](https://img.shields.io/pypi/pyversions/pydecomp)
![PyPI - License](https://img.shields.io/pypi/l/pydecomp)
![PyPI - Downloads](https://img.shields.io/pypi/dm/pydecomp)

## Quickstart

Install dependencies the following:

* Linux:
    ```
        sudo apt-get install libcdd-dev libblas3 libblas-dev liblapack3 liblapack-dev gfortran
    ```

* Mac:
    ```
        brew install cddlib gmp eigen openblas cython boost
    ```

*Note*: Remember to set `LDFLAGS` and `CPPFLAGS` to the correct paths for the libraries.

In a virtual environment, install from PyPI with

```
    pip install pydecomp
```

### Conda

`pycddlib` does not ship Linux/macOS wheels, so `pip` builds it from source and
needs the `cddlib` C headers. In a conda environment the easiest path is to let
conda-forge supply `cddlib` and point pip at the env's include/lib paths:

```bash
conda create -n pydecomp_env python=3.12 -y
conda activate pydecomp_env
conda install -c conda-forge cddlib tk -y           # tk gives matplotlib a working GUI backend

export CPPFLAGS="-I$CONDA_PREFIX/include"
export LDFLAGS="-L$CONDA_PREFIX/lib"

pip install pydecomp
python -c "import pydecomp; print(pydecomp.__version__)"
```

If `plt.show()` produces no window, `matplotlib` has no interactive backend —
`conda install -c conda-forge tk` (above) fixes it; alternatively
`pip install pyqt5`.

## Examples

Forest - 2D | Office - 2D | Office - 3D
:-------------------------:|:-------------------------:|:-------------------------:
![](https://github.com/jonarriza96/pydecomp/raw/main/docs/forest.png) | ![](https://github.com/jonarriza96/pydecomp/raw/main/docs/office.png) | ![](https://github.com/jonarriza96/pydecomp/raw/main/docs/office_3d.png)

Given an occupancy grid map and a pieciwise linear path, the package returns a convex decomposition of the free space. The free space is represented by a collection of convex sets, whose halspace representation fulfills ` Ax-b<0`. The package returns the matrixes `A` and `b` for each convex set. The matrix `A` is a `n x 3` matrix and `b` is a `n x 1` vector, where `n` is the number of planes in the halfspace.

To check a script to perform a convex decomposition out of a given occupancy grid map, see [this file](examples/ptcloud_decomp_2D.py) for a planar (2D) case or [this file](examples/ptcloud_decomp_3D.py) for a spatial (3D) case. We provide two exemplary maps (forest and office), which you can select by modifying [this line](examples/ptcloud_decomp_2D.py#L8).

For the most minimal example see [this file](examples/ellipsoid_decomp_2D.py), which replicates a [test case](https://github.com/sikang/DecompUtil/blob/master/test/test_ellipsoid_decomp.cpp) in the original <a href="https://github.com/sikang/DecompUtil/tree/master">DecompUtil<sup></sup></a> repository.

https://github.com/jonarriza96/pydecomp/blob/1d1c6f97d6eff1f2b3b90bdb2f038eed0caa8578/examples/ellipsoid_decomp_2D.py#L5-L19

## Installing from source

After installing the dependencies given above, initialize git submodules with

```
    git submodule init
    git submodule update
```

Install the package with

```
    pip install .
```

## Citing

If you use this framework please cite our papers:

```
@misc{arrizabalaga2024differentiablecollisionfreeparametriccorridors,
      title={Differentiable Collision-Free Parametric Corridors}, 
      author={Jon Arrizabalaga and Zachary Manchester and Markus Ryll},
      year={2024},
      eprint={2407.12283},
      archivePrefix={arXiv},
      primaryClass={cs.RO},
      url={https://arxiv.org/abs/2407.12283}, 
}
```

```
@inproceedings{arrizabalaga2023sctomp,
  title={SCTOMP: Spatially Constrained Time-Optimal Motion Planning},
  author={Arrizabalaga, Jon and Ryll, Markus},
  booktitle={2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
  pages={4827--4834},
  year={2023},
  organization={IEEE}
}
```
## Related repositories
For computing continuous and differentiable collision-free corridors, check out [CorrGen](https://github.com/jonarriza96/corrgen)!

pydecomp

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README