weixin_42376927 2010-06-18 20:52
浏览 264
已采纳

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

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

  • chief_fu 2010-06-30 09:48
    关注

    还是沿用我原来的思路,要证明:六面体(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;

    沿用我前面给的同一平面内直线穿越闭合图形的判断方法,此题得解。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(7条)

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题