经典计算几何模版

【计算几何模版】是为初学者准备的一个实用资源，包含了一系列基础的计算几何算法和函数，便于理解和应用。模版中的代码用C++编写，提供了丰富的数学运算和几何对象处理功能。 1. **叉乘**（Cross product）：计算三维空间中两点相对于第三个点的向量的叉积，返回的是一个标量值，可用于判断两个向量的相对方向，也可用于确定平面内的法向量。 2. **两点距离**（Distance）：计算平面上两个点之间的欧几里得距离，根据三维坐标计算点与点之间的距离，适用于三维空间的点定位问题。 3. **直线方程系数**（Line Equation）：返回直线的Ax + By + C = 0形式的系数，对于解析几何中的直线表示非常关键。 4. **线段**（Segment）：处理线段的类或结构体，可能包括起点和终点坐标，支持线段与点、线段与线段的交互判断。 5. **圆**（Circle）：定义圆类，包含圆心坐标和半径，可以进行圆与点、圆与线段、圆与圆的碰撞检测。 6. **两个圆的公共面积**（Intersection Area of Two Circles）：计算两个圆相交部分的面积，用于分析两圆的关系。 7. **矩形**（Rectangle）：定义矩形类，包括对角线上两点坐标，支持矩形与点、线段的碰撞检测以及计算矩形面积。 8. **多边形**（Polygon）：定义多边形类，存储顶点坐标，可以计算多边形的周长、判断是否为简单多边形、求多边形面积等。 9. **判断点在线段上**（Point on Segment）：检查一个点是否位于给定线段上，用于判断点的位置关系。 10. **线段相交**（Intersecting Segments）：判断两条线段是否相交，考虑端点重合的情况，这对于处理图形的交集至关重要。 11. **线段平行**（Parallel Segments）：检查两条线段是否平行，用于确定线段的方向关系。 12. **直线相交的交点**（Intersection Point of Lines）：找到两条直线的交点，用于绘制或分析两条线的交集。 13. **判断是否简单多边形**（Simple Polygon Check）：检验一个多边形是否为简单多边形，即没有自交的多边形。 14. **求多边形面积**（Polygon Area）：计算多边形的面积，可应用于几何形状的分析。 15. **判断是否在多边形上**（Point on Polygon）：确定一个点是否在多边形的边界上，用于图形的边界检测。 16. **判断是否在多边形内部**（Point Inside Polygon）：检查点是否位于多边形的内部，通常使用射线法或 winding number 方法。 17. **点阵的凸包**（Convex Hull of Point Set）：找出一组点的凸包，得到一个最小的多边形包围所有点，常用在数据结构和算法问题中。 模版中的辅助宏如Abs、Sgn、Max、Min等提供了基本的数学操作，方便在计算几何中进行数值处理。此外，还包括了角度与弧度的转换、三角函数和平方根函数，为计算几何问题提供了一整套的数学工具。 这个计算几何模版为初学者提供了一个全面的基础，使他们能够轻松地理解和实现计算几何问题的解决方案。通过学习和使用这个模版，开发者可以更好地掌握计算几何的基本概念，并将其应用到实际的编程项目中。