**comp.graphics.algorithms**

## Subject: **Joining points to form 3D convex polygon**

Hi,

I have a problem which has come up during my attempt to solve another

problem!

I am trying to find the intersection between a 3D triangle and a convex

polyhedron. I have managed to work out a way of doing this by working

out where each edge of the triangle intersects the polyhedron and also

where each edge of the polyhedron intersects the triangle.

The problem is, what I end up with are a series of points, all of which

are either on the edges of or within the triangle (i.e. all in the same

arbitrary 3D plane) but I cannot see an easy way to determine how to

traverse these points to describe the resultant convex polygon in 3D.

I have started out by trying to work out every single scenario of

intersection and treat each one as a separate case to determine the

order of the points, however this is proving very time consuming and I

am not convinced I will cover all cases as it can be hard to visualise

the different scenarios for this problem.

Another idea occurred to me which is that if I can work out the

shortest path between all the points, this will by definition be the

path that describes the convex polygon.

My questions are:

1) Is that correct and will it always work?

2) Is there a straightforward algorithm to do this? The maximum number

of points will be 10 I think.

3) Whatever I come up with will have to be reasonably fast as I am

having to perform this intersection calculation many different times

although it is not "real-time" e.g. game or anything, it is a CAD

program.

4) Is there an easier way to achieve what I am trying here?

Thanks,

Mark.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Replies:

Re: Joining points to form 3D convex polygon

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.