计算几何精要：活性边表与向量运算

"活性边表-ACM之计算几何" 计算几何是计算机科学中的一个重要领域，它涉及到几何对象的算法和数据结构。在ACM（国际大学生程序设计竞赛）中，计算几何是一个常见的考点，尤其是处理点、线、多边形等几何实体的问题。活性边表是一种在计算几何中用于高效处理动态多边形剪切问题的数据结构。 活性边表主要用于解决动态线段相交问题，例如在多边形剪切或构造过程中，动态维护线段集合。这种数据结构允许快速地插入、删除线段，并能实时检测到新产生的线段交叉情况。 1. 基本数据结构： 在计算几何中，点通常被定义为一个包含x和y坐标的结构体。由于大部分ACM题目输入为整数点，但在计算过程中应考虑使用浮点数以处理精度问题。例如，可以定义一个`point_t`结构体，包含`int x`和`int y`成员。 2. 精度问题： 处理浮点数时，我们需要定义一个很小的常量`EPS`来判断两个数是否接近于零。这里使用`double const EPS = 1E-6;`，并通过宏`#define is0(x)(-EPS<(x)&&(x)<EPS)`来检查一个数是否可以视为零。选择合适的`EPS`值对算法的正确性至关重要。 3. 向量运算： 向量的加法、减法和标量乘法是基础运算。点积（内积）和叉积（外积）具有重要的几何意义。点积可以计算两向量的夹角余弦，而叉积则可以确定夹角的正负和面积。在二维空间中，叉积结果是一个实数，其绝对值代表了由两个向量构成的平行四边形的面积。 4. 向量幅角计算： 尽量避免直接计算角度，而是通过向量的象限和外积来比较幅角大小。如果需要计算角度，可以使用`atan2(y, x)`函数，它的值域为`(-π, π]`。 5. 外积的应用： 外积在计算几何中有广泛的应用，如判断三点的拐向、求三角形面积、判断点是否在线上、线段上、三角形内或凸多边形内，以及判断线段相交等。 6. 判断两线段是否相交： 线段相交的判断通常通过“排斥实验”和“跨立实验”这两个方法来实现，它们是计算几何中处理线段交点的经典算法。 7. 直线的数据结构： 直线可以用一般式`ax + by + c = 0`来表示，但在实际应用中，为了优化处理，有时会将a设为1.0，或者在a为0时将b设为1.0。对于整数输入，可以直接用整数表示直线，以减少浮点数运算带来的误差。 8. 题目实践： 学习计算几何可以通过解决实际的ACM题目来巩固，如POJ1066、POJ1654、POJ1127、POJ2318、POJ2653和POJ1410等，这些题目涵盖了线段相交、多边形面积计算和点在几何形状内的判断等问题，是初学者很好的入门练习。 活性边表在ACM计算几何中是一个核心概念，它帮助我们高效地处理动态线段集合，同时，掌握好基本的几何运算、精度处理和数据结构设计，是解决这类问题的关键。