Opened 9 years ago
Closed 8 years ago
#13638 closed defect (fixed)
fix adjacency of rays
Reported by: | vbraun | Owned by: | mhampton |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | geometry | Keywords: | |
Cc: | Merged in: | sage-5.6.beta2 | |
Authors: | Volker Braun | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11763 | Stopgaps: |
Description (last modified by )
The adjacency of rays in polyhedra isn't right. This impacts some corner cases in plotting 2-d non-compact polytopes:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (2, 0), (3, 0), (4, 1)], rays=[(0,1)]).plot() --------------------------------------------------------------------------- ValueError Traceback (most recent call last) /home/vbraun/opt/sage-5.4.rc1/devel/sage-main/<ipython console> in <module>() /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in plot(self, **kwds) 516 render = render_method[self.ambient_dim()] 517 if render != None: --> 518 return render(self,**kwds) 519 raise NotImplementedError('Plotting of '+str(self.ambient_dim())+ 520 '-dimensional polyhedra not implemented') /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.pyc in render_2d(projection, **kwds) 54 """ 55 if is_Polyhedron(projection): ---> 56 projection = Projection(projection) 57 return \ 58 projection.render_points_2d(zorder=2, pointsize=10, **kwds) + \ /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.pyc in __init__(self, polyhedron, proj) 411 412 if polyhedron.ambient_dim() == 2: --> 413 self._init_from_2d(polyhedron) 414 elif polyhedron.ambient_dim() == 3: 415 self._init_from_3d(polyhedron) /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.pyc in _init_from_2d(self, polyhedron) 630 self._init_points(polyhedron) 631 self._init_lines_arrows(polyhedron) --> 632 self._init_area_2d(polyhedron) 633 634 /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.pyc in _init_area_2d(self, polyhedron) 727 assert polyhedron.ambient_dim() == 2, "Requires polyhedron in 2d" 728 vertices = [v for v in polyhedron.Vrep_generator()] --> 729 vertices = cyclic_sort_vertices_2d(vertices) 730 coords = [] 731 /home/vbraun/opt/sage-5.4.rc1/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.pyc in cyclic_sort_vertices_2d(Vlist) 188 break; 189 else: --> 190 raise ValueError 191 return result 192 ValueError:
Attachments (1)
Change History (29)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 follow-up: ↓ 4 Changed 9 years ago by
In this case there is only one ray in the V-representation. I see that its tricky, but I'm unsure how to phrase it clearer.
comment:4 in reply to: ↑ 3 Changed 9 years ago by
Replying to vbraun:
In this case there is only one ray in the V-representation. I see that its tricky, but I'm unsure how to phrase it clearer.
I'd assume that you have the usual decomposition of a polyhedron into the sum of a subspace, a pointed cone, and a polytope, right? But all the rays then come from a pointed cone, and there is no way to get TWO parallel rays then...
comment:5 follow-up: ↓ 7 Changed 9 years ago by
How about:
If the V-representation of the polygon contains only vertices and a single ray, then every V-representation object has exact two adjacent ones. The cyclic order is unique up to reversal of direction and choice of starting point.
If the V-representation of the polygon contains vertices and two rays, then the two rays are not adjacent to each other. The cyclic order then starts with one of the rays and ends with the other ray.
comment:6 Changed 9 years ago by
I've clarified the docstring in question.
comment:7 in reply to: ↑ 5 Changed 9 years ago by
Replying to vbraun:
How about:
If the V-representation of the polygon contains only vertices and a single ray, then every V-representation object has exact two adjacent ones. The cyclic order is unique up to reversal of direction and choice of starting point.
If the V-representation of the polygon contains vertices and two rays, then the two rays are not adjacent to each other. The cyclic order then starts with one of the rays and ends with the other ray.
This implies that the two extreme rays of a pointed cone in R^2
non-adjacent. Which is obviously wrong: these rays have a common vertex, which is an element of the polyhedron of dimension one less, and due to this they are adjacent, just as two facets of a polytope in R^3
would be adjacent if they had a common edge (or two edges would be adjacent if they had a common vertex).
Did you mean to say more than 1 vertex, rather than vertices?
Why does it only talk about polygons? What about bigger dimensions?
There is a typo on line 261 of geometry/polyhedron/base.py
: exact->exactly
comment:8 follow-up: ↓ 9 Changed 9 years ago by
Yes, I was thinking about more than one vertex (and thats what the doctest is doing). I've fixed the wording and the typo.
I was taking polygons as an example, since its easier to visualize. In higher dimension there is of course no cyclic ordering of adjacent vertices. Apart from that it works the same.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
Replying to vbraun:
Yes, I was thinking about more than one vertex (and thats what the doctest is doing). I've fixed the wording and the typo.
I was taking polygons as an example, since its easier to visualize. In higher dimension there is of course no cyclic ordering of adjacent vertices. Apart from that it works the same.
In fact, now I think the setup is mathematically not quite sound. Sorry for not noticing this straight away.
In my book, rays and edges are of the same dimension. One cannot normally even talk about adjacency between rays and vertices, yet you do (lines 974-9 of geometry/polyhedron/base.py
).
Although you can certainly talk about incidence between them, by inclusion, as usual.
You can have adjacency graphs between faces of the same dimension (bounded or not, does not matter). It would simplify things if one knows what exactly is behind the error message in the description.
comment:10 follow-up: ↓ 11 Changed 9 years ago by
A ray by itself does not define an edge, so you can't identify these two concepts. I claim that it does make sense to treat V-representation objects (vertices, rays, lines) on the same footing when talking about vertex-adjacencies. To span an edge you need two vertices, a vertex and a ray, or a vertex and a line.
Alternatively, you can understand this by going to projective space. Now rays are just points at infinity...
The original error message in the ticket description is a bug in my code for plotting where I didn't handle some special case with rays correctly.
comment:11 in reply to: ↑ 10 Changed 9 years ago by
Replying to vbraun:
A ray by itself does not define an edge, so you can't identify these two concepts. I claim that it does make sense to treat V-representation objects (vertices, rays, lines) on the same footing when talking about vertex-adjacencies.
It might make sense for the purpose of drawing things, perhaps. I don't mind this being implemented in a way you see fit, I'm just objecting to the names used to describe the objects, as they are hugely misleading.
By they way, it would be great to know what exactly you (and Sage :-)) mean by the V-representation. Is it always reduced? Does it always distinguish between vertices, rays, and lines? A reference?
To span an edge you need two vertices, a vertex and a ray, or a vertex and a line.
the classical definition of a face of a convex set B is that it is the intersection of a supporting hyperplane with B. And the dimension of the face is the topological dimension of the intersection. This way it certainly does not make sense to talk about adjacency beween vertices and rays, as they are objects of different type (i.e., dimension).
Alternatively, you can understand this by going to projective space. Now rays are just points at infinity...
No, you certainly do not want to squash your affine space. You want to add the hyperplane at infinity. Then the rays have two vertices, one of which at infinity. (And parallel rays intersect at infinity, which might make sense for your purposes, or not...)
Regarding lines, there are two schools, one of which just forbids full lines in convex sets in RP^n
all together.
comment:12 follow-up: ↓ 13 Changed 9 years ago by
I'm basing the nomenclature on "Representations of Convex Polyhedra" in the PPL docs http://bugseng.com/products/ppl/documentation#%2Fproducts%2Fppl%2Fdocumentation%2F%2Fdevref%2Fppl-devref-1.0-html%2Findex.html, if you want a reference. The representation is always reduced.
With regard to the projective space, I guess it would be best to compactify by adding rays as extra "points". Instead of lines, which would give you the usual real projective space. Note that you don't have to say rays/lines modulo parallel transport since the rays/lines don't have a base point in my notation.
So there is no such thing as parallel rays, only parallel edges. Two parallel half-infinite edges intersect at infinity.
The Polyhedron
class doesn't keep track of extra generators at infinity. So two half-infinite edges that are not parallel can be thought of as closed up by a edge that is at infinity, but that is not part of the data we track.
comment:13 in reply to: ↑ 12 Changed 9 years ago by
Replying to vbraun:
I'm basing the nomenclature on "Representations of Convex Polyhedra" in the PPL docs ppl, if you want a reference. The representation is always reduced.
Do I understand you right that you're "unrolling" a minimal V-representation when building up your adjacencies? E.g. if your polyhedron is a polytope plus a ray then you have to "paste" a ray into each vertex, and this gives you your parallel "half-infinite edges"?
Hmm, and what do you do if your polyhedron has no vertices at all? (E.g. it's a half-plane?)
comment:14 Changed 9 years ago by
A polyhedron has at least one vertex, except when it is empty:
sage: Polyhedron(lines=[(1,0),(0,1)]) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 lines sage: _.Vrepresentation() (A line in the direction (0, 1), A line in the direction (1, 0), A vertex at (0, 0)) sage: Polyhedron() The empty polyhedron in QQ^0 sage: _.Vrepresentation() ()
The representation of polyhedra containing whole lines is not unique.
comment:15 Changed 9 years ago by
PS: Its a non-trivial step to compute the adjacencies, I agree. All edges are constructed in that step. Right now actually the whole face lattice is computed, though that could be done faster with linear programming. In any case, we first need to get it right before we can make it fast ;-)
comment:16 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to trailing whitespaces
please remove all trailing whitespaces
comment:17 follow-up: ↓ 20 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues trailing whitespaces deleted
The only trailing whitespace policy that we have in effect is to not care about trailing whitespace. In particular, this might break my other patches on top of this one for no good reason.
comment:18 Changed 9 years ago by
When you say "we have", do you mean "I have" ?
Well, please do as you want. But I will not be happy with any ticket if the bot is not fully green.
comment:19 Changed 9 years ago by
This was discussed on sage-devel not so long ago, see https://groups.google.com/d/msg/sage-devel/dQENkqZ3uWI/q-jU2S952LsJ
comment:20 in reply to: ↑ 17 ; follow-up: ↓ 21 Changed 9 years ago by
Replying to vbraun:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (2, 0), (3, 0), (4, 1)], rays=[(0,1)]) sage: P.adjacency_matrix? ... Definition: P.adjacency_matrix(self) Docstring: This is an alias for "vertex_adjacency_matrix()" ...
this seems to indicate that only vertices can be adjacent, no? Another very confusing thing is
Two V-representation objects are adjacent if they generate a 975 (1-dimensional) face of the polyhedron. Examples are two 976 vertices of a polytope that bound an edge, or a vertex and a 977 ray of a polyhedron that generate a bounding half-line of the 978 polyhedron.
in geometry/polyhedron/base.py
.
IMHO the whole documentation for the adjacency is a mess. I am unable to make sense out of it, and the link to PPL docs (which aren't clear to me at all) is not helping much, either. Please, please, define what is meant by "ray" somewhere. I just don't get it...
comment:21 in reply to: ↑ 20 Changed 9 years ago by
Replying to dimpase:
In short, in order to be able to review this ticket, I'd like to see what are V-objects (they are vertices and rays, as far as I can see, but I don't get what is done with polyhedra containing lines), what are 1-dimensional objects, and a full list of adjacency rules, not "Examples are...". Without this I don't see what this ticket is supposed to fix.
comment:22 Changed 9 years ago by
Historically there was a vertex_adjacency_matrix
first. Though it would have been more appropriate to call it Vrepresentation_adjacency_matrix
. I agree that the docs could be better. I'll try to write a concise definition...
comment:23 Changed 8 years ago by
- Dependencies set to #11763
comment:24 Changed 8 years ago by
I've expanded the documentation for V-representation objects and for the adjacency rules. Please let me know if anything is still unclear.
In order to have clearer examples I added #11763 to the dependencies, this ticket improves output and introduces the polyhedron.faces(dim)
method which is useful if you have to talk about one-dimensional faces.
comment:25 Changed 8 years ago by
- Status changed from needs_review to positive_review
hopefully the patchbot faults is just a setup problem. At least I have it all running on my machine (macosx 10.6.8).
comment:26 Changed 8 years ago by
Thanks!
The patchbot has the wrong order of patches for #11763 for some reason, which is why it fails. I think it fails to parse the formatting in the description.
comment:27 Changed 8 years ago by
- Milestone changed from sage-5.5 to sage-5.6
- Reviewers set to Dmitrii Pasechnik
comment:28 Changed 8 years ago by
- Merged in set to sage-5.6.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
line 279 in geometry/polyhedron/base.py says:
This is bizzarre. Are you saying that if you, say, have a 3-D cube "with the lid removed", i.e. extended infinitely into direction z, say, then all the 4 rays present will be adjacent? This seems to contradict what the lines 995-999 of the same file say, too.