简单多边形三角剖分的算法：考查连续三个 顶点A,B,C,若AC完全在多边形内部，则可输出 △ABC为一个剖分后形成的三角形，删除点B 后再对少了一个顶点的多边形继续进行。 简单多边形的顶点序列为P,P1,P1,那么算 法可描述如下： SIMPLE POLYGON TRIANGULATION 1.(准备)Qo-Po; 2.〔剖分)若n>3,则做2.1~2.2，否则转到步3： 2.1Q1←-点序列中Q的下一个顶点；Q2←-点 序列中Q的下一个顶点； 2.2若Test(Q,Q1,Q2)为真，则做： 输出△QQ1Q2
简单多边形三角剖分的算法:考查连续三个 顶点A,B,C,若AC完全在多边形内部,则可输出 △ABC为一个剖分后形成的三角形,删除点B 后再对少了一个顶点的多边形继续进行。 简单多边形的顶点序列为P0 ,P1 ,Pn-1 ,那么算 法可描述如下: SIMPLE POLYGON TRIANGULATION 1.〔准备〕Q0←P0 ; 2.〔剖分〕若n>3，则做2.1~2.2,否则转到步3: 2.1 Q1←点序列中Q0的下一个顶点;Q2←点 序列中Q1的下一个顶点; 2.2 若Test(Q0 ,Q1 ,Q2 )为真,则做: 输出△Q0Q1Q2 ;
从点序列中删除顶点Q: n←n-1, 返回步2开头； 否则做Q←Q1,返回步2.1； 3.〔最后输出)输出点序列中剩下三点为最后一个三 角形，然后算法结束。 函数Test是对△Qo9,92进行检查，分两步实现， 第一步检查Qo,Q1,Q2是否是一个在Q,的左转，若不然， 是右转，则QQ,在多边形外部而可以回答假而结束。 第二步可对原多边形中除去Qo,Q1,Q2这三点的其它点， 对每一点都考查它对三角形的包含性，若有一点被包 含则就可以回答假而结束，只有其它点都在三角形外 部时才能回答真而结束
从点序列中删除顶点Ql ; n←n-1; 返回步2开头; 否则做Q0←Q1 ,返回步2.1; 3.〔最后输出〕输出点序列中剩下三点为最后一个三 角形,然后算法结束。 函数Test是对△Q0 Q1 Q2进行检查，分两步实现, 第一步检查Q0 ,Q1 ,Q2是否是一个在Ql的左转,若不然, 是右转,则Q0 Q2在多边形外部而可以回答假而结束。 第二步可对原多边形中除去Q0 ,Q1 ,Q2这三点的其它点， 对每一点都考查它对三角形的包含性,若有一点被包 含则就可以回答假而结束,只有其它点都在三角形外 部时才能回答真而结束
最小权三角剖分或最小三角剖分 如果一个三角剖分中选取的对角线的总长 度最小。 任意的凸多边形最小三角剖分 V2 V3 V3 V1 V4 V4 V5 VO V5 V6 V6 (1) (2)
最小权三角剖分或最小三角剖分 如果一个三角剖分中选取的对角线的总长 度最小。 任意的凸多边形最小三角剖分
事实3 在n边形(n≥3)的任意一种三角剖分中 每一对相邻顶点中至少有一个顶点是某条对 角线的端点。 因为若相邻顶点V,V+都不是某条对角线 的端点，则区域(W;-1,V,V+,V+2)中没有对角 线，因而也就没有被三角剖分。 事实4如果VV:是三角剖分的一条对角线，则 一定存在某顶点Vk,使得VVk和VkV是多边形 的边或对角线。 因为若不然，一定存在以VV:为边界的某 个区域没有被三角剖分
事实3 在n边形(n≥3)的任意一种三角剖分中, 每一对相邻顶点中至少有一个顶点是某条对 角线的端点。 因为若相邻顶点Vi ,Vi+1都不是某条对角线 的端点,则区域(Vi-1 ,Vi ,Vi+1,Vi+2)中没有对角 线,因而也就没有被三角剖分。 事实4 如果Vi Vj是三角剖分的一条对角线,则 一定存在某顶点Vk ,使得Vi Vk和Vk Vj是多边形 的边或对角线。 因为若不然,一定存在以Vi Vj为边界的某 个区域没有被三角剖分
顶点序列Vo,V,一，Vn确定的凸n边形的最小 三角剖分 挑选两个相邻顶点比方选V和V1,由事实 3知道在最小三角剖分中，必有另一顶点Vk, 或者使VV是对角线，或者使VoYk是对角线。 对有n个顶点的多边形，V的选取方法 有n-3种。 对于每个可能的Vk用对角线VoVk(或VVk) 把原多边形剖分成两个较小的多边形，这样 原问题就被分成为两个子问题。 往下需要寻找分成的两个较小凸多边形 的最小三角剖分。（递归)
• 顶点序列V0 ,V1 --,Vn-1确定的凸n边形的最小 三角剖分 挑选两个相邻顶点比方选V0和V1 ,由事实 3知道在最小三角剖分中,必有另一顶点Vk , 或者使V1 Vk是对角线,或者使V0 VK是对角线。 对有n个顶点的多边形，Vk的选取方法 有n-3种。 对于每个可能的Vk用对角线V0 Vk (或V1 Vk ) 把原多边形剖分成两个较小的多边形,这样 原问题就被分成为两个子问题。 往下需要寻找分成的两个较小凸多边形 的最小三角剖分。（递归）