tulip-control / polytope

Geometric operations on polytopes of any dimension
https://pypi.org/project/polytope
Other
73 stars 19 forks source link

With large scales `reduce` can remove non-redundant hyperplanes #74

Closed matthewearl closed 2 years ago

matthewearl commented 2 years ago

Hyperplanes whose b element is large relative to their A row can be incorrectly removed with default tolerances:

import numpy as np
import polytope

# construct a 10x10 square centred on (-95, 0)
box = polytope.Polytope.from_box([[-1000, -990], [-5, 5]])

# split the box in two by adding a plane through y=995
half_box = polytope.Polytope(
    np.concatenate([[[1, 0]], box.A], axis=0),
    np.concatenate([[-995], box.b], axis=0),
)

# validate the volume of the half box (prints 50, correct)
print(half_box.volume)

# reduce the half box and check its volume (prints 100, incorrect)
print(polytope.reduce(half_box).volume)

The non-redundant hyperplane is removed by the part of reduce that removes linearly dependent rows: https://github.com/tulip-control/polytope/blob/main/polytope/polytope.py#L1109

krooken commented 2 years ago

I think this is the same problem as seen in tulip-control/tulip-control#239 and they both might be solved by #66.

matthewearl commented 2 years ago

This seems to fix the problem, thanks!