search

tulip-control / polytope

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

Region diff fix #67

Open krooken opened 3 years ago

krooken commented 3 years ago

The purpose of the function region_diff() is to remove a set of polytopes (a region, the subtrahend) from one polytope (the minuend). The result may be a single polytope if the result is convex, or multiple polytopes (a single region).

The function region_diff() does not produce the correct result for certain input. For instance, when the minuend is a unit square and the subtrahend is two squares with side 0.5 positioned at [(0, 0), (0.5, 0.5)] and [(0.5, 0.5), (1, 1)], the result produced by region_diff() incorrectly includes the square [(0, 0), (0.5, 0.5)]. The issue is the code that prunes the search tree when none of the remaining polytopes removes anything from the current set of hyperplanes.

The algorithm is a depth first search algorithm implemented in a while loop. It has a set of hyperplanes which is initialized to the minuend. It then works by branching on the hyperplanes of the subtrahend. At each branchin point the set of hyperplanes is partitioned into two by one of the hyperplanes of the subtrahend.

A recursive version of the algorithm is described in Algorithm 2 in:

Mato Baotic "Polytopic computations in constrained optimal control" Automatika, 2009

When none of the remaining polytopes intersects the current set of hyperplanes, some things hold:

This PR:

murrayrm commented 3 years ago

It would be great to get a review of this from @tichakornw or @johnyf if they have time, since they would be able to spot errors better than I could.

krooken commented 3 years ago

The more the merrier. I thought it was quite difficult to find a solution, so it might be a good idea to do some iterations before accepting this PR.

krooken commented 3 years ago

Nice! Thank you for the review comments. I will start looking at them this week, but it will take some time to go through them.

I agree that the change of the algorithm in commit e7036dc is quite big and that it is difficult to understand how the change affects the search tree. If it was implemented with recursion it would be simpler to understand and to correct, but such a solution would potentially use a lot of stack memory.

I went through the while loop several times when I was debugging. I will try to write down step-by-step how the old implementation fails and how the new version fixes it.

johnyf commented 3 years ago

Indeed, I agree that a recursive implementation would be more readable, and that in CPython it would also be more limited, due to the potential for raising a RecursionError.

johnyf commented 3 years ago

Yet another observation in support of using the imperative mood when titling commit messages: the changes to the LaTeX kernel and to LaTeX packages in the LaTeX news have such titles, for example: https://www.latex-project.org/news/latex2e-news/ltnews30.pdf. This is an addendum to my comment above (https://github.com/tulip-control/polytope/pull/67#pullrequestreview-627817356).

krooken commented 3 years ago

I think all review comments should be addressed now. I tried to explain how and why the algorithm failed before and how the fix solves it, but the code change is still the same as before.

johnyf commented 3 years ago

Thank you for revising the changes, I will review the revised changes.

johnyf commented 2 years ago

A note that while reviewing the changes of this pull request, I had encountered issues in a function in the call graph of the function region_diff (I think it is the function polytope.polytope.reduce). The issues may require re-implementing the function reduce, and possibly also other functions in the module polytope.polytope.

These issues caused errors in the tests of tulip. A re-implementation of parts of the module polytope.polytope may be needed, to avoid these errors. The current code (i.e., in polytope == 0.2.3) in module polytope.polytope can compute results that are in error, without raising an exception.