ACM几何学算法基础.ppt

1、确定任意两条线段是否都不相交 设有一组线段，要求判断这组线段中任意两条线段是否都不相交。 问题分析： 对于一组线段，我们可以先假设这组线段中不存在与垂直轴平行的线段，同时也没有三条线段相交于一点的情况。基于这种假设，我们可以通过一根垂直扫描线来扫描这组线段，在扫描过程中我们可以发现，一旦两条线段存在交点，则其扫描的结果会发生变化。即垂直扫描线自上而下扫描时的输 ......