天空留不下飞鸟的痕迹,但我已飞过

统计

留言簿(1)

often go---Blogs

often go---GeoLogy

often go---Opengl

often go---SoftwareTest

阅读排行榜

评论排行榜

1 任意不自相交的凹多边形实现三角剖分

输入:凹多边形的顶点序列p1、p2、、、、pn;
输出:剖分形成的三角集合
剖分方法:
        1) 从顶点p1开始,判断连续的三点p1p2p3组成的三角形是否为逆时针,若是则将三角型p1p2p3添加到三角型集合中,在顶点序列链表中去掉顶点p2,然后判断连续的三点p1p3p4是否构成逆时针三角形;若p1p2p3组成三角形为顺时针,则从p2点开始重复步骤1)继续处理顶点序列,相邻三点组成逆时针三角形,则从顶点序列中去掉中间点,并将该三角形添加到三角形集合中。
 注:判断三角形ABC是否为逆时针,只需判定向量AC角度是否大于向量AB 或根据三角形面积是否为正判断。三角形面积为正,三角形为逆时针,否则为顺时针。
计算三角形面积公式:s = 0.5*   | x1  y1  1  |

                                                        |x2  y2  1  |

                                                        |x3  y3  1  |

A(x1,y1) B(x2,y2) C(x3,y3) 

posted on 2009-05-18 22:31 BirdOfWonder 阅读(3053) 评论(2)  编辑 收藏 引用 所属分类: 图形学简单算法

评论

# re: 1 任意不自相交的凹多边形实现三角剖分[未登录] 2011-07-18 14:43 天地之灵

Hi,此算法某情形下有问题,还需判断: 没有其它顶点在此次剖分的三角形内。  回复  更多评论   

# re: 1 任意不自相交的凹多边形实现三角剖分 2014-01-03 08:52 彩天蝶文

楼上正解  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理