2
$\begingroup$

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?

  • 1
    What kind of polygons should the faces be?2010-12-10
  • 0
    @J.M., what do you mean by what kind of polygons?2010-12-10
  • 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.)2010-12-10
  • 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.2010-12-10
  • 1
    I see six planes in the figure, not four.2011-06-09

1 Answers 1

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

  • 0
    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.2010-12-11