Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two faces ($S_1$ and $S_2$), each bounded by a series of Vertex $V$. These two faces may or may not intersect. In addition to that there are two vertical faces $S_3$ and $S_4$, that connect between $S_1$ and $S_2$ vertically, as shown in the below diagram. The question is how to find the polyhedrons that are formed by the bounding of the four faces?

An example of this is shown below: alt text

In the above example, there should be two polyhedrons returned, one above $S_2$, another below $S_1$.

Both $S_1$ and $S_2$ are defined by 3D coordinates. Let's say the coordinates for $S_1$ is ($P_1$,$P_2$, $P_3$, $P_4$) and $S_2$ is $P_5$,$P_6$, $P_7$, $P_8$, and the intersected points are $P_9$ and $P_{10}$. I want a program that returns me two polyhedrons:

$$P_1,P_2,P_9,P_{10},P_5,P_6$$

and

$$P_3,P_4,P_{10},P_9,P_7,P_8$$

One way to do this is to find the intersecting line of the two faces, and then construct polyhedron from there. But is there a more elegant method?

share|improve this question
1  
What kind of polygons should the faces be? –  J. M. Dec 10 '10 at 8:30
    
@J.M., what do you mean by what kind of polygons? –  Graviton Dec 10 '10 at 8:31
1  
What about the polyhedron $P_1, P_2, P_9, P_{10}, P_8, P_7$? Should the program return that one as well? What if the intersection of $S_1$ and $S_2$ doesn't meet the edges of $S_2$? What if $S_1$ and $S_2$ are disjoint? (By the way - it would really help if you labelled the vertices of your figure.) –  Sam Nead Dec 10 '10 at 11:50
1  
This may be a numerically unstable problem. Imagine $S/1$ and $S/2$ such that (for one assignment of vertex matching) all three lines go through a point. If one vertex moves slightly, the configuration will change. If your vertices are rational, you can do this exactly, but if they are reals, no. –  Ross Millikan Dec 10 '10 at 14:01
1  
I see six planes in the figure, not four. –  TonyK Jun 9 '11 at 17:18

1 Answer 1

There is a large literature about how to take a drawing in the plane which tries to give a 3-dimensional view of a polyhedron and extract a polyhedron from this drawing, in contrast to applying Steinitz's Theorem which gives necessary and sufficient conditions that a graph be the vertex-edge graph of a convex 3-dimensional polyhedron:

http://en.wikipedia.org/wiki/Steinitz%27s_theorem

Here is a sample of the other kind of work:

http://linkinghub.elsevier.com/retrieve/pii/S009784930900020X

http://linkinghub.elsevier.com/retrieve/pii/S009784930900020X

http://portal.acm.org/citation.cfm?id=1052355

share|improve this answer
    
I think you misunderstand my point; I have the coordinates of the planes ( or faces) in 3D format, so it's not a case of extracting polyhedron from the drawing. All I need is an efficient algorithm to come up with the polyhedron bounded by two faces. –  Graviton Dec 11 '10 at 15:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.