Opened 4 years ago

Closed 4 years ago

#24047 closed defect (fixed)

Polyhedron.affine_hull() raises AssertionError

Reported by: yzh Owned by:
Priority: major Milestone: sage-8.1
Component: geometry Keywords:
Cc: mkoeppe, moritz, vdelecroix, jipilab Merged in:
Authors: Moritz Firsching Reviewers: Travis Scrimshaw, Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 70114be (Commits, GitHub, GitLab) Commit: 70114bed83dee82e8d811ddb698022926fe33317
Dependencies: Stopgaps:

Status badges

Description

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))

Change History (17)

comment:1 Changed 4 years ago by mkoeppe

  • Cc moritz vdelecroix jipilab added

comment:2 follow-up: Changed 4 years ago by vdelecroix

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!

comment:3 in reply to: ↑ 2 Changed 4 years ago by mkoeppe

Replying to vdelecroix:

we should not recompute anything!

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

comment:4 Changed 4 years ago by jipilab

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

comment:5 Changed 4 years ago by moritz

  • Branch set to u/moritz/24047

comment:6 Changed 4 years ago by moritz

  • Commit set to 0022adca807b06c0eeb5786134d9531ebf005b42
  • Status changed from new to needs_review

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:

ffd2bddcompensate the order change of 'translation'
0022adcadded test from trac

comment:7 Changed 4 years ago by tscrim

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)
Last edited 4 years ago by tscrim (previous) (diff)

comment:8 Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work

comment:9 Changed 4 years ago by git

  • Commit changed from 0022adca807b06c0eeb5786134d9531ebf005b42 to 0bee595118118e9921038e59a987d99e90a4b3b1

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

0bee595tabs to spaces

comment:10 Changed 4 years ago by moritz

  • Status changed from needs_work to needs_review

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

comment:11 Changed 4 years ago by mkoeppe

  • Authors set to Moritz Firsching

comment:12 Changed 4 years ago by jipilab

  • Status changed from needs_review to needs_work

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!

comment:13 Changed 4 years ago by git

  • Commit changed from 0bee595118118e9921038e59a987d99e90a4b3b1 to 70114bed83dee82e8d811ddb698022926fe33317

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

7036f1ccompensate the order change of 'translation'
d4456e3added test from trac
e081292tabs to spaces
70114betypo in comment

comment:14 Changed 4 years ago by moritz

  • Status changed from needs_work to positive_review

thanks for the review, JP!

comment:15 Changed 4 years ago by chapoton

reviewer name, please

comment:16 Changed 4 years ago by jipilab

  • Reviewers set to Travis Scrimshaw, Jean-Philippe Labbé

comment:17 Changed 4 years ago by vbraun

  • Branch changed from u/moritz/24047 to 70114bed83dee82e8d811ddb698022926fe33317
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.