Loading... 这篇笔记会给出一个简单的用于测试球体与立方体是否相交的算法，并给出实现代码。这个算法基于[这个回答](https://www.zhihu.com/question/24251545/answer/27184960)所给出的方法。 ## 数据输入及处理 该算法需要立方体的顶点坐标最大值与顶点坐标最小值。这里为简化代码使用二维时的情况，也就是`minx,miny,maxx,maxy`，当然也可以拓展到高维。 如果给定所有的矩形(立方体...)顶点，如hdu2436，则： ```c++ const int cnt = 4; // 顶点数量 如果是立方体应该是8 int minx=INT32_MAX, miny=INT32_MAX, maxx=INT32_MIN, maxy=INT32_MIN; // 如果保证顶点坐标均为大于0的值(位于第一象限)，则maxx,maxy可以初始化为0。 // 这里使用的常量(宏)定义于 <limits> 中 for (int i=0; i<cnt; ++i) { // 这里直接使用cin从stdio中读入 int x, y; cin >> x >> y; // min与max函数均位于 <math.h> 中 minx = min(minx, x); miny = min(miny, y); maxx = max(maxx, x); maxy = max(maxy, y); // 如果是更高维度则可以增加其它分量 // 如 minz ... maxz ... } ``` 而对于球体我们需要它的圆心坐标以及它的半径(这俩玩意可以定义一个球体)。同样简化为二维：我们有`x,y,r`。 ## 算法流程 参照最开始提到的回答，设$c$为矩形中心，$h$为矩形半长（这是一个向量，见下图），$p$为圆心，$r$为半径。  ### 计算$c$与$h$ 这个很简单。设矩形最小点为$min = (minx, miny,...)$，最大点为$max=(maxx,maxy,...)$。就有$c=\frac{(min+max)}{2}$，$h=max-c$。 ### 将从立方体中心指向圆心的向量转移到第一象限 我们将这个步骤得到的向量设为$v$。  如上图，在正常求向量时对每个分量都取绝对值，这个转移不会对相交测试的结果产生影响。 ### 求圆心到矩形的最短距离向量 在矩形上建立一个坐标系(以最大的顶点为原点，如下图)，这样计算最短距离向量$u = v - h$，当$u$各个分量均为正值时，$u$确实是最短距离。但是当某个分量为负值时，$u$并不是最短距离，如下图：  出现负值，说明可以通过做垂线得到一个更短的路径(向量)，因为矩形位于第三象限中。所以直接将负值的分量置$0$即可。 如果采用建立坐标系的方式，代码量会相对较大。我们可以变换回原坐标系运算（下面的$max$为求输入参数中最大值的函数，并非上面定义的向量，$min$同理）：  其中*矩形最小x坐标*为$minx$，其他同理。 ### 比较面积(套距离公式) 这里我们只需要比较$u^2$与$r^2$比较即可，如果$u^2\le r^2$代表它们相交。这里之所以不用开方，是因为$|u| \ge 0$且$|r| \ge 0$，所以上面的不等式也成立。 如果是一个定向矩形(OBB)，也可以将圆心旋转到矩形的坐标系来求解。 ## 代码 ```c++ // 这里简化了部分代码 struct Box { double minX, minY, minZ, maxX, maxY, minZ; }; struct Sphere { double x, y, z, r; }; bool measure(Box& box, Sphere& sphere) { double x = max(box.minX, min(sphere.x, box.maxX)); [...y,z...] double ds = (x - sphere.x) * (x - sphere.x) + (y - sphere.y) * (y - sphere.y) + [...]; return ds < sphere.r * sphere.r; } ``` 最后修改：2021 年 08 月 24 日 11 : 04 PM © 允许规范转载 赞赏 请我喝杯咖啡 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
