计算几何：点、向量与线段交点的判别

"该资源是关于计算几何的课件，主要涵盖了点、向量的定义，点积与叉积的应用，以及如何判断线段相交、点的位置关系、多边形面积计算、浮点精度处理等多个核心概念。此外，还涉及了实际问题，如容器能装多少水、点在多边形内的判断、凸包问题，以及解决具体编程竞赛题目如POJ2826和POJ1556的策略。" 计算几何是计算机科学中的一个重要分支，它利用数学几何原理来解决计算机图形学和数据处理中的问题。在这个课件中，首先介绍了基本的几何元素——点和向量。点可以用坐标表示，而向量则包含了方向和大小。点积（内积）和叉积（外积）是向量运算的两个关键工具。 1. 点积：两个向量的点积等于它们的模长乘积与它们之间夹角的余弦值的乘积。当两个向量的点积为0时，它们互相垂直。通过点积可以判断两个非零向量是否平行，因为若点积为0，意味着它们的方向不一致。 2. 叉积：叉积的结果是一个向量，其方向垂直于原向量，且模长等于两个原向量模长乘积与它们之间夹角的正弦值。叉积可以用来判断一个点是否位于某直线或线段上，以及判断线段是否相交。例如，当交叉点积为0时，表示点位于直线上；若两个线段的两个叉积符号相反，则表示线段相交。 3. 直线与点的交点：给定两条直线的参数方程，可以通过解方程组找到它们的交点。若一条直线由点p1和向量v1定义，另一条由点p2和向量v2定义，它们的交点可以通过消元法求得。 4. 多边形面积计算：计算多边形的面积通常基于三角形面积的求和。对于凸多边形，可以将其分割成多个三角形，然后累加每个三角形的面积。对于非凸多边形，可能需要采用其他方法，如将多边形划分为多个凸部分。 5. 浮点精度处理：在计算机中，浮点数的比较可能存在精度问题。为了判断两个浮点数是否相等或不等，通常会设定一个很小的误差范围（如eps），如果两数之差的绝对值小于这个范围，则认为它们相等或不等。 6. 编程竞赛题目：课件提到了POJ2826和POJ1556两个题目。POJ2826涉及到计算两个线段组成的容器能容纳的最大水量，可以通过判断线段相对位置来解决。POJ1556是一个寻找穿过墙壁的最短路径问题，可能需要用到动态规划或搜索算法。 7. 凸包问题：凸包是包含在多边形内的所有点中，最外层的边界，分为上凸壳和下凸壳。求解凸包的方法有多种，如 Graham's Scan 和 Jarvis March。 通过这个计算几何课件，学习者能够掌握基础的几何概念和高级技巧，这对于解决计算机图形学和算法设计中的实际问题至关重要。