Xref: utzoo comp.graphics:9911 sci.math:9808
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!ucsfcgl!cca.ucsf.edu!root
From: root@cca.ucsf.edu (Systems Staff)
Newsgroups: comp.graphics,sci.math
Subject: Re: Wanted: line-crossing-volume algorithm
Summary: Isn't this straightforward LP?
Keywords: geometry, FEM, algorithm
Message-ID: <2756@ucsfcca.ucsf.edu>
Date: 13 Feb 90 02:53:04 GMT
References: <1393@tnoibbc.UUCP>
Organization: Computer Center, UCSF
Lines: 39

In article <1393@tnoibbc.UUCP>, pvdl@tnoibbc.UUCP (Peter van de Leur) writes:
> 
> I am looking for a solution to the following problem:
> 
> I have a volume bounded by 6 planes that are not parallel nor perpendicular to 
> one another (this element probably has a name, but I am not aware of it) . 

I take it you intend this to be a distorted cube? You would need to
constrain the planes additionally to ensure this. The conditions
given could lead to a skewed hexagonal cylinder which would be unbounded.

In any case, the volume is defined by a set of linear inequalities
which say  which side of each plane the volume lies on.

> I have also got a straight line running in an arbitrary direction.

And this part is defined by linear equations.

> I need to know :
>   1. whether the line crosses the volume
>   2. If it crosses, what is the length of the cross-section.

Linear equations and linear inequalities?

Looks like a small linear programming problem from here. Is there
something I'm missing?


 Thos Sumner       Internet: thos@cca.ucsf.edu
 (The I.G.)        UUCP: ...ucbvax!ucsfcgl!cca.ucsf!thos
                   BITNET:  thos@ucsfcca

 U.S. Mail:  Thos Sumner, Computer Center, Rm U-76, UCSF
             San Francisco, CA 94143-0704 USA

I hear nothing in life is certain but death and taxes -- and they're
working on death.

#include <disclaimer.std>