求算法或思路(二维数据处理)

这个算法问题是有关三维空间的,我先简化为二维问题以便于讨论,不知道是否适合在此提问,但我要用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。

求高手能优化此算法或给出其他思路,非常感谢

8个回答

还是沿用我原来的思路,要证明:六面体(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=广度优先搜索

兄弟,这个简单得很,判断同一平面内,一条直线 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 不同为正或者同为负。

其他遍历步骤不用我说了吧

你的算法太抽象了看不懂,没有我的算法好理解。

说错了个东西,上面六面体 被直线穿越的那个不是充分必要条件,只是必要条件。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!