# Find the Polyhedron Enclosed by Multiple Faces

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:

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?

-
What kind of polygons should the faces be? –  Ｊ. Ｍ. Dec 10 '10 at 8:30
@J.M., what do you mean by what kind of polygons? –  Graviton Dec 10 '10 at 8:31
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
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
I see six planes in the figure, not four. –  TonyK Jun 9 '11 at 17:18

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: