Opened 20 months ago
Last modified 8 weeks ago
#27448 needs_work enhancement
compute normal vectors of surface faces of polyhedron
Reported by:  dkrenn  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  geometry  Keywords:  
Cc:  jipilab, ghLaisRast, ghkliem  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  u/dkrenn/surfacenormal (Commits)  Commit:  8f23aa949086e9cb358a2d50b67ad85f2efb7fdd 
Dependencies:  Stopgaps: 
Description
Change History (33)
comment:1 Changed 20 months ago by
 Branch set to u/dkrenn/surfacenormal
comment:2 Changed 20 months ago by
 Commit set to 297ff0033b0e6a568e50d9466ac4fccc2cd60805
 Status changed from new to needs_review
comment:3 Changed 20 months ago by
 Commit changed from 297ff0033b0e6a568e50d9466ac4fccc2cd60805 to d0b6b79ae32affd6124af88e4a37ad0047f84713
Branch pushed to git repo; I updated commit sha1. New commits:
d0b6b79  Trac #27448: simplify methods and restrict to one algorithm for all

comment:4 followup: ↓ 6 Changed 20 months ago by
Invalid Python 3 syntax found: invalid syntax (face.py, line 587)
comment:5 Changed 20 months ago by
 Commit changed from d0b6b79ae32affd6124af88e4a37ad0047f84713 to acb48f667435c8e76cc82383da878b4f1ebfca3a
Branch pushed to git repo; I updated commit sha1. New commits:
acb48f6  Trac #27448: Py3 exception

comment:6 in reply to: ↑ 4 Changed 20 months ago by
Replying to chapoton:
Invalid Python 3 syntax found: invalid syntax (face.py, line 587)
Indeed, missed this one. Thanks, is now corrected.
comment:7 followup: ↓ 14 Changed 20 months ago by
please add one example with vertices in AA
comment:8 followup: ↓ 15 Changed 20 months ago by
Why is it cached!?
comment:9 followup: ↓ 16 Changed 20 months ago by
 Status changed from needs_review to needs_info
What is that intended for?
if T.base_ring() in (AA, QQbar): def exactify(c): c.exactify() try: return QQ(c) except (ValueError, TypeError): return c T = T.apply_map(lambda c: exactify(c))
If it is of any use, it should be carefully explained in the code.
comment:10 followup: ↓ 17 Changed 20 months ago by
Isn't it a big waste to compute the matrix T
each time you ask for a normal vector. Wouldn't it make more sense to compute it once and for all?
comment:11 followup: ↓ 18 Changed 20 months ago by
Documentation must include examples with unbounded faces. Especially the degenerate case where the polyhedron is a vector space.
comment:12 Changed 19 months ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:13 Changed 19 months ago by
 Commit changed from acb48f667435c8e76cc82383da878b4f1ebfca3a to 8f23aa949086e9cb358a2d50b67ad85f2efb7fdd
Branch pushed to git repo; I updated commit sha1. New commits:
4b7a774  Trac #27448: cache matrix

53e3b14  Trac #27448: refactor imports

82e7613  Trac #27448: more careful use of exactify

0c359ce  Trac #27448: move more code around (fixup caching)

919bebf  Trac #27448: explain purpose of exactifycode

769ba63  Trac #27448 doctest for unbounded polyhedron

8f23aa9  Trac #27448: doctest for polyhedron with vertices in AA

