Polyhedron.affine_hull() raises AssertionError

[yuan-zhou]

The method affine_hull of Polyhedron fails.

sage: P1 = Polyhedron(vertices=([[-1, 1], [0, -1], [0, 0], [-1, -1]]))
sage: P2 = Polyhedron(vertices=[[1, 1], [1, -1], [0, -1], [0, 0]])
sage: P = P1.intersection(P2)
sage: A, b = P.affine_hull(as_affine_map=True, orthonormal=True, extend=True)
AssertionError

This is because the order of the vertices of P is changed by the translation by zero vector.

sage: P.vertices()
(A vertex at (0, 0), A vertex at (0, -1))
sage: P.translation(vector([0,0])).vertices()
(A vertex at (0, -1), A vertex at (0, 0))

CC: @mkoeppe @mo271 @videlec @jplab

Component: geometry

Author: Moritz Firsching

Branch/Commit: 70114be

Reviewer: Travis Scrimshaw, Jean-Philippe Labbé

Issue created by migration from https://trac.sagemath.org/ticket/24047

[videlec]

comment:2

1. It would be bettter to sort the V and H generators so that this kind of troubles never appear (and equality test would be even faster)

2. The translation method is stupidly written

    displacement = vector(displacement)
    new_vertices = [x.vector()+displacement for x in self.vertex_generator()]
    new_rays = self.rays()
    new_lines = self.lines()
    new_ring = self.parent()._coerce_base_ring(displacement)
    return Polyhedron(vertices=new_vertices, rays=new_rays, lines=new_lines, base_ring=new_ring)

we should not recompute anything!

[mkoeppe]

comment:3

Replying to @videlec:

we should not recompute anything!

That would require #22701 - Setting up a Polyhedron from both Vrep and Hrep.

[jplab]

comment:4

@Moritz: You told me you would have a fix for this? It consists in what exactly?

[mo271]

Branch: u/moritz/24047

[mo271]

Commit: 0022adc

[mo271]

comment:6

This should fix at least the reported bug; it simply chooses the zero, instead of relying on the fact that it is the first in the list.

---

New commits:

ffd2bdd	compensate the order change of 'translation'
0022adc	added test from trac

[tscrim]

comment:7

You have some tab characters (should be 4 spaces) and your indentation level is wrong:

       Check that :trac:`24047` is fixed::
 
            sage: P1 = Polyhedron(vertices=([[-1, 1], [0, -1], [0, 0], [-1, -1]]))
            sage: P2 = Polyhedron(vertices=[[1, 1], [1, -1], [0, -1], [0, 0]])
            sage: P = P1.intersection(P2)
            sage: A, b = P.affine_hull(as_affine_map=True, orthonormal=True, extend=True)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0bee595

tabs to spaces

[sagetrac-git]

Changed commit from 0022adc to 0bee595

[mo271]

comment:10

uups, I used a different editor, which changed spaces by tabs..
Should be fixed now.

[mkoeppe]

Author: Moritz Firsching

[jplab]

comment:12

that we really Q really -> that Q really?

Otherwise, it looks good to me and the bot is happy so I would put it as positive review once the small mistake above is corrected.

Thanks for the quick fix!

[sagetrac-git]

Changed commit from 0bee595 to 70114be

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7036f1c	compensate the order change of 'translation'
d4456e3	added test from trac
e081292	tabs to spaces
70114be	typo in comment

[mo271]

comment:14

thanks for the review, JP!

[fchapoton]

comment:15

reviewer name, please

[jplab]

Reviewer: Travis Scrimshaw, Jean-Philippe Labbé

[vbraun]

Changed branch from u/moritz/24047 to 70114be