·1296· 北京科技大学学报 第33卷 8 g。 00 。 a o a 4 00 00 0 80 00 00 0g0。° 00 0 0 g (bi 图5决策线构建示例.(a)判别域：(b)各类凸壳运算：(c)整体凸壳运算：(d)差集多边形：(c)Delaunay三角剖分：()中轴线提取； (g)中轴线延展：(h)形成决策边界 Fig.5 Demonstration of constructing decision-making boundaries:(a)discriminant space:(b)convex hulls of classes;(c)integral convex hull; (d)interval space polygon among classes:(e)Delaunay triangulation:(f)extracting polygon axes:(g)extending polygon axes:(h)generating classification boundaries 首先，在二维判别域空间（图5(a)上，采用凸 间隙所构成的差集多边形（图5(）)，目的是生成 壳运算找寻c个离散点集各自的类凸壳（即子凸壳， 模式类间分隔间隙 图5(b)以及由c个离散点集构成的总离散点集的 随后，对凸壳间隙差集多边形进行Delaunay三 整体凸壳（即总凸壳，图5（©）).对离散点集进行凸 角剖分（图5(e)).所谓的多边形Delaunay三角剖 壳运算实质是找到某类模式离散点集的最小包围 分即为将多边形拆分为满足Delaunay三角剖分的 域.计算平面点集凸壳的算法主要有格雷厄姆算 原则（即空圆特性、最大化最小角特性以及多边形 法、卷包裹法、分治算法、增量算法、实时算法、快速 三角剖分特性)的三角网，由此得到的多边形三角 算法和周培德的Z3-8算法等，本文采用了格雷厄 网具有唯一性、最优性和区域性等优异的特性© 姆算法针对各类模式离散点集求其子凸壳，并混合 本文进行任意多边形的Delaunay三角剖分的算法， c个离散点集构成总离散点集计算出总体凸壳. 在构网的同时考虑约束边的影响，直接构建Delau- 然后，进行总凸壳与各子凸壳的差集运算.求 nay三角网) 解总凸壳与各子凸壳的差集利用了多边形差集布尔 最后，在Delaunay三角网的基础上构建多边形 运算的概念.运算的基本思路是：求解两多边形A、 的中轴线（图5(）的粗线)并延展（图5(g)的粗 B的差集A-B,若A∩B=②，则C=A=A-B;否则 线)，形成c个模式类的分类决策线（图5(h)),完 C=A-A∩B.运算布尔找到判别域内由各子凸壳 成模式识别分类器的构建.这里，多边形中轴也叫北 京 科 技 大 学 学 报 第 33 卷 图 5 决策线构建示例． ( a) 判别域; ( b) 各类凸壳运算; ( c) 整体凸壳运算; ( d) 差集多边形; ( e) Delaunay 三角剖分; ( f) 中轴线提取; ( g) 中轴线延展; ( h) 形成决策边界 Fig． 5 Demonstration of constructing decision-making boundaries: ( a) discriminant space; ( b) convex hulls of classes; ( c) integral convex hull; ( d) interval space polygon among classes; ( e) Delaunay triangulation; ( f) extracting polygon axes; ( g) extending polygon axes; ( h) generating classification boundaries 首先，在二维判别域空间( 图 5( a) ) 上，采用凸 壳运算找寻 c 个离散点集各自的类凸壳( 即子凸壳， 图 5( b) ) 以及由 c 个离散点集构成的总离散点集的 整体凸壳( 即总凸壳，图 5( c) ) ． 对离散点集进行凸 壳运算实质是找到某类模式离散点集的最小包围 域． 计算平面点集凸壳的算法主要有格雷厄姆算 法、卷包裹法、分治算法、增量算法、实时算法、快速 算法和周培德的 Z3 － 8 算法等，本文采用了格雷厄 姆算法针对各类模式离散点集求其子凸壳，并混合 c 个离散点集构成总离散点集计算出总体凸壳． 然后，进行总凸壳与各子凸壳的差集运算． 求 解总凸壳与各子凸壳的差集利用了多边形差集布尔 运算的概念． 运算的基本思路是: 求解两多边形 A、 B 的差集 A － B，若 A∩B = #，则 C = A = A － B; 否则 C = A － A∩B． 运算布尔找到判别域内由各子凸壳 间隙所构成的差集多边形( 图 5( d) ) ，目的是生成 模式类间分隔间隙． 随后，对凸壳间隙差集多边形进行 Delaunay 三 角剖分( 图 5( e) ) ． 所谓的多边形 Delaunay 三角剖 分即为将多边形拆分为满足 Delaunay 三角剖分的 原则( 即空圆特性、最大化最小角特性以及多边形 三角剖分特性) 的三角网，由此得到的多边形三角 网具有唯一性、最优性和区域性等优异的特性［10］． 本文进行任意多边形的 Delaunay 三角剖分的算法， 在构网的同时考虑约束边的影响，直接构建 Delau￾nay 三角网［11］． 最后，在 Delaunay 三角网的基础上构建多边形 的中轴线( 图 5 ( f) 的粗线) 并延展( 图 5 ( g) 的粗 线) ，形成 c 个模式类的分类决策线( 图 5( h) ) ，完 成模式识别分类器的构建． 这里，多边形中轴也叫 ·1296·