检测一个立方体和圆锥彼此相交？ [英] Detect if a cube and a cone intersect each other?
问题描述
考虑3D两种几何对象：
Consider two geometrical objects in 3D:
- 与轴通过其中心和其程度（边长）的位置对准和限定的立方体
- 不与轴线对准并且由它的顶点，其底部的中心的位置，和半角的位置在顶点限定的锥形
下面是一个小的code定义在C ++中这些对象：
Here is a small code to define these objects in C++:
// Preprocessor
#include <iostream>
#include <cmath>
#include <array>
// 3D cube from the position of its center and the side extent
class cube
{
public:
cube(const std::array<double, 3>& pos, const double ext)
: _position(pos), _extent(ext)
{;}
double center(const unsigned int idim)
{return _position[idim];}
double min(const unsigned int idim)
{return _position[idim]-_extent/2;}
double max(const unsigned int idim)
{return _position[idim]+_extent/2;}
double extent()
{return _extent;}
double volume()
{return std::pow(_extent, 3);}
protected:
std::array<double, 3> _position;
double _extent;
};
// 3d cone from the position of its vertex, the base center, and the angle
class cone
{
public:
cone(const std::array<double, 3>& vert,
const std::array<double, 3>& bas,
const double ang)
: _vertex(vert), _base(bas), _angle(ang)
{;}
double vertex(const unsigned int idim)
{return _vertex[idim];}
double base(const unsigned int idim)
{return _base[idim];}
double angle()
{return _angle;}
double height()
{return std::sqrt(std::pow(_vertex[0]-_base[0], 2)+std::pow(
_vertex[1]-_base[1], 2)+std::pow(_vertex[2]-_base[2], 2));}
double radius()
{return std::tan(_angle)*height();}
double circle()
{return 4*std::atan(1)*std::pow(radius(), 2);}
double volume()
{return circle()*height()/3;}
protected:
std::array<double, 3> _vertex;
std::array<double, 3> _base;
double _angle;
};
我想编写一个函数来检测一个多维数据集的交集和圆锥体是否为空或不：
I would like to write a function to detect whether the intersection of a cube and a cone is empty or not:
// Detect whether the intersection between a 3d cube and a 3d cone is not null
bool intersection(const cube& x, const cone& y)
{
// Function that returns false if the intersection of x and y is empty
// and true otherwise
}
这是问题的说明（图中是2D的，但我的问题是在3D）：
Here is an illustration of the problem (the illustration is in 2D, but my problem is in 3D):
如何有效地做到这一点（我在寻找一种算法，所以答案可以在C，C ++或Python）？
How to do that efficiently (I am searching for an algorithm, so the answer can be in C, C++ or Python) ?
请注意：在这里交点被定义为：存在一个非空的三维体积是在立方体和在锥体（如果立方体是锥体内，或者如果锥体是立方体内，它们相交）。
Note: Here intersection is defined as: it exists a non-null 3D volume that is in the cube and in the cone (if the cube is inside the cone, or if the cone is inside the cube, they intersect).
推荐答案
这答案是稍微比你的问题更普遍的（我认为一个盒子，而不是一个立方体为例）。适应你的情况应该是真的很简单。
For the code
This answer will be slightly more general than your problem (I consider a box instead of a cube for example). Adapting to your case should be really straightforward.
/*
Here is the cone in cone space:
+ ^
/|\ |
/*| \ | H
/ | \ |
/ \ |
+---------+ v
* = alpha (angle from edge to axis)
*/
struct Cone // In cone space (important)
{
double H;
double alpha;
};
/*
A 3d plane
v
^----------+
| |
| |
+----------> u
P
*/
struct Plane
{
double u;
double v;
Vector3D P;
};
// Now, a box.
// It is assumed that the values are coherent (that's only for this answer).
// On each plane, the coordinates are between 0 and 1 to be inside the face.
struct Box
{
Plane faces[6];
};
在线 - 锥路口
现在，让我们来计算一个段，我们的锥体之间的交叉点。请注意，我会做计算锥空间。另请注意，我把Z轴是垂直的。它改变给Y一个作为练习留给读者。线路被认为是在锥形空间。段方向不归;相反，段是方向矢量的长度的，并开始在点 P
/*
The segment is points M where PM = P + t * dir, and 0 <= t <= 1
For the cone, we have 0 <= Z <= cone.H
*/
bool intersect(Cone cone, Vector3D dir, Vector3D P)
{
// Beware, indigest formulaes !
double sqTA = tan(cone.alpha) * tan(cone.alpha);
double A = dir.X * dir.X + dir.Y * dir.Y - dir.Z * dir.Z * sqTA;
double B = 2 * P.X * dir.X +2 * P.Y * dir.Y - 2 * (cone.H - P.Z) * dir.Z * sqTA;
double C = P.X * P.X + P.Y * P.Y - (cone.H - P.Z) * (cone.H - P.Z) * sqTA;
// Now, we solve the polynom At² + Bt + C = 0
double delta = B * B - 4 * A * C;
if(delta < 0)
return false; // No intersection between the cone and the line
else if(A != 0)
{
// Check the two solutions (there might be only one, but that does not change a lot of things)
double t1 = (-B + sqrt(delta)) / (2 * A);
double z1 = P.Z + t1 * dir.Z;
bool t1_intersect = (t1 >= 0 && t1 <= 1 && z1 >= 0 && z1 <= cone.H);
double t2 = (-B - sqrt(delta)) / (2 * A);
double z2 = P.Z + t2 * dir.Z;
bool t2_intersect = (t2 >= 0 && t2 <= 1 && z2 >= 0 && z2 <= cone.H);
return t1_intersect || t2_intersect;
}
else if(B != 0)
{
double t = -C / B;
double z = P.Z + t * dir.Z;
return t >= 0 && t <= 1 && z >= 0 && z <= cone.H;
}
else return C == 0;
}
矩形 - 锥路口
现在，我们可以检查计划的一个矩形部分是否相交锥体（这将被用于检查面立方体是否相交锥）。然而在锥形空间。该计划通过的方式，这将有助于我们：2载体和一个点。所述载体不归，以简化计算。
Rect - cone intersection
Now, we can check whether a rectangular part of a plan intersect the cone (this will be used to check whether a face of the cube intersects the cone). Still in cone space. The plan is passed in a way that will help us: 2 vectors and a point. The vectors are not normalized, to simplify the computations.
/*
A point M in the plan 'rect' is defined by:
M = rect.P + a * rect.u + b * rect.v, where (a, b) are in [0;1]²
*/
bool intersect(Cone cone, Plane rect)
{
bool intersection = intersect(cone, rect.u, rect.P)
|| intersect(cone, rect.u, rect.P + rect.v)
|| intersect(cone, rect.v, rect.P)
|| intersect(cone, rect.v, rect.P + rect.u);
if(!intersection)
{
// It is possible that either the part of the plan lie
// entirely in the cone, or the inverse. We need to check.
Vector3D center = P + (u + v) / 2;
// Is the face inside the cone (<=> center is inside the cone) ?
if(center.Z >= 0 && center.Z <= cone.H)
{
double r = (H - center.Z) * tan(cone.alpha);
if(center.X * center.X + center.Y * center.Y <= r)
intersection = true;
}
// Is the cone inside the face (this one is more tricky) ?
// It can be resolved by finding whether the axis of the cone crosses the face.
// First, find the plane coefficient (descartes equation)
Vector3D n = rect.u.crossProduct(rect.v);
double d = -(rect.P.X * n.X + rect.P.Y * n.Y + rect.P.Z * n.Z);
// Now, being in the face (ie, coordinates in (u, v) are between 0 and 1)
// can be verified through scalar product
if(n.Z != 0)
{
Vector3D M(0, 0, -d/n.Z);
Vector3D MP = M - rect.P;
if(MP.scalar(rect.u) >= 0
|| MP.scalar(rect.u) <= 1
|| MP.scalar(rect.v) >= 0
|| MP.scalar(rect.v) <= 1)
intersection = true;
}
}
return intersection;
}
箱 - 锥路口
现在，最后的部分：整个多维数据集：
Box - cone intersection
Now, the final part : the whole cube:
bool intersect(Cone cone, Box box)
{
return intersect(cone, box.faces[0])
|| intersect(cone, box.faces[1])
|| intersect(cone, box.faces[2])
|| intersect(cone, box.faces[3])
|| intersect(cone, box.faces[4])
|| intersect(cone, box.faces[5]);
}
有关数学
在锥形空间尽管如此，锥方程为：
For the maths
Still in cone space, the cone equations are:
// 0 is the base, the vertex is at z = H
x² + y² = (H - z)² * tan²(alpha)
0 <= z <= H
现在，在3D的线的参数方程是：
Now, the parametric equation of a line in 3D is:
x = u + at
y = v + bt
z = w + ct
的方向向量是上线（A，B，C），点（U，V，W）的谎言。
The direction vector is (a, b, c), and the point (u, v, w) lie on the line.
现在，让我们把等式联合起来：
Now, let's put the equations together:
(u + at)² + (v + bt)² = (H - w - ct)² * tan²(alpha)
然后深化发展，并重新进行因式分解这个等式后，我们得到如下：
Then after developping and re-factorizing this equation, we get the following:
At² + Bt + C = 0
其中A，B和C示于第一交叉函数。简单地解决这个检查在z和T的边界条件。
where A, B and C are shown in the first intersection function. Simply resolve this and check the boundary conditions on z and t.
这篇关于检测一个立方体和圆锥彼此相交？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
