自动搬运

查看原文

来自洛谷，原作者为

	狂犇 **

搬运于2025-08-24 22:00:51，当前版本为作者最后更新于2019-01-23 19:36:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法1 (k=1时)

对于每个面 f

计算光线投射到 f 平面上时与 f 的交的面积

对所有 f 求出的面积求和

求光线在平面 f 上投射后的图形

将光源平面的每个顶点投影

设 p0, p1, p2是 f 上不共线的三个点，w是光源上的点，d是光线的方向，则

投影点 – p0 = x (p1 – p0) + y (p2 – p0) = w + z d

由上式解三元一次方程组即可求出投影点

x, y 可作为点 w 在平面 f 上的二维坐标，由于p1 – p0和p2 – p0可能不垂直，在使用此坐标计算面积时需要考虑他们的夹角 求两个凸多边形的交的面积

利用投射的方法转换成二维，在二维空间上计算交的面积

算法2 (k>1 时 ）

对于每个面 f

计算光源和 f 的交 T，在 f 上记录T

将T作为新的光源，根据入射光线方向和 f 的法向计算出射方向，即新光源的方向

若还能够反射，则递归处理

递归完成后，对于每个面 f

计算所有记录在 f 上的交T的并的面积

对所有 f 求出的面积求和

计算反射光线

令入射向量为 d，法线向量为 n, 则出射向量为d – 2 (d · n) / (n · n) n; (其中 · 表示点积)

n可使用平面上两个不共线向量的叉积得到，上式与n的正反性无关

求凸多边形并的面积

和交的面积的计算类似，投射到二维平面计算