给定三维世界中一个垂直于a、B和C的三角形，以及一个长*宽*高=nd*md*ld（n，m，l为整数，d为浮点）的轴对齐边界长方体，将该长方体划分为n*m*l立方体，如何找到该三角形通过的立方体？
有很多算法可以检测三角形和立方体是否相交。遍历所有多维数据集，问题就可以解决了。然而，这种方法的复杂性是O（n*m*l）或O（n^3）。有没有一种复杂度为O（n^2）甚至O（nlogn）的方法？
由于以下原因，您无法改进O（n m l）：选择m=1和l=1。然后有一个由n个立方体组成的平面排列，你的三角形可以与每个立方体相交。如果需要报告每个相交的多维数据集，则必须报告所有n个多维数据集。
但很明显，这只是你问题陈述中的一个缺陷。你应该问的是n=m=l的情况。现在你有一个n x n x n的立方体集合，一个三角形只能与其中的O（n^2）相交。
在这种情况下，当然一个三角形可能会与Ω（n^2）个多维数据集，因此不能改进了二次复杂度。这排除了O（n log n）。
因此，问题变成了：是否有一种亚字节算法来识别与三角形相交的O（n^2）个立方体？（一个可以代替"三角形"带有"平面"）
我相信答案是是。一种方法是构造八叉树表示立方体。搜索"体素"one_answers"八叉树交点"可能会引导您到显式算法。