comment:14 in reply to: ↑ 7 Changed 19 months ago by
comment:15 in reply to: ↑ 8 Changed 19 months ago by
Replying to vdelecroix:
Why is it cached!?
Because for my computation (related to #27447) it reduced the computation time by a factor 7 or 8.
comment:16 in reply to: ↑ 9 Changed 19 months ago by
Replying to vdelecroix:
Code commented inWhat is that intended for?
if T.base_ring() in (AA, QQbar): def exactify(c): c.exactify() try: return QQ(c) except (ValueError, TypeError): return c T = T.apply_map(lambda c: exactify(c))If it is of any use, it should be carefully explained in the code.
919bebf  Trac #27448: explain purpose of exactifycode

comment:17 in reply to: ↑ 10 Changed 19 months ago by
Replying to vdelecroix:
Indeed. Done inIsn't it a big waste to compute the matrix
T
each time you ask for a normal vector. Wouldn't it make more sense to compute it once and for all?
4b7a774  Trac #27448: cache matrix

but also see the other commits (some more changes were done).
comment:18 in reply to: ↑ 11 Changed 19 months ago by
Replying to vdelecroix:
Done inDocumentation must include examples with unbounded faces. Especially the degenerate case where the polyhedron is a vector space.
769ba63  Trac #27448 doctest for unbounded polyhedron

comment:19 Changed 19 months ago by
 Status changed from needs_info to needs_review
comment:20 Changed 19 months ago by
All comments are incorporated, so please review again.
comment:21 Changed 19 months ago by
I don't understand something. According to the comment When the polyhedron is rational, ... We correct this below.
the following should not fail
c.exactify() try: return QQ(c)
comment:22 Changed 19 months ago by
There is no example of polyhedra defined over a number field such as QuadraticField(2)
or NumberField(x^3  2, 'a', embedding=AA(2)^(1/3))
.
comment:23 Changed 19 months ago by
If the matrix T
is supposed to belong to the ground field, isn't there a more direct way to compute it wihtout going through A
that might involve a lot of different square roots?
comment:24 Changed 18 months ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
comment:25 Changed 16 months ago by
 Milestone changed from sage8.8 to sage8.9
Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).
comment:26 Changed 12 months ago by
Please have a look at the related #17215.
Also, it seems that in the doctests, the older version of the repr
for faces is used... This should be updated.
comment:27 Changed 10 months ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:28 followup: ↓ 30 Changed 9 months ago by
With #17215, one can do:
sage: s = polytopes.simplex(2) sage: for facet in s.facets(): ....: print("{} has normal vector {}".format(facet,facet.normal_cone().rays()[0].vector())) ....: A 1dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices has normal vector (1, 1, 0) A 1dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices has normal vector (0, 1, 0) A 1dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices has normal vector (1, 0, 0)
sage: P = Polyhedron(vertices=[(0,0), (1,0), (sqrt(AA(2)),2), (1,1)],base_ring=AA) sage: for facet in P.facets(): ....: print("{} has normal vector {}".format(facet,facet.normal_cone().rays()[0].vector())) ....: A 1dimensional face of a Polyhedron in AA^2 defined as the convex hull of 2 vertices has normal vector (0, 1/2) A 1dimensional face of a Polyhedron in AA^2 defined as the convex hull of 2 vertices has normal vector (1, 0.7071067811865475?) A 1dimensional face of a Polyhedron in AA^2 defined as the convex hull of 2 vertices has normal vector (1, 0.2071067811865476?)
sage: P = Polyhedron(ieqs=[(0, 1, 1, 1, 1)]) sage: for facet in P.facets(): ....: print("{} has normal vector {}".format(facet,facet.normal_cone().rays()[0].vector())) ....: A 3dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 1 vertex and 3 lines has normal vector (1, 1, 1, 1) sage: for facet in P.facets(): ....: print("{} has normal vector {}".format(facet,facet.normal_cone('inner').rays()[0].vector())) ....: A 3dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 1 vertex and 3 lines has normal vector (1, 1, 1, 1)
sage: P = Polyhedron(ieqs=[(0, 0, 1), (0, 1, 0), (1, 0, 1)]) sage: for facet in P.facets(): ....: print("{} has normal vector {}".format(facet,facet.normal_cone().rays()[0].vector())) ....: A 1dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray has normal vector (0, 1) A 1dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 2 vertices has normal vector (1, 0) A 1dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray has normal vector (0, 1)
I don't know if this fulfills what is intended in this ticket? Does it? If it does, I believe that it would be appropriate to minimize the duplication of code. In particular, it seems that the present function is intended for facets only (smaller dimensional faces also have normal vectors, but not anymore just in 1 direction...) so the name normal_vector
is a choice which may be nasty for the user.
As for speed, well, it is true that we create a polyhedron in normal_cone
, though, the code in #17215 is essentially all obtained through already computed data. I guess this should be benchmarked.
comment:29 Changed 9 months ago by
 Cc jipilab ghLaisRast ghkliem added
comment:30 in reply to: ↑ 28 ; followup: ↓ 31 Changed 8 months ago by
Replying to jipilab:
With #17215, one can do: [...]> I don't know if this fulfills what is intended in this ticket? Does it? If it does, I believe that it would be appropriate to minimize the duplication of code.
This might be the case. Can we make the doctests here on this ticket work with the code of #17215 (or giving at least somehow a similar output)?
In particular, it seems that the present function is intended for facets only
Yes, true.
(smaller dimensional faces also have normal vectors, but not anymore just in 1 direction...) so the name
normal_vector
is a choice which may be nasty for the user.
It seems that the new code is more general indeed.
comment:31 in reply to: ↑ 30 Changed 8 months ago by
Replying to dkrenn:
Replying to jipilab:
With #17215, one can do: [...]> I don't know if this fulfills what is intended in this ticket? Does it? If it does, I believe that it would be appropriate to minimize the duplication of code.
This might be the case. Can we make the doctests here on this ticket work with the code of #17215 (or giving at least somehow a similar output)?
Yes, that's definitely possible I would say.
In particular, it seems that the present function is intended for facets only
Yes, true.
(smaller dimensional faces also have normal vectors, but not anymore just in 1 direction...) so the name
normal_vector
is a choice which may be nasty for the user.It seems that the new code is more general indeed.
Then, I believe it make sense to have a method for facets that return the appropriate normal vector.
comment:32 Changed 6 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:33 Changed 8 weeks ago by
Has this been implemented in #17215?
New commits:
Trac #27448: compute normal vectors of face