计算几何基础：简单与凸多边形的定义与有向面积

"算法设计与分析学习提纲，第十一章 计算几何问题" 在计算几何这一领域中，主要研究的是如何利用算法解决与几何形状相关的数学问题。本章主要探讨二维平面上的点、线段和多边形的基本概念及其应用。以下是对这些概念的详细解释： 1. 点：在二维平面上，点是最基本的元素，通常用一对有序实数`(x, y)`来表示其位置。例如，点`P`可以通过坐标`(pic)`来标识。 2. 线段：线段由其两个端点定义。如果`(pic)`和`(pic)`是两个不同的点，那么线段`[pic]`表示由这两个点连接的线段。线段的长度可以通过两点之间的欧几里得距离计算得出。 3. 多边形：一个多边形是由一系列连续的线段（边）组成的闭合路径。如果`(pic)`是一个点的序列，且`(pic)`表示相邻点之间的一条线段，那么这些线段围成的区域被称为多边形`(pic)`。每个`(pic)`都是多边形的顶点，而`(pic)`是多边形的边。 4. 简单多边形与非简单多边形：简单多边形是指任何两条边都不相交（除了共享顶点的情况）。反之，如果有多条边交叉，这样的多边形就是非简单的。例如，图11.1(a)所示的是一个简单的多边形，而图11.1(b)则展示了非简单的多边形。 5. 凸多边形与非凸多边形：凸多边形的特点是，连接其任意两个顶点的线段都完全位于多边形内部。相反，非凸多边形存在至少一条这样的连线部分或全部在多边形外部。图11.2(a)显示了一个凸多边形，而图11.2(b)则是一个非凸多边形。 6. 有向面积：有向面积是衡量两个向量构成的平行四边形方向的面积。以源点`(pic)`为起点的向量`op`和`oq`的有向面积可以通过叉乘运算计算，即`op × oq = (pic)[pic]oq - (pic)oq[pic]`。这个面积可以是正、负或零，分别对应着逆时针旋转、顺时针旋转或共线的情况。图11.3展示了两个向量构成的平行四边形及其面积计算方式。 7. 左转判断：在计算几何中，判断三个点`(pic)`, `(pic)`, `(pic)`是否按逆时针顺序排列（即判断`(pic)`、`(pic)`和`(pic)`形成的三角形是面向观察者还是背对观察者）通常通过计算`(pic) × (pic)`的符号来实现。如果结果为正，则表示`(pic)`, `(pic)`, `(pic)`逆时针排列，反之则顺时针排列。 计算几何问题的解决通常涉及点、线段和多边形的碰撞检测、求解最短路径、图形遍历等。理解这些基本概念是解决更复杂问题的基础，如计算有向面积、判断点的位置关系以及构建高效的几何算法。在实际应用中，计算几何广泛应用于计算机图形学、地理信息系统、机器人路径规划等多个领域。