使用旋转测径法寻找凸多边形直径的Python实现

"该资源是一篇关于通过对踵对确定凸多边形直径的算法的实例，使用Python读取MAT文件并转换为CSV文件。文章介绍了Preparata & Shamos的算法，该算法利用旋转测径思想求解凸多边形的直径。文章还包含了作者的版权声明、版本说明、内容概要以及相关代码实现链接和推荐的计算几何书籍。" 本文详细讲解了如何运用计算几何中的方法来寻找凸多边形的直径，即凸多边形上两个最远端点之间的距离。具体来说，它引用了Preparata & Shamos在1985年提出的一种算法，该算法基于旋转测径法。算法的基本思想是遍历凸多边形的所有点对，找出那些形成对踵对的点，即一条直线穿过凸多边形内部，同时与多边形的两个顶点相邻。通过比较这些对踵对之间的距离，可以确定凸多边形的直径。 算法步骤如下： 1. 初始化指针i为n-1（n为顶点数量），j为0。 2. 在一个while循环中，计算当前点对(i, j)的向量积，即面积差，如果下一个点对的面积差更大，则更新j。 3. 更新j为下一个顶点（j = next(j)，next(i)表示i的下一个顶点）。 4. 当所有点对都被检查过或当前i超过q时，结束循环。 5. 设定q为当前j，i更新为下一个顶点。 6. 初始化直径d为-1.0。 7. 继续循环，直到j回到初始位置且i小于等于q，更新直径d。 此外，该资源提供了相关的C++源码实现，方便读者理解和实践。作者还列举了计算几何领域的一些经典书籍，如《Geometric Tools for Computer Graphics》和《Computational Geometry: Algorithms and Applications》，供进一步学习参考。 这篇文章对于理解如何用编程方式解决计算几何问题，特别是求解凸多边形直径的问题，提供了非常实用的信息。通过阅读和实践，读者可以掌握这一算法，并将其应用于实际的计算机图形学或相关领域的项目中。