Henry, Here is one solution to your problem, but this approach doesn't require right regular cylindrical polyhedra. Permitting more general strut shapes allows for a simple algorithm. It scales well to large graphs as it is based on many small convex hull operations in local neighborhoods: George Hart, "An Algorithm for Constructing 3D Struts," Journal of Computer Science and Technology, 24:1, 2009, pp. 56-64. http://jcst.ict.ac.cn:8080/jcst/EN/Y2009/V24/I1%20%20%20%20%20%20%20%20%20/5... http://www.georgehart.com/rp/Algorithmfor%20Constructing3DStruts.pdf George http://georgehart.com/ On 6/4/2013 8:53 AM, Henry Baker wrote:
I've been hacking some code for building 'networks' in 3D out of 'nodes' and 'links'.
Here's the problem.
I have a very large undirected graph -- e.g., O(10^6) vertices/faces/edges -- that I want to embed in 3D.
I make an assignment of vertices to 3D points, and would then like to 'link' these points together with 'links'/'struts' which are right regular cylindrical polyhedra.
Thus, given points P1=[x1,y1,z1], P2=[x2,y2,z2], I want to 'link' P1 to P2 with a 'strut' whose cross section is a regular n-gon (e.g., equilateral triangle) of some fixed size (e.g., side length = 10 millimeters).
For the moment, I will completely ignore the problem of choosing the 3D locations of the vertices so that the struts do not interfere/intersect -- except where two (or more) struts meet at a vertex node. (This will be easy if I construct the graph embedding in the first place with no such interferences/intersections.)
We thus assume that we have a 'good' embedding of vertices/nodes in 3D such that the struts don't interfere/intersect except at the vertices/nodes themselves.
Note that when we have a 'strut' from P1 to P2, the line down the exact center of this strut goes exactly from P1 to P2.
However, the angles/faces where two such struts meet can be quite complex.
Thus, the only degree of freedom for the strut from P1 to P2 is the _rotation angle_ of the strut around the line from P1 to P2 as the axis of rotation.
I'd like to minimize the complexity (in terms of the number of faces/facets) of the overall structure, which means minimizing the number of faces where the struts come together at the vertices.
Consider one of the simplest examples: a complete graph of 3 vertices joined by 3 edges/links, which I embed in 3D as an equilateral triangle.
I want the links to have cross-sections which are regular n-gons -- e.g., triangles.
I could choose to have the 'flat' part of all three struts on the _outside_ of the big triangle linking the 3 nodes. Each pair of struts would meet at a 60 degree angle and generate no additional faces.
Or I could choose to have the 'edge' part of all three struts on the _ outside_ of the big triangle linking the 3 nodes. Each pair of struts would still meet at a 60 degree angle and generate no additional faces.
But I could choose _any angle_ for one strut around its long axis, and -- so long as I choose the _same angle_ for the other two struts -- I can still arrange for the struts to meet at the vertices/nodes with no additional faces.
I.e., the complete graph of 3 vertices and 3 edges has only 1 degree of freedom.
Q: what happens if the location assignment of the graph to 3D is no longer equilateral? Am I now forced to have additional faces?
A: No, we can still have simple joins. Proof: look at the 3 planes which are the angle bisectors of the embedded triangle. When 2 struts meet at such an angle bisector plane, they intersect the angle bisector plane at the same triangle if their rotation angle about their long axis is the same. Thus, _any_ embedded triangle still has exactly 1 degree of freedom: if we choose the rotation angle of any 1 of the 3 struts, the rotation angles of the other two struts are constrained to be the same.
Q: what happens with more complex objects -- e.g., what happens if I start with a _planar_ graph & use a location assignment that preserves its planarity. What exactly do the nodes look like where the struts come together at random angles?
Q: what happens with non-planar embeddings -- e.g., a graph that looks like a regular (or perhaps non-regular) tetrahedron?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun