计算几何：Python实现简单多边形的单调性与凸性判定

"该资源是一份关于计算几何的教程，主要介绍了如何判断简单多边形的性质，如单调性和凸性，并提供了相应的算法。作者提供了C++源代码实现，并提到了Shamos-Hoey算法和Preparata&Supowit算法等经典方法。" 在计算几何领域，多边形的属性分析是重要的研究内容。本文档主要探讨了如何判断简单多边形的两种关键特性：单调性和凸性。简单多边形是指没有自我相交边的多边形。 6.3.1 简单多边形的单调性 简单多边形的单调性是指多边形的所有边都沿着一个固定方向，如上至下或左至右，没有反转。在二维空间中，对于逆时针顺序的简单多边形，可以通过检查每条边相对于水平轴的倾斜方向来判断其是否单调。Preparata&Supowit在1981年提出的算法，具有最优的线性时间复杂度，可以有效地解决这个问题。 6.3.2 多边形的凸性 多边形的凸性是判断其是否每个内角都小于180度。一个简单的多边形可能是凸的，也可能是凹的。Schorn&Fisher在1994年提出了一个线性时间复杂度的算法，可以直接判断多边形是否为凸的，无需先判断简单性。若先判断简单性再判断内角，算法的时间复杂度会提升到O(n log n)。 Shamos-Hoey算法(1976)是用于判断线段集是否存在相交的一种方法，其时间复杂度为O(n log n)，在多边形简单性判断中起着关键作用。这个算法可以有效地检测多边形的边是否自相交，从而确定其是否为简单多边形。 本教程还包括其他计算几何的基础内容，如向量和矩阵的数学概念，以及与之相关的算法，如面、线、三角形和矩形的处理。此外，还介绍了多边形类型判定、旋转测径法，以及三维空间下的凸包算法和包围体算法。 作者提供了源代码库，便于读者深入理解和实践这些算法，同时也欢迎读者指出错误和提供反馈，以便不断改进和完善教程内容。此外，作者还推荐了几本计算几何的经典书籍，供读者进一步学习和参考。