M丹+B-2 定理二和三的内容及证明虽然和参考文献【】里稍有区别，但对算法却提供了有力的依 据。它使我们从形形色色的图形，各种可能的刘分方式中解放出来，在考虑算法时，只要对 并联型的凹点先以直线连接，其它凹点按合理划分进行，就能获得最优划分。 在参考文献【！里给出一种刘分的算法，其基本想法转述如下： (1)在P的水平边中，设y坐标最大的边为AB=(x1,x',y)。其中x1为A点的x 坐标，x'为B点的x坐标，y:为AB的y坐标。 (2)在沿X轴向，投影与AB重迭的边中，设y坐标最大的边为CD,且 CD=(x2,x',y:),(x1,x)∩(x2,x'2)丰中 (3)设矩形L为由AB和从A、B点向下作的垂线以及CD所围成，即 L={(x,y)∈R2|x≤x≤x'1,y2≤y≤y} (4)如L=P,则计算完毕，如果不是，就把从P中减去L后的图形，重新作为P(数据 结构要更新)，再从头开始计算。 这个算法对定理二指出的情况能给最小划分，出对有并联型凹点的图形则不能求得最优 解答。此外文中只给出想法而没有写明采用什么样的数据结构表示图形P。下面就这些方面 进一步作一些探讨和改进。 1.败据结构 图形P的内外边界都是简单回路，它的每个頂点的内向积和外向积均为1。为了算法中 经常要存取、插入和删除，考忠用双向链表来表示图形P。每条闭合的边界线用一条环形链 来表示。链表的每个结点，其数据城存放图形頂点的编号、坐标和凹点标记：另外有两个指 针，向前指针存放先导结点的地址和编号，向后指针存放后继结点的地址。以Y坐标最大中 最右的一点为链头。以链头所在的水平向量为首向量。以逆时针作为外边界的链表指向，以 顺时针作为内边界的链表指向（图4），图中A、B各为相应的链头。 2.算法 (1)设有首向量AB=(x1,x'1,y1),取其先导向量EF(x2,x',y:)和后继向量 CD(x,x',y)检查C、D、E、F四点中有无凹点，有则执行下一步，否则，置状态变 量0=3，转第4步。 (2)如果(x1,x')∩(x2,x'2)∩(x3,x') =中，且y:=ys,则令yz为y,置变量o=0(如 图5)，否则，令y=max{y2,y}(两数中取 大值)，置变量o=1(如图6) (3)取各内边界的首向量（x1,x‘:1)i=1 2…m。如果(x1,x)∩(x1,x')牛中且y: 图4 图5 >y则令y=yi,置①=2。 (4)按状态变量⊙，作下列处理，输出矩形L和更新数据结构。 对@=0，作并联处理事 ⊙=1，作单凹点处理影 0=2,作中空处理 ①=3，作无凹点处理。（见下面说明）。 146、 ， ， ’ 州 二生 — 十 艺 — 定理二和三 的内容及证 明 虽然和 参考文 献 ‘ 里 稍有区别 ， 但 对算法却提供 了有力的依 据 。 它使我 们从形形 色色的图形 ， 各种可 能 的划 分方 式 中解放 出来 ， 在考虑算法时 ， 只 要对 并联 型 的 凹点 先 以 直线连 接 ， 其 它 凹点按 合 理划 分进 行 ， 就 能获 得最优划 分 。 在 参考文 献 ‘ 里给 出一种 划分 的 算法 ， 其基 本 想法 转述如 下 一一 寸 在 的 水 平边 中 ， 设 坐标最大的边为 ， ， ， 。 其 中 为 点的 且 一 州 坐标， 尹 为 点的 坐标， 为 的 坐标 。 在 沿 轴 向 ， 一 ， 投影 与 重 迭的 边 中 ， 设 坐标 最大的 边为 ， 产 ， ， ， ， 尹， ， 斗 小 设 矩形 为由 和 从 、 点向下 作的垂 线 以 及 所 围成 ， 即 ， 〔 三 三 尹 ， 三 三了 “ 如 ， 则计 算完毕 ， 如 果不 是 ， 就 把 从 中减去 后 的 图 形 ， 重新 作为 数据 结 构要 更新 ， 再 从头开 始计 算 。 这 个算法对定 理二 指 出的 情况 能 给 最小 划分 ， 出对 有并联 型 凹点的 图 形则不 能 求得最优 解答 。 此外文 中只 给出 想法而没有写 明采用 什 么样 的 数据结 构表示 图形 。 下面就这些 方面 进 一 步作一些 探讨 和 改 进 。 胜 结构 图 形 的 内外边界都是 简单 回路 ， 它的每个顶 点的 内向积和 外向 积均为 。 为 了算法中 经 常要 存取 、 插 入 和 删除 ， 考虑 用 双 向链 表 来表示 图 形 。 每 条 闭合的 边界线用一 条环形链 来表示 。 链表的 每个结 点 ， 其数据域 存放图形顶点的 编号 、 坐标和 凹点标记， 另外有两个指 针 ， 向前指 针存放先导结 点的 地址 和 编 号 ， 向后 指针存放后继结 点的 地址 。 以 坐标最大 中 最右的 一 点为链头 。 以链 头所在 的水 平向量为首 向量 。 以 逆时针作为外 边界的链 表指 向 ， 以 顺时针作为内边界的 链 表指 向 图 ， 图 中 、 各为 相应 的链 头 。 算 法 门 一 寸 设有首向量 ， 产 ， ， ， 取 其 先导 向量 ， 了 ， 和 后 继 向量 。 ， 尹 ， 检 查 、 、 、 四 点 中有无 凹点， 有则执 行下一 步， 否则 ， 置状态 变 。 ， 转 第 步 。 如 果 ， 矛 门 ， ， 门 。 ， 尹 小 ， 且 。 ， 则令 为 ， 置 变量 。 如 图 ， 否则 ， 令 ， 两数 中取 大值 ， 置 变最 。 如图 取 各内边界 的 首 向量 ‘ ， 矛‘ … … 。 如 果 ， 尹 门 ‘ ， ， 尹‘ 今 小且 ‘ ， 图 图 则令 ‘ ， 置 。 。 按状态 变最 。 ， 作下 列 处 理 ， 输 出矩 形 和 更新 数据结 构 。 对 。 二 ， 作 并联处 理， 。 ， 作单 凹 点处理， 。 ， 作 中空处理， ① ， 作无 凹 点处理 。 见 下面说 明 。 母