首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》变种

关灯直达底部

一个有趣的变种算法是只需要返回是否存在交点,而不是找出所有的焦点,这个算法在检测两个多边形是否相交时很有用,需要花费O(n log n)的时间。在平均情况下,这个算法能够快速地寻找到第一个交点。另一个变种则要处理这样的情况:输入的线段被标记为蓝色或者红色,我们只需要寻找到不同颜色线段之间的交点(Palazzi和Snoeyink,1994)。