计算几何基础：多边形面积与有向面积

"依然成立！！！-（HDUACM201403版_08）计算几何基础" 这篇资料主要介绍了计算几何的基本概念，包括多边形面积的计算和线段的属性，适用于杭州电子科技大学的ACM课程。在计算几何中，多边形的面积计算是一个基础且重要的问题，特别是对于参与ACM程序设计竞赛的学员来说。 首先，多边形面积的公式是通过将多边形划分为多个三角形并累加它们的面积来得到的。对于一个简单多边形，如果其顶点按照逆时针顺序排列，可以将多边形分割为N-2个三角形，其中N是多边形的顶点数。面积公式可以表示为：A = ΣAi (i = 1…N-2)，这里的Ai代表每个三角形的面积。 传统的计算线段相交的方法可能涉及复杂的几何运算，但计算几何中更注重向量的运用。对于三角形的面积，不再依赖于边长和海伦公式，而是通过向量的叉乘来计算。两个非零向量的叉积结果是一个向量，其模长等于两个向量构成的平行四边形的面积，而叉积的符号则表示它们构成的是左手系还是右手系，从而确定三角形的面积正负。例如，三角形ABC的面积可以表示为：Area(A, B, C) = 1/2 * (↑AB) × (↑AC)，其中Xb - Xa, Yb - Ya, Xc - Xa, Yc - Ya是向量AB和AC的坐标差，而"↑"表示向上的方向。 在计算几何中，这种基于向量叉积的方法具有计算量小和精度高的优点。但要注意，这种方法得到的面积是有向面积，即具有正负之分，表示多边形所在的平面相对于坐标轴的旋转方向。 此外，对于凸多边形，可以通过将其剖分为多个三角形来计算其面积，这被称为凸多边形的三角形剖分。每个三角形的面积可以用上述叉乘方法计算，然后将所有三角形的面积相加即可得到整个多边形的有向面积。 特别提醒，线段的三个属性是计算几何的基础，掌握这些知识对于解决其他计算几何问题，如求凸包等，都至关重要。因此，学生需要熟练掌握这些基础知识，并能灵活运用到实际编程中去。