计算几何 计算几何

㈠ 点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 。。。。 计算几何是计算机科学中的一个重要分支，它涉及到二维和三维空间中的几何对象的数学运算和算法。这个领域在图形学、游戏开发、地理信息系统、物理模拟等多个领域都有广泛应用。以下是一些计算几何的基础知识： 1. **点的基本运算**： - **平面上两点之间距离**：使用勾股定理计算两点之间的欧氏距离。 - **判断两点是否重合**：比较两个点的坐标值，若在允许的误差范围内相等，则认为它们重合。 - **矢量叉乘**：用于判断两个向量的方向关系，叉乘结果是一个标量，其正负表示方向，零表示共线。 - **矢量点乘**：两个向量的点乘结果是一个标量，表示它们在某一轴上的投影乘积，也用于判断角度。 - **判断点是否在线段上**：通过比较点与线段端点的相对位置关系。 - **求一点饶某点旋转后的坐标**：利用旋转矩阵或向量的方法进行坐标变换。 - **求矢量夹角**：使用点乘和长度信息计算两个向量之间的夹角。 2. **线段及直线的基本运算**： - **点与线段的关系**：确定点相对于线段的位置（在线上、在线段内部、在线段外部）。 - **求点到线段所在直线垂线的垂足**：构建垂直于线段的直线并找到交点。 - **点到线段的最近点**：找出线段上距离给定点最近的点。 - **点到线段所在直线的距离**：计算点到直线的垂距。 - **点到折线集的最近距离**：遍历所有线段，找到最近的点。 - **判断圆是否在多边形内**：利用射线法检查圆心与多边形边的交点情况。 - **求矢量夹角余弦**：通过点乘和向量长度计算。 - **求线段之间的夹角**：结合矢量叉乘和点乘计算。 - **判断线段是否相交**：检查线段端点的相对顺序。 - **判断线段是否相交但不交在端点处**：排除端点相交的情况。 - **求线段所在直线的方程**：基于两点确定直线的一般式或斜截式方程。 - **求直线的斜率和倾斜角**：从方程中提取斜率，并转换为角度。 - **求点关于某直线的对称点**：构建对称变换矩阵。 3. **多边形常用算法模块**： - **判断多边形是否简单多边形**：检查是否有自交情况。 - **检查多边形顶点的凸凹性**：通过相邻边的相对方向判断。 - **判断多边形是否凸多边形**：根据凸多边形定义检查。 - **求多边形面积**：使用向量叉乘或者分割成三角形求解。 - **判断多边形顶点的排列方向**：通过向量叉乘的正负判断。 - **射线法判断点是否在多边形内**：从点出发射出一条射线，计算与边界交点的数量。 - **判断点是否在凸多边形内**：利用凸多边形性质快速判断。 - **寻找点集的 Graham 算法**：找到点集的极小锥顶点，构建凸包。 - **寻找点集凸包的卷包裹法**：从一点开始按顺时针或逆时针方向连接最近的点形成凸包。 - **判断线段是否在多边形内**：线段的端点是否都在多边形内部。 - **求简单多边形的重心**：多边形各顶点权重求平均得到中心。 - **求凸多边形的重心**：类似简单多边形，但考虑了面积权重。 - **求肯定在给定多边形内的一个点**：找到位于多边形内部的点。 - **求从多边形外一点出发到该多边形的切线**：找到与多边形边平行的切线。 4. **圆的基本运算**： - **点是否在圆内**：比较点到圆心的距离与半径的关系。 - **求不共线的三点所确定的圆**：基于托勒密定理求解圆的方程。 5. **矩形的基本运算**： - **已知矩形三点坐标，求第 4 点坐标**：通过矩形的对边平行性确定。 6. **其他算法**： - **两圆关系**：判断两圆相交、内切、外切或分离。 - **判断圆是否在矩形内**：比较圆心坐标和半径。 - **点到平面的距离**：用点到平面的法向量和点的坐标计算。 - **点是否在直线同侧**：通过点到直线的偏移量判断。 - **镜面反射线**：利用法线和入射线计算反射线。 - **矩形包含**：判断一个矩形是否完全在另一个矩形内。 - **两圆交点**：解二次方程找到交点坐标。 - **两圆公共面积**：计算两圆相交部分的面积。 - **圆和直线关系**：判断直线与圆的相离、相切、相交。 - **内切圆**：在多边形内部找到一个内切圆的算法。 - **求切点**：找出圆与线段或直线的切点位置。 - **线段的左右旋**：判断线段相对于参考线的旋转方向。 以上内容涵盖了计算几何的基本概念和常见操作，每个知识点都可以进一步扩展成复杂的算法和问题解决策略。理解并掌握这些基础，对于处理实际的计算几何问题至关重要。在编程实现时，通常会使用浮点数来近似表示坐标，因此需要考虑精度问题，例如使用EP（epsilon）作为近似相等的阈值。此外，常量定义如INF表示无穷大，方便在算法中进行边界处理。