【文件属性】：
文件名称：随机生成凸多边形-python读取mat文件并转为csv文件的实例
文件大小：9.75MB
文件格式：PDF
更新时间：2021-06-10 00:01:12
算法
图 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 步中简单多边形至少存在一条边对