huangli321456
星辰落
采纳率33.3%
2018-06-25 09:05 阅读 4.3k
已采纳

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

5

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

或者下面这样的
图片说明

欢迎各位大神提供思路

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

4条回答 默认 最新

  • 已采纳
    caozhy 从今以后生命中的每一秒都属于我爱的人 2018-06-25 15:25
    点赞 评论 复制链接分享
  • qq_41686694 qq_41686694 2018-06-25 09:21

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

    点赞 2 评论 复制链接分享
  • suchvaliant suchvaliant 2018-06-25 09:33

    数学归纳法证明:一个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个三角形.

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

    点赞 1 评论 复制链接分享
  • szja402 szja402 2018-06-27 01:11

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

    点赞 评论 复制链接分享

相关推荐