[with patch, positive review] Make triangulated_facial_incidences() work better

(reviewing myself)

This breaks sometimes for dimensions above 3 because vertex_adajcencies() will list adjacencies that are not on the current face, but still in the polygon.

I was just lucky with my earlier tests. Expect an updated patch later tonight.

Now it works in all cases, all the time. It is faster for dimensions 2 and 3.

Dimensions higher than that can take really long (like 1 second in dimension 4) to compute, but at least they work.

I would like someone familiar with polyhedrons and their triangularization to do a sanity check on the output for dimensions 4 or 5 since my level of understanding of this topic is a bit lacking.

Crap, I forgot to remove the part that disabled the cache for the timings I did. trac_4164_corrections2.patch fixes that.

First of all let me say thanks for working on this. There are some problems with these patches though:

1) They don't pass doctesting on my machine. This is because of some output order differences. Did you test the final combination of all three patches? Otherwise it might be architecture-specific but looking at your code that seems unlikely.

2) In higher dimensions, "triangulation" usually means a decomposition into simplices - so in four dimensions the elements of a triangulation of a face should be tetrahedra. It occurs to me that it would perhaps be best to write a function in the Polyhedra class that triangulates (in this sense) the polyhedra itself, and then for .triangulated_facial_incideneces() call this function on the polyhedrons generated by each face.

3) Things seem to break for bigger examples. For instance, an octohedron:

sage: p_oct = Polyhedron(vertices = [[0,1],[0,2],[1,0],[2,0],[3,1],[3,2],[1,3],[2,3]])
sage: p_oct.triangulated_facial_incidences()

[[0, [3, 4, 3]],
 [1, [2, 3, 2]],
 [2, [0, 2, 0]],
 [3, [0, 1, 0]],
 [4, [1, 6, 1]],
 [5, [6, 7, 6]],
 [6, [5, 7, 5]],
 [7, [4, 5, 4]]]

Notice that the triangulation consists of the edges.

Do you have a reference for the algorithm you are using, or are you coming up with one yourself?

Replying to mhampton:

First of all let me say thanks for working on this. There are some problems with these patches though: 1) They don't pass doctesting on my machine. This is because of some output order differences. Did you test the final combination of all three patches? Otherwise it might be architecture-specific but looking at your code that seems unlikely.

I think I should never post patches past midnight, because this is when I always forget something like this.

2) In higher dimensions, "triangulation" usually means a decomposition into simplices - so in four dimensions the elements of a triangulation of a face should be tetrahedra. It occurs to me that it would perhaps be best to write a function in the Polyhedra class that triangulates (in this sense) the polyhedra itself, and then for .triangulated_facial_incideneces() call this function on the polyhedrons generated by each face.

I can't think right now of an algorithm that will triangulate according to your description in an arbitrary dimension. I will think about it for a while though.

3) Things seem to break for bigger examples. For instance, an octohedron: {{{ sage: p_oct = Polyhedron(vertices = [[0,1],[0,2],[1,0],[2,0],[3,1],[3,2],[1,3],[2,3]]) sage: p_oct.triangulated_facial_incidences() [[0, [3, 4, 3]], [1, [2, 3, 2]], [2, [0, 2, 0]], [3, [0, 1, 0]], [4, [1, 6, 1]], [5, [6, 7, 6]], [6, [5, 7, 5]], [7, [4, 5, 4]]] }}} Notice that the triangulation consists of the edges.

This is what I expected. Since the polyhedron itself is in 2D the edges are in 1D so they correspond to the edges. I asked you this question before with a square and you told me it was normal.

If it is not supposed to do that, then facial_incidences() is broken. Take a look at it.

Do you have a reference for the algorithm you are using, or are you coming up with one yourself?

I am more or less coming up with it myself. The actual triangulation of 2D surfaces is pretty standard in computer graphics (walk the points of the polygon building a triangle strip) but it obviously does not cover the cases where surfaces are in 4D. That's where I innovate (or just do something random it seems).

I'm sorry, I don't know what I was thinking - about my point (3). I guess I was thrown off by the edge having three coordinates. I retested this on a pyramid with an octahedral base (what I really had in mind) and it was fine. But on a 2D polytope, the "triangulation" of the faces would just be the edges.

I will post a patch soon so you can take a look if you want at what I've been doing. It might be useful for testing at least.

New patch, and new method. This time it should work in all cases and behave like one would expect.

This does not include a render_solid() method because it is late and I don't want to work on it right now (plus the fact that I am not quite certain about what it should do for polyhedra of dimension > 3)

To try (or merge) only apply trac_4164_tfi.patch

This passed all tests, and seems to work well for 3D polytopes, which was the original request. It does fail for some 4D polytopes, for example for one with vertices: {{{[[99, 19, 38, 0],

[-85, -86, -72, 0], [11, 31, 97, 0], [61, 99, 28, 0], [-50, -85, -90, 0], [-29, -56, 96, 0], [-48, 56, -83, 0], [97, -42, 60, 0], [-77, 73, 28, 0], [41, -92, 27, 0], [-34, 82, -58, 0], [-81, 37, -93, 0], [-96, 6, 11, 0], [-93, 66, 88, 0], [-35, -84, 77, 0], [82, 83, -66, 0], [-68, -72, -99, 0], [89, -96, -97, 0], [84, -92, -46, 0], [88, 67, -18, 0], [28, 93, 73, 0], [-97, -14, -84, 0], [97, 15, -61, 0], [39, 92, -36, 0], [-40, 99, 41, 0], [-39, 56, 99, 0], [-96, -85, -35, 0], [-48, -18, 99, 0], [91, 69, -95, 0], [-73, 60, -36, 0], [-65, -99, -32, 0], [100, 4, 65, 0], [32, 17, 94, 0], [-86, -93, 34, 0], [83, 48, -100, 0], [75, -75, 100, 0], [0, 0, 0, 1]]

}}} I am happy to work on that if you (Arnaud) want; I didn't figure out why it fails on that example.

First, sorry for the delay, I got swamped with other work to do.

The failure is due to me (cluelessly) assuming that every vertex is only connected to dim()-1 other vertices. So basically almost all the other test cases worked by luck.

I think there should be a quick and easy method for 3d polygons to have fast rendering.

But I'm still working on the general method and discovering that your example breaks almost all assumptions I had left. It should work for real after that.

Final version (apply only this)

I now consider the general case to be impossible. I don't have a formal proof for that though, only experience. I had almost fixed all of the problems with your 4D example and just to test, tried it with a 5D example. This broke a lot of things. I kind of realized that even if I managed to fix the 5D case, there would be still more problems in nD (for any n > 5).

So I restricted the input to polyhedrons of three dimensions or less which works fine and is sensible. It also fits better with the original function definition which was to produce only triangles.

Any attempt to make a more general version of this should go in a separate ticket/patch and have a different function name.

Only patch needed; merges A.B. and M.H. improvements

OK, I've combined your code in 3D with my improvements for higher dimensions. I've also added you (Arnaud) as an author. I've also based this against 3.1.2, with some improvements related to #4060. I am putting it all as one patch to make review easier. Since this is now combined work of me and Arnaud, we need to get another reviewer.

another merged contribution; no other patch is necessary

You can get 2 reviews for 1 by using the patch from #4256.

Merged in Sage 3.2 via the unified patch at #4256.

Cheers,

Michael

And since #4256 has a positive review so does this one :)

Cheers,

Michael