摘要
我们引入扫视法的思想,在某种程度上降低了线段求交问题的复杂度.其基本思想是:设想有一纵坐标轴(y)自左向右扫过所有线段,当y处于某一位置时,所有与y接触线段可按此时y值的大小建立一全序关系,若当y轴移近某两相交线段的交点时,这两线段在全序关系中一定相邻.因此只需检查全序关系中相邻两线段是否相交即可.我们可假定线段的左端点为靠近交点的已知点,扫视线在任一状态所接触线段的全序关系可按这些线段的左端点y值的大小来建立.应该注意到:当某线段与其他线段有两交点时,相交线段的左端点就不是最靠近第二个交点的已知点了,而是第一个交点,因此当出现相交后需要重新调整全序集的位置关系.
出处
《微计算机应用》
2001年第3期166-166,共1页
Microcomputer Applications
