## vertices of a polyhedron

### vertices of a polyhedron

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

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.
James

### vertices of a polyhedron

>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
--
Jeff Erickson                         Center for Geometric Computing

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

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.