Re: Finding edges of a given polyhedra in 3D

klaus hoffmann wrote:
macio wrote:
Hello,

I have a problem to solve.

How can I find the edges of a polyhedra in 3D having only coordinates
of its vertices?
All the pairs of the vertices constitute corresponding line segments.
Some of them are diTetrahedronagonals and some of them are edges. I have to
distinguish them based only on the vertices data.

I searched a little and found no solution. I intended only very heavy
algorithm in 2D which consist on finding which of the line segments
intercept with each other in the area of the polyhedra (based on this I
could decide which is diagonal which is edge). This doesn't work of
course in 3D.

regards


A simple way of representing the polyhedron is as union of tetrahedra. You might take the middle of each pair of the vertices and check whether it is in the interior any tetrahedron (taking all four-tuples). This should give an (quite slow) algorithm to start with.
hth
Klaus


Are there any limitations on the polyhedron, such as that it must be convex?

If not, a tetrahedron with four of the points as vertices could enclose
space that is outside the polyhedron.

Similarly, for the 2D polygon, I don't think the original diagonal
crossing idea works for non-convex:

A------B
| |
| C--D
| |
| E--F
| |
G------H

The lines CF and DE intersect outside the area of the polygon, but
neither is an edge.

Patricia
.

Relevant Pages

  • Re: Test-Driven Development
    ... > I would expect you achieve this by reasoning about your code, ... written to generate random input tables to an algorithm. ... to a new geometry library). ... Out of the set of all such polyhedra the number that exhibit ...
    (comp.programming)
  • really simple definition
    ... Im doing some work with some surfaces. ... definition of a polygon to me, any 2D shape made with straight lines all ... polyhedra, and 3D shape made up of polygons basically. ... i thought it was a dimension -1 of the dimension of the shape ...
    (sci.math)
  • Re: Finding edges of a given polyhedra in 3D
    ... How can I find the edges of a polyhedra in 3D having only coordinates ... All the pairs of the vertices constitute corresponding line segments. ... A simple way of representing the polyhedron is as union of tetrahedra. ... This should give an algorithm to start with. ...
    (comp.theory)
  • Re: Intersecting volume of two convex polyhedra
    ... cube. ... this is not a trivial task if the algorithm is ... for your 8-vertex polyhedra. ...
    (comp.graphics.algorithms)