凹多边形的切割
凹多边形的分割
算法来源
Elements of Computer Graphics.pdf
算法概述
已知：凹多边形不存在空洞。
- 对凹多边形顶点进行编号
- 找出凹点
- 绘制凹点的延长线（延长线的起点为 凹点的上一个点）
- 延长线与凹多边形求交点
- 凹点延长线的情况
- 延长线与多边形只有一个交点
- 保留凹点到交点的线段
- 延长线与多边形有多个交点
- 保留凹点到每一个交点的最短距离的线段
- 延长线互相相交
- 根据凹点的出现顺序决定是否能够修改，第一个出现的凹点不可以修改，只能修改第二个出现的点
- 延长线与多边形只有一个交点
算法图示结果
注
本文代码及可视化代码均放在 gitee 码云上 欢迎star & fork