Opened 3 years ago

Last modified 2 months ago

#27448 needs_work enhancement

Compute normal vector of facet of polyhedron

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-9.5
Component: geometry Keywords:
Cc: jipilab, gh-LaisRast, gh-kliem Merged in:
Authors: Daniel Krenn Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues: Implement a normal_vector for facets
Branch: u/dkrenn/surface-normal (Commits, GitHub, GitLab) Commit: 8f23aa949086e9cb358a2d50b67ad85f2efb7fdd
Dependencies: Stopgaps:

Status badges

Description (last modified by jipilab)

This ticket implements a "normal_vector" for facets.

Change History (37)

comment:1 Changed 3 years ago by dkrenn

  • Branch set to u/dkrenn/surface-normal

comment:2 Changed 3 years ago by dkrenn

  • Commit set to 297ff0033b0e6a568e50d9466ac4fccc2cd60805
  • Status changed from new to needs_review

New commits:

297ff00Trac #27448: compute normal vectors of face

comment:3 Changed 3 years ago by git

  • Commit changed from 297ff0033b0e6a568e50d9466ac4fccc2cd60805 to d0b6b79ae32affd6124af88e4a37ad0047f84713

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

d0b6b79Trac #27448: simplify methods and restrict to one algorithm for all

comment:4 follow-up: Changed 3 years ago by chapoton

    Invalid Python 3 syntax found:
    invalid syntax (face.py, line 587)

comment:5 Changed 3 years ago by git

  • Commit changed from d0b6b79ae32affd6124af88e4a37ad0047f84713 to acb48f667435c8e76cc82383da878b4f1ebfca3a

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

acb48f6Trac #27448: Py3 exception

comment:6 in reply to: ↑ 4 Changed 3 years ago by dkrenn

Replying to chapoton:

    Invalid Python 3 syntax found:
    invalid syntax (face.py, line 587)

Indeed, missed this one. Thanks, is now corrected.

comment:7 follow-up: Changed 3 years ago by chapoton

please add one example with vertices in AA

comment:8 follow-up: Changed 3 years ago by vdelecroix

Why is it cached!?

comment:9 follow-up: Changed 3 years ago by vdelecroix

  • 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 follow-up: Changed 3 years ago by vdelecroix

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 follow-up: Changed 3 years ago by vdelecroix

Documentation must include examples with unbounded faces. Especially the degenerate case where the polyhedron is a vector space.

comment:12 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 2 years ago by git

  • Commit changed from acb48f667435c8e76cc82383da878b4f1ebfca3a to 8f23aa949086e9cb358a2d50b67ad85f2efb7fdd

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

4b7a774Trac #27448: cache matrix
53e3b14Trac #27448: refactor imports
82e7613Trac #27448: more careful use of exactify
0c359ceTrac #27448: move more code around (fixup caching)
919bebfTrac #27448: explain purpose of exactify-code
769ba63Trac #27448 doctest for unbounded polyhedron
8f23aa9Trac #27448: doctest for polyhedron with vertices in AA

comment:14 in reply to: ↑ 7 Changed 2 years ago by dkrenn

Replying to chapoton:

please add one example with vertices in AA

Done in
8f23aa9Trac #27448: doctest for polyhedron with vertices in AA

comment:15 in reply to: ↑ 8 Changed 2 years ago by dkrenn

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 2 years ago by dkrenn

Replying to vdelecroix:

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.

Code commented in
919bebfTrac #27448: explain purpose of exactify-code

comment:17 in reply to: ↑ 10 Changed 2 years ago by dkrenn

Replying to vdelecroix:

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?

Indeed. Done in
4b7a774Trac #27448: cache matrix

but also see the other commits (some more changes were done).

comment:18 in reply to: ↑ 11 Changed 2 years ago by dkrenn

Replying to vdelecroix:

Documentation must include examples with unbounded faces. Especially the degenerate case where the polyhedron is a vector space.

Done in
769ba63Trac #27448 doctest for unbounded polyhedron

comment:19 Changed 2 years ago by dkrenn

  • Status changed from needs_info to needs_review

comment:20 Changed 2 years ago by dkrenn

All comments are incorporated, so please review again.

comment:21 Changed 2 years ago by vdelecroix

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 2 years ago by vdelecroix

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 2 years ago by vdelecroix

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 2 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

comment:25 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.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 2 years ago by jipilab

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 21 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:28 follow-up: Changed 20 months ago by jipilab

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 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices has normal vector (1, 1, 0)
A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices has normal vector (0, -1, 0)
A 1-dimensional 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 1-dimensional face of a Polyhedron in AA^2 defined as the convex hull of 2 vertices has normal vector (0, -1/2)
A 1-dimensional face of a Polyhedron in AA^2 defined as the convex hull of 2 vertices has normal vector (-1, 0.7071067811865475?)
A 1-dimensional 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 3-dimensional 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 3-dimensional 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 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray has normal vector (0, -1)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 2 vertices has normal vector (-1, 0)
A 1-dimensional 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 20 months ago by gh-kliem

  • Cc jipilab gh-LaisRast gh-kliem added

comment:30 in reply to: ↑ 28 ; follow-up: Changed 20 months ago by 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)?

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 20 months ago by jipilab

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 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.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 follow-up: Changed 13 months ago by mkoeppe

Has this been implemented in #17215?

comment:34 Changed 11 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:35 in reply to: ↑ 33 Changed 8 months ago by jipilab

  • Description modified (diff)
  • Summary changed from compute normal vectors of surface faces of polyhedron to Compute normal vector of facet of polyhedron
  • Work issues set to Implement a normal_vector for facets

Replying to mkoeppe:

Has this been implemented in #17215?

I think that the resolution was that it might be nice to have a direct function giving the vector and not a "cone" object...

comment:36 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:37 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

Setting a new milestone for this ticket based on a cursory review.

Note: See TracTickets for help on using tickets.