vertices of a polyhedron

vertices of a polyhedron

Post by James Lova » Sat, 26 Oct 1996 04:00:00



I am looking for code or refrences to solve a problem you all have solved
many times over.
Given a matrix describing a set of lines, I want to find the vertices of the
polyhedron defined by that matrix. More to the point, I want to find all
the intersections of the lines (they do not necessarly form a polyhedron).

I have spent a day searching netlib, statlib, and the web with no sucess.

Any help directing me towards where this type of code lives would be greatly
appreciated.


Thank you
James

 
 
 

vertices of a polyhedron

Post by James Lova » Tue, 29 Oct 1996 04:00:00


In my previous post, I was unclear on the problem specification.

Quote:> >I am looking for code or refrences to solve a problem you all have solved
> >many times over.
> >Given a matrix describing a set of lines, I want to find the vertices of the
> >polyhedron defined by that matrix. More to the point, I want to find all
> >the intersections of the lines (they do not necessarly form a polyhedron).

The matrix I am thinking of is like :

1 0 -1.96
1 1  1.96
0 1  1.96
1 0  1.96
0 1  2.50

There are 5 lines described by this matrix :
x     =-1.96
x + y = 1.96
    y = 1.96
x     = 1.96
    y = 2.5

The resulting polyhedron looks like

     ----------
     |        |
     |        |
     \        |
      \       |
       \      |
        -------

I hope this was clearer.
Thank you for your help.
James

 
 
 

vertices of a polyhedron

Post by Jeff Erickso » Wed, 30 Oct 1996 04:00:00



>Given a matrix describing a set of lines, I want to find the vertices of the
>polyhedron defined by that matrix. More to the point, I want to find all
>the intersections of the lines (they do not necessarly form a polyhedron).

This is the convex hull problem in disguise.

I'm going to assume two things.  (1) The polygon you want is the one
containing the origin.  [A set of n lines defines about n^2/2 different
polygons.]  (2) None of the lines actually passes thorough the origin.
[Otherwise, just move all the lines by the same (small) amount.]  In
other words, in addition to specifying the lines, you also have to
specify one point in the interior of the polygon you want, and I'm
assuming that this point is the origin (0,0).

For each line ax+by=c, write down its "dual" point (a/c, b/c).
Construct the convex hull of these dual points AND THE ORIGIN.  (This is
a technical point to deal with the case where the ansewr is unbounded.
If the polygon you want is bounded, the origin will be in the interior
of the convex hull.)  Each edge of this dual convex hull is bounded by a
line of the form ex+fy=g, and its dual point (e/g, f/g) is a vertex of
the polygon you want.

Now all you need is a convex hull algorithm.  See the FAQ, or Joe
O'Rourke's textbook "Computational Geometry in C".  Joe's textbook also
talks about point-line duality.
--
Jeff Erickson                         Center for Geometric Computing

http://www.cs.duke.edu/~jeffe

 
 
 

1. Defining "principal curvatures" at vertices of a polyhedron

Does anyone have an idea of how one could calculate reasonable values
for the principal curvatures of a polyhedral mesh of arbitrary
connectivity at each of its vertices?

For a 2D polygon one could take the inverse radius of the circle that
goes through the vertex under consideration and its two neighbors. Is
there a 3D generalization? Any other idea? (I prefer the simplest
expressions).
--
        - Sbastien

"I think not," said Descartes; and promptly disappeared.

2. availability of the OpenGL library

3. Determining the convex polyhedron given a set of vertices

4. Help with a problem

5. Q: vertex ordering of a polyhedron

6. Animated presentation

7. polyhedron generated by the movement of a polyhedron

8. Q: Shape matching: Polyhedron in polyhedron

9. polyhedron generated by the movement of a polyhedron

10. polyhedron/polyhedron intersection

11. Clipping a Polyhedron against another Polyhedron

12. polyhedron generated by the movement of a polyhedron