这个算法问题是有关三维空间的，我先简化为二维问题以便于讨论，不知道是否适合在此提问，但我要用java实现它。请推荐更适合发此帖的论坛。
问题描述：
在二维图形空间XY(尺寸10000x10000)，分布有n(>40000)个不相互交叠的小四边形(接近但不是矩形)，纵横直径介于30-50。已知每个小四边形４个角的坐标及它的８个方向的相邻四边形ID,每个小四边形有0到8个相邻四边形。现给定任意两点(x1,y1)(x2,y2)，连成一线，求此线穿过哪些四边形。(见附图)
我现有的算法如下：
１，根据两点间距，平均分割k小段(含首尾点,共k+1个标志点,约一般250-350个)，k的取值使小段尺寸小于小四边形，保证此线穿过的小四边形至少有落上1-3个标志点
２，按顺序从此线取一个标志点
３，循环历遍所有n个小四边形，看此标志点是否落在某个小四边形内（根据标志点坐标和四边形角点空间关系判定，称方法A），如果找到，终止循环,输出此四边形的ID编号
４，取下个标志点，如果其前个标志点没有落在某个小四边形内，回到第３步
５，如果其前个标志点落在一个小四边形内，看是否当前标志点也在同个小四边形内，如果是，重复第４步，如果否，则查看此标志点是否落在前个小四边形的0-８个相邻四边形内，如果找到，输出此四边形的ID编号
６，重复第４－５步，直到此线终点
算法可以解决问题，但比较慢: 主要耗时在第３步，因为往往要循环n次方法A，历遍每个小四边形(可能无功而返,没有匹配的四边形)，而实际上n很大。k个标志点实际上只有1/3落在小四边形内(达到第５步)，另外2/3k个标志点都要经过第３步。所以大约需要调用2/3*k*n次方法A。
求高手能优化此算法或给出其他思路，非常感谢
还是沿用我原来的思路，要证明：六面体（A,B,C,D,E,F,G,H) 被直线P ax + by + cz + d = 0 穿越的充分必要条件是 直线在三个坐标平面的投影与六面体在三个坐标平面的投影都相交。点A（x0,y0,z0)在三个坐标平面的投影分别是Az（x0,y0) Ay(x0,z0) Ax(y0,z0), 直线P ax + by + cz +d = 0 在三个坐标平面的投影分别是Pz ax + by + d = 0; Py ax + cz + d = 0; Px by + cz + d = 0;
沿用我前面给的同一平面内直线穿越闭合图形的判断方法，此题得解。
以任意个四边形为point，做一个bfs，压到线上记录并输出，没压到线上标记为true访问过.复杂度=o(n)
PS:判断四边形与线段是否相交，参考计算几何判断线段与线段是否相交。即四边形1条线段与之相交，则四边形与之相交
BFS=广度优先搜索
http://leon-a.iteye.com/admin/blogs/163719
参照这个东西吧
兄弟，这个简单得很，判断同一平面内，一条直线 ax+by+c = 0 是否穿越某（凸）四边形[(A0,B0),(A1,B1),(A2,B2),(A3,B3)]的充分必要条件就是 a*A0+b*b0+c, a*A1+b*b1+c ,a*A2+b*b2+c ,a*A3+b*b3+c 不同为正或者同为负。
其他遍历步骤不用我说了吧
你的算法太抽象了看不懂，没有我的算法好理解。
说错了个东西，上面六面体 被直线穿越的那个不是充分必要条件，只是必要条件。