鑑於3D世界與頂點A，B和C的三角形，並用長*寬*高度軸對齊包圍長方體 = ND * MD * LD（通過立方體n，m，l是整數，d是float）包含它，將長方體分成n * m * l立方體以及如何找到三角形通過的立方體？如何找到通過由三角形
有許多算法來檢測三角形和立方體是否相交。遍歷所有立方體，問題可以解決。但是，這種方法的複雜性是O（n * m * 1）或O（n^3）。是否有複雜度爲O（n^2）甚至O（nlogn）的方法？
由於以下原因，您無法改進O（n m l）：select m = 1 and l = 1。 然後你有一個n個立方體的平面排列，你的三角形可以與每一個相交。如果您需要報告每個相交的立方體，則必須報告所有n個立方體。
但顯然這只是您的問題陳述中的一個缺陷。你應該問的是n = m = 1的情況。所以現在你有一個n×n×n的立方體集合，一個三角形只能與O（n^2）相交。
在這種情況下，當然一個三角形可能與Ω（n^2）個立方體相交，因此無法在二次複雜度上改進 。這排除了O（n log n）。
所以問題變成：是否有一個subcubic算法來識別O（n^2）立方體與三角形相交的 ？ （並且可以用「飛機」代替「三角形」 ）。
我相信答案是是的。一種方法是構建一個八叉樹代表 立方體。搜索「體素」和「八叉樹相交」可能會導致您顯式算法。