intersection of two cylinders in 3D space

20 次查看（过去 30 天）
Tyler
Tyler 2014-5-10
编辑： Bruno Luong 2018-9-13
HI everyone,
does anyone know of an existing algorithm to check the intersection of two cylinders in 3D space? I believe this is done by projecting the cylinders onto a plane and checking for a "separating axis"
Any help would be greatly appreciated!
  2 个评论
Matt J
Matt J 2014-5-10
编辑：Matt J 2014-5-10
Are they infinitely long cylinders?
Tyler
Tyler 2014-5-10
sorry, to clarify - the cylinders are finite in length (therefore the edges need to be taken into account)

请先登录，再进行评论。

请先登录，再回答此问题。

回答（4 个）

Matt J
Matt J 2014-5-10
编辑：Matt J 2014-5-10
If the cylinders are of infinite length, it can be done by finding the shortest distance between the cylinder axes. Calculating the distance between two lines in 3D is explained, for example in this video
https://www.youtube.com/watch?v=HC5YikQxwZA
Once you have the distance between the central axes of the cylinders, you just check if it is less than the sum of the cylinder radii. If so, the cylinders intersect, otherwise, they do not.
  5 个评论
显示 3更早的评论
Tyler
Tyler 2014-5-11
Matt J, can you elaborate on subjecting the norm command to constraints? from what i understand the norm command finds the distance between two vectors - are you representing the cylinders as vectors?
Matt J
Matt J 2014-5-11
编辑：Matt J 2014-5-11
The cylinders are to be represented using inequality constraints. So, for example, suppose x=(u1,u2,u3), is a point in Cylinder 1 and y=(v1,v2,v3) is a point in Cylinder 2. Suppose further, for simplicity, that Cylinder 1 is centered on the u3/v3 axis, and Cylinder2 is centered on the u1/v1 axis. Then the 6-dimensional vector (u1,u2,u3,v1,v2,v3) satisfies inequalities
u1^2+u2^2<=radius1^2
LowerBound1<=u3<=UpperBound1 %containment in Cylinder 1
v2^2+v3^2<=radius2^2
LowerBound2<=v1<=UpperBound2 %containment in Cylinder 2
If you minimize the function
f(u1,u2,u3,v1,v2,v3) = norm((u1,u2,3) - (v1,v2,3))^2
subject to the inequalities, you will find the shortest separation (squared) between the cylinders, which will be zero if the cylinders intersect.
The above is a nonlinear, constrained optimization problem. It can be solved analytically using Lagrange Multipliers. Or, you can let fmincon() do it for you, but that's an iterative solver, so it might take longer and not be as exact.
To modify the constraints to handle cylinders in arbitrary positions, you must make a variable substitution x'=R*x+t in the inequalities for each cylinder, where R is an appopriate 3x3 rotation matrix and t is a translation vector.

请先登录，再进行评论。

Matt J
Matt J 2014-5-11
编辑：Matt J 2014-5-11
I believe this is done by projecting the cylinders onto a plane and checking for a "separating axis"
I didn't realize until a short while ago how this could be done, but I think I understand it now and it does make things a lot easier.
First, I'll assume that the cylinders are not parallel. It is easy to detect the intersection of parallel cylinders. It occurs when both (1) the separation of their axes is less than the sum of their radii (2) projecting the cylinders onto a common parallel axis results in overlapping line segments.
I'll also assume that the cylinders do intersect when extended to infinity. I explained in my other answer why this is easy to detect. If they don't intersect when extended to infinity, they don't intersect period.
Since the cylinders are not parallel, then their axes have direction vectors u1 and u2 with non-zero cross product
u3=cross(u1,u2)
I claim that if you project the cylinders onto the plane normal to u3, you will get rectangles which intersect if and only if the original cylinders intersect. So, the problem reduces to finding the intersection of 2 rectangles.
Finding the intersection of rectangles is very easy to do using, for example, this FEX sumbmission
http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or--in-equalities
When the cylinders are projected onto the plane, the rectangles will be given by 2 sets of inequalities
A1*x<=b1
A2*x<=b2
where A1,A2 are each 4x3 and b1,b2 are 4x1. You can then use lcon2vert in the FEX package to get the vertices of the intersection, by combining the equalities into one system
V=lcon2vert([A1;A2],[b1;b2])
If it returns V=[], then no vertices and hence no intersection, was detected.
  4 个评论
显示 2更早的评论
Berti
Berti 2015-4-10
I'm afraid this test is not 100% accurate. The problem arises if the infinite cylinder barely touch each other. In the projection to u3, the intersection would be close to the projected main axis of the cylinders. However, the two rectangles would intersect in cases where there is no actual cylinder intersection. For example, the corners of the rectangles could overlap before the projected main axis intersects.
Matt J
Matt J 2015-4-10
I think I see what you mean, Berti. Well, I think that the test can at least be used to rule out intersection of the projected rectangles don't overlap.
I conjecture that if you make two more projections - one onto the plane perpendicular to u1 and the other onto the plane perpendicular to u2 -- that you would complete the test. The cylinders do not intersect if and only the projected shapes fail to intersect on at least one of those 3 planes....?

请先登录，再进行评论。

Matt J
Matt J 2014-5-10
编辑：Matt J 2014-5-10
Another option would be to take lots of sample points (x,y,z) on the circular caps of both cylinders and try to find a separating plane between them. This is equivalent to what is done in the training of support vector machines and can be done using the svmtrain() command in the Statistics Toolbox.
It's an approximate solution of course, with error depending on how much sampling you do.
Bruno Luong
Bruno Luong 2018-9-13
编辑：Bruno Luong 2018-9-13
This FEX might provide an answer:

类别

在 Help Center 和 File Exchange 中查找有关 Multiobjective Optimization 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by