 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第一节 线段的交点计算 | ||||
 两线段AB和CD交点的算法
1.〔计算行列式〕  若  ,则两线段重合或平行,可算做无交点,算法结束;2.〔计算交点参数〕  若  ,则无交点,算法结束;
若  ,则无交点,算法结束;3.〔计算交点〕  ,输出交点(x,y)后算法结束;多条线段求交
寻找这样的算法,其计算工作量要大体上与交点个数成正比,即只对有可能相交的两线段计算交点,对不可能相交的线段不计算交点,使算法有更好的效率。 我们称平面内两条线段在横坐标x处是可比较的,如果存在一条通过x的垂直线,此线与两条线段都相交。我们规定一个在x处的"上面"关系为：在x处,线段  在 的上面,记为 ,如果在x处可比较,且与垂直线的交点位于与垂直线的交点的上面。 |
||||
 |
||||
其中， |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
