首页 > 其他 > 详细

算法5-5:线段交叉问题

时间:2014-06-19 12:51:51      阅读:456      评论:0      收藏:0      [点我收藏+]

问题


给定一系列线段,每条线段可以是水平或者竖直。求相交的线段


解决


算法的基本思想是先将线段以x坐标进行排序。做一条扫描线,从左往右扫描,也就是下图中的红线。


当进入一条水平的线时,记录该线段的y坐标。


bubuko.com,布布扣


当走出水平线时,从二叉查找树中删除该线段的y坐标。


bubuko.com,布布扣


当遇到竖直的线时,判断该线段范围内有无之前记录的坐标即可判断两线是否相交。

bubuko.com,布布扣

算法5-5:线段交叉问题,布布扣,bubuko.com

算法5-5:线段交叉问题

原文:http://blog.csdn.net/caipeichao2/article/details/30089629

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!