Opened 2 years ago
Closed 2 years ago
#29125 closed defect (fixed)
`is_inscribed` depends on order of vertices
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.1 |
Component: | geometry | Keywords: | polytopes, is inscribed |
Cc: | jipilab, gh-LaisRast | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | Jean-Philippe Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | 3f9cc75 (Commits, GitHub, GitLab) | Commit: | 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f |
Dependencies: | Stopgaps: |
Description (last modified by )
Currently the inscription test for polyhedra depends on the order of vertices:
sage: Polyhedron(vertices=[[-2,-1], [-2,1], [0,-1], [0,1]]).is_inscribed() True sage: P = Polyhedron(vertices=[[-2,-1], [-2,1], [0,-1], [0,1]], backend='field') sage: P.is_inscribed() False sage: V = P.Vrepresentation() sage: H = P.Hrepresentation() sage: parent = P.parent() sage: dic = {True: 0, False: 0} sage: for V1 in Permutations(V): ....: P1 = parent._element_constructor_( ....: [V1, [], []], [H, []], Vrep_minimal=True, Hrep_minimal=True) ....: dic[P1.is_inscribed()] += 1 ....: sage: dic {True: 18, False: 6}
The algorithm constructs a sphere around dim + 1
vertices in general position. The circumcenter is computed up to sign. Then, one vertex is taken to determine, which sign to choose. However, up to dim
vertices might lie on the intersection of both spheres.
We fix this by checking distance from the circumcenter for all vertices of that simplex.
Change History (4)
comment:1 Changed 2 years ago by
- Description modified (diff)
comment:2 Changed 2 years ago by
- Branch set to public/29125
- Commit set to 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f
- Status changed from new to needs_review
comment:3 Changed 2 years ago by
- Reviewers set to Jean-Philippe Labbé
- Status changed from needs_review to positive_review
Looks good to me. Thanks for fixing this error!
Again, the pyflakes is fixed in another ticket.
comment:4 Changed 2 years ago by
- Branch changed from public/29125 to 3f9cc75dfac02eb6b05ff49deabdfbd03b491f5f
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
check sign of circumcenter using all vertices of simplex