Python实现：计算凸多边形宽度的旋转测径法

本文档深入探讨了如何利用Python处理计算机图形学中的计算几何问题，特别是针对凸多边形的宽的计算。"对互相平行的支撑线确定的宽"这一主题，是基于定理7.3，该定理指出在凸多边形中，宽度是由最接近的边-边对踵对所决定的。这种宽的定义是指一个顶点到与其相邻边对应的支撑线的距离，当两条支撑线通过旋转尽可能减小间距，直到一条与边重合时，这个距离即为多边形的宽度。 算法的核心是旋转测径法，其目的是寻找所有可能的点-边对踵对，并找到其中最小距离的那个，以确定多边形的宽度。这种方法的时间复杂度为O(n)，因为需要遍历多边形的所有顶点和边，n代表多边形的顶点数量。具体步骤包括： 1. 给定一个凸多边形，存储其顶点的坐标形成逆时针顺序的序列。 2. 遍历每个顶点，计算其与相邻边所对应的支撑线。 3. 将每对支撑线沿着多边形的边界方向逆时针旋转，逐步寻找支撑线间的最小距离。 4. 当两条支撑线中的一条与多边形的边重合时，停止旋转，此时的点-边对踵对即为宽度决定对。 5. 记录并返回找到的最小距离作为多边形的宽度。 文中还提到了一些资源和参考资料，包括版权声明，作者的联系方式以及推荐的计算几何相关书籍，如Philip J. Schneider和David H. Eberly的《Geometric Tools for Computer Graphics》以及Franco P. Preparata和Michael Shamos的著作。这些书籍对于深入理解计算几何理论和技术具有重要作用。 此外，作者在前言部分还强调了作品的版权和更新记录，以及对读者反馈的鼓励，表示作品可能存在不足，欢迎读者提出改进意见。整个文档结构清晰，从基础的向量和矩阵概念，到复杂图元的处理，再到三维空间下的算法，涵盖了丰富的计算几何内容，适合学习和研究计算机图形学的读者参考。