Opened 7 years ago

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

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: 

Attach trac_13638_ray_adjacency_fix.patch

Attachments (1)

trac_13638_ray_adjacency_fix.patch (14.9 KB) - added by vbraun 7 years ago.
Updated patch

Download all attachments as: .zip

Change History (29)

comment:1 Changed 7 years ago by vbraun

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by dimpase

line 279 in geometry/polyhedron/base.py says:

	        Note that parallel rays are adjacent to each other

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.

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

comment:4 in reply to: ↑ 3 Changed 7 years ago by dimpase

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: Changed 7 years ago by 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.

comment:6 Changed 7 years ago by vbraun

I've clarified the docstring in question.

comment:7 in reply to: ↑ 5 Changed 7 years ago by dimpase

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: Changed 7 years ago by 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.

comment:9 in reply to: ↑ 8 Changed 7 years ago by dimpase

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: Changed 7 years ago by 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. 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 7 years ago by dimpase

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: Changed 7 years ago by vbraun

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 7 years ago by dimpase

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 7 years ago by vbraun

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 7 years ago by vbraun

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 7 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues set to trailing whitespaces

please remove all trailing whitespaces

Last edited 7 years ago by chapoton (previous) (diff)

comment:17 follow-up: Changed 7 years ago by vbraun

  • 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 7 years ago by chapoton

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 7 years ago by vbraun

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: Changed 7 years ago by dimpase

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

Last edited 7 years ago by dimpase (previous) (diff)

comment:21 in reply to: ↑ 20 Changed 7 years ago by dimpase

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 7 years ago by vbraun

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 7 years ago by vbraun

  • Dependencies set to #11763

Changed 7 years ago by vbraun

Updated patch

comment:24 Changed 7 years ago by vbraun

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 7 years ago by dimpase

  • 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 7 years ago by vbraun

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 7 years ago by jdemeyer

  • Milestone changed from sage-5.5 to sage-5.6
  • Reviewers set to Dmitrii Pasechnik

comment:28 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.