文件名称：随机生成凸多边形-python读取mat文件并转为csv文件的实例
文件大小：9.75MB
文件格式：PDF
更新时间：2024-06-29 17:47:52
算法
图 6.9 随机生成凸多边形 6.2.5. 简单多边形的生成算法 问题描述：随机生成不重合的 n 个点的点集 0 1 1, , , nS P P P ，由该点集生成一个逆 时针顺序的简单多边形。 方法一. 稳定增长法 CH(S)表示包围点集 S 的凸多边形，算法主要分为四个步骤： i. 从点集 S 中任取三个点 0 1 2 , , i i i P P P ，构成初始的简单多边形 1 T ，需要保证 1 T 中不 包含点集中的其它点，令 0 1 21 , , i i i S S P P P ； ii. 从 , 1 m S i 中任取一个点 i P ，从点集 m S 中移除该点 1 { } m m i S S P ，保证 1m S 中不 存在点在 ( { }) m i CH T P 内； iii. 从简单多边形 m T 中找到一条边 1k k V V ，使得它对点 i P 完全可见，然后把该边替换 为 k i V P 和 1 V i k P ，得到新的简单多边形 1m T ； iv. 若 1m S 不为空，重复算法第 ii~iii 步。 满足第 ii 步的点 i P 总是可以找到，这保证了第 iii 步中简单多边形至少存在一条边对