MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » ,这个有关问题如何解决

,这个有关问题如何解决

www.MyException.Cn  网友分享于:2013-02-26  浏览:3次
各位高手,这个问题怎么解决?

条件:在区域S1,S2......Sn 上
  分散着点A1(x1,y1),A2(x2,y2),A3(x3,y3).....An(xn,yn)

目的:将在同一区域Si上的点Ai(xi,yi)....合并为同一点,合并后同一区域的点的坐标 可以
  以这一区域任意一点的坐标代替

例如,图中A1(x1,y1),A2(x2,y2)在同一区域内,将点A1,A2合并,
即(x1=x2,y1=y2)

求一算法

由于点数很多(有十几万个点),合并的效率越高,越好!

------解决方案--------------------
有个想法是,按照x坐标建立若干个桶,然后把每个点按照x坐标扔进相应的桶,然后按照y坐标建立若干个桶,将刚才x坐标的那些桶里的坐标拿出来扔进y桶里,扔的过程就可以知道哪些点是一个区域的了

------解决方案--------------------
楼上正解,不过如果区域可以是不规则的就不能这样了。

反正就是根据区域建桶,把点扔进对应的桶了。输出每个非NULL桶的第一个元素即可。

算法时间复杂度O(nm),n为区域个数,m为点个数。如果区域是规则的,可以按楼上优化
------解决方案--------------------
1).如果区域是等分的矩形,实现可以比较简单。假设在x方向上有Nx个区域,y方向上有Ny个区域。
定义结构体
struct s { bool bhave[Nx*Ny]; int x1, x2, y1, y2; float idlex, idley; };
初始化 bhave 全部为 false
初始化 (x1,x2)为x方向起始终止值,(y1,y2)为y方向起始终止值
初始化 idlex为(x2-x1)/Nx,idley为(y2-y1)/Ny
上述操作时间复杂度为O(1) (Nx*Ny为常量)

从头到尾遍历A1(x1,y1)~An(xn,yn)。对于任意Ai,执行:
(A.xi-s.x1)*idlex得出x索引;
(A.yi-s.y1)*idley得出y索引。
设置 s.bhave[x + Nx*y] = true;
上述操作时间复杂度为O(n)

遍历检测s.bhave[Nx*Ny],若s.bhave[i]为true,则获得一个A点坐标。
时间复杂度为O(1)(因为Nx*Ny为常量)

2).如果区域不是等分,或者是复杂的图形,则在判定Ai时,需要做定位处理。比如对于大小不等的矩形,可以采用二分搜索达到lg(n)复杂度。最好的定位方式和Si的分割有关系了。

实现可以比较简单。假设在x方向上有Nx个区域,y方向上有Ny个区域。
------解决方案--------------------
用空间换时间的做法:可以将所有的点以及区域的边界值(做一个标记区分是边界还是点)按x和y轴方向分别排序,复杂度为O((n+m)log(n+m));然后沿x轴扫描所有按x方向排好序的点,扫描过程更新相应区域的x方向边界值,并判断每个点是否位于该区域的x边界范围,如果是,对该点做一个标记=区域号,这一过程复杂度为n+m;同样对y方向也作类似处理, 这一过程复杂度也为n+m。 最后一遍判断所有点,如果该点标记的x方向和y方向都是同一个区域,那么它们是重复点,在同一个等价类中, 这一过程复杂度也为n。 所以总的复杂度为O((n+m)log(n+m))。

文章评论

写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员必看的十大电影
程序员必看的十大电影
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
如何成为一名黑客
如何成为一名黑客
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
鲜为人知的编程真相
鲜为人知的编程真相
一个程序员的时间管理
一个程序员的时间管理
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
Java程序员必看电影
Java程序员必看电影
那些争议最大的编程观点
那些争议最大的编程观点
编程语言是女人
编程语言是女人
程序员都该阅读的书
程序员都该阅读的书
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
老程序员的下场
老程序员的下场
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
10个调试和排错的小建议
10个调试和排错的小建议
漫画:程序员的工作
漫画:程序员的工作
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员的鄙视链
程序员的鄙视链
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
中美印日四国程序员比较
中美印日四国程序员比较
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
旅行,写作,编程
旅行,写作,编程
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
每天工作4小时的程序员
每天工作4小时的程序员
代码女神横空出世
代码女神横空出世
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有