任意多边形拆分长多个三角形

如题,有什么算法能将一个不规则的任意多边形拆分成多个三角形呢?例如下面这
样的多边形
图片说明

或者下面这样的
图片说明

欢迎各位大神提供思路

4个回答

huangli321456
星辰落 谢谢,虽然后面也找到这个算法了,分还是给你吧
大约 2 年之前 回复

对于凸多边形,可以选取一个点k,然后从这个点开始顺序取(k+1,k+2)(k+2,k+3)……和点k组成三角形。如果不是凸多边形的话,就看看能不能把它切割成凸多边形。
凸多边形的性质就是外角和为360度或所有内角都小于180度,可以由此判断是否时凸多边形。

数学归纳法证明:一个k边形可以分解为若干个三角形
K=3 显然成立
假设k(k>3)边形都可以分解为k-2个三角形 ,那么对于k+1边形A1A2……AkAk+1,连A1Ak,就把它分成△A1AkA和k边形A1A2……Ak,由归纳假设,k(k>3)边形都可以分解为k-2个三角形,∴k+1边形可以分解为k-2+1=k-1个三角形.
综上,n(n>3)边形都可以分解为n-2个三角形.

分割算法: 耳切法处理多边形三角划分

对于n条边的多边形,随意取一个角点A,则设连接该点的边为S1和S2,两条边端点分别为B、C。连接BC得到S3,判断S3是否在该多边形的内部。如果是,则得到一个三角形和一个新的n-1条边的多边形,对新的多边形进行迭代操作,直到这个多边形为三角形;如果不是,选下一个角点进行迭代操作,直到S3在该多边形的内部。这样就得到了n-2个三角形。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