Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say I have a set $C$ of $N$ cylinders in 3-space, $(c_1, ..., c_N) \in C$, where each cylinder, $c_i$, has an associated radius $r_i$ and two coordinates specifying the endpoints of the line segment representing its axis of symmetry, $(x_{i,1},y_{i,1},z_{i,1})$ & $(x_{i,2},y_{i,2},z_{i,2})$.

How can I quickly decide if the union volume of the cylinders is equal to the sum of the volumes of the individual cylinders? In other words, how can I quickly verify or disprove the existence of an intersection between any two cylinders? I'd like to stress that I mean this as a decision problem - I'm not necessarily asking for an explicit union volume calculation or a manner of finding points of intersection.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

The union itself is quite complicated, and has been the object of study in computational geometry. For example, recently, it was established by Esther Ezra that the union is nearly quadratic in size: "On the Union of Cylinders in Three Dimensions." But because you only want to decide if any pair intersects, it seems the best method is to simply check all pairs, and avoid the union. This will be a quadratic algorithm. I think it would not be easy to attain subquadratic time complexity. Of course you could pre-check to avoid the calculation if, say, their bounding boxes do not intersect. So it seems your question reduces to: How to intersect a pair of cylinders.

Since you didn't ask that, perhaps you already understand that problem? It is easy if the cylinders are infinite, for then it is merely computing the distance between their axes. More work is needed near the endcaps for finite cylinders. Certainly if the distance between their axes exceeds the sum of their radii, they do not intersect.

Fortunately, Dave Eberly of Geometric Tools has investigated this cylinder-cylinder question thoroughly, in his document "Intersection of Cylinders": PDF link.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.