这个算法问题是有关三维空间的,我先简化为二维问题以便于讨论,不知道是否适合在此提问,但我要用java实现它。请推荐更适合发此帖的论坛。
问题描述:
在二维图形空间XY(尺寸10000x10000),分布有n(>40000)个不相互交叠的小四边形(接近但不是矩形),纵横直径介于30-50。已知每个小四边形4个角的坐标及它的8个方向的相邻四边形ID,每个小四边形有0到8个相邻四边形。现给定任意两点(x1,y1)(x2,y2),连成一线,求此线穿过哪些四边形。(见附图)
我现有的算法如下:
1,根据两点间距,平均分割k小段(含首尾点,共k+1个标志点,约一般250-350个),k的取值使小段尺寸小于小四边形,保证此线穿过的小四边形至少有落上1-3个标志点
2,按顺序从此线取一个标志点
3,循环历遍所有n个小四边形,看此标志点是否落在某个小四边形内(根据标志点坐标和四边形角点空间关系判定,称方法A),如果找到,终止循环,输出此四边形的ID编号
4,取下个标志点,如果其前个标志点没有落在某个小四边形内,回到第3步
5,如果其前个标志点落在一个小四边形内,看是否当前标志点也在同个小四边形内,如果是,重复第4步,如果否,则查看此标志点是否落在前个小四边形的0-8个相邻四边形内,如果找到,输出此四边形的ID编号
6,重复第4-5步,直到此线终点
算法可以解决问题,但比较慢: 主要耗时在第3步,因为往往要循环n次方法A,历遍每个小四边形(可能无功而返,没有匹配的四边形),而实际上n很大。k个标志点实际上只有1/3落在小四边形内(达到第5步),另外2/3k个标志点都要经过第3步。所以大约需要调用2/3*k*n次方法A。
求高手能优化此算法或给出其他思路,非常感谢