基于Web的CAD系统中最小不规则封闭区域的识别方法.pdf

收稿日期 2004 07 05 基金项目 安徽省自然科学基金资助项目 03044106 作者简介 伍 梅 1979 女 湖南津市人 助教 硕士研究生 主要研究领域为计算机图形学和 CAD CAM AutoCAD SolidEdge SolidWorks UG Pro E等各种现代CAD系统都在努力提高系统的 智能化 以提供给用户最大的使用方便和准确理 解 作者所在的研究组正在研发的基于协同设计 的 WebCAD 系统同样也在为此而努力 研发的 WebCAD 系统没有使用如 AutoCAD 一类的任何 CAD 平台及如 OpenGL 一类的图形工具 而是 使用 Java 语言开发以使 WebCAD 系统真正脱离 操作系统且拥有自主版权 该系统可以更有效的 使用各种数据资源 减少试制成本 缩短产品设 计生产周期 提高效率 提高市场竞争力 1 目 前该系统是一个机械制图网络教学系统的一个 重要组成部分 旨在便于师生远程完成制图作业 和批改作业的需要 提高教学质量 图形填充功能 Hatch 是所有 CAD 软件中必不可少的功能 而实现 Hatch 等功能时 首先必须能识别出鼠标 点击处所在的最小封闭区域 从而能实现对区域 的准确填充 面积计算等操作 如何能准确有效 地找到最小封闭区域是关键所在 1 WebCAD 系统总体结构 Internet 技术的不断发展和人们对 CAD 的需 求 使得利用 Internet 在 Web 上发布 CAD 图纸 为用户提供 CAD 图纸浏览 查询 管理和分析 功能 以及提供异地协同设计功能 已经成为 CAD 发展的必然趋势 2 研究建立了一个直接在 Internet 上的协同设计环境 用户可以通过该环 境进行共享资源的异地协同设计 本系统的功能 模块如图 1 所示 其中协同设计模块采用的是一 个 Browser Server Data 的三层结构体系 如图 2 所示 在这个三层的体系结构中 客户端是运行在 浏览器上的 Applet 服务器是一个 Server 端 Java Application 而数据端采用 MySQL 数据库 三 层中 服务器端是中间层 它在用户数据的交互 中起到中间桥梁的作用 多用户的交互包括 Applet 和 Server 以及 Server 和数据端的交互 它 们之间的交互过程如图 3 所示 对于系统中权限 20052005 年 工 程 图 学 学 报 20052005 第 4 4 期 JOURNAL OF ENGINEERING GRAPHICS No 4 基于 Web 的 CAD 系统中最小不规则 封闭区域的识别方法 伍 梅 沈连婠 刘亚明 赵 玮 李木军 郑津津 中国科学技术大学 合肥 230026 摘 要 介绍了自行研发的 WebCAD 网上协同设计系统及在此系统中研发的基于 Web 的图形填充区的识别模块 重点介绍了此模块研发中提出的一种最小不规则封闭区域识 别方法 即将二维曲线看成由两条走向相反的边构成 通过环的跟踪识别出任意的最小不规 则封闭区域 文中给出了算法的具体实现方法和步骤 关 键 词 计算机应用 最小不规则封闭区域识别 循环搜索 网络 CAD 中图分类号 TP 391 文献标识码 A 文 章 编 号 1003 0158 2005 04 0036 05 图 1 系统的功能模块 的管理将采用用户组 用户的方式进行分级权限 控制和角色定义 如图 4 所示 文件操作部分实 现了对 DWG 和 DXF 两种重要图形文件的存取 功能 且正在开发对 DWF 文件的存取功能 图 2 Browser Server Data 三层结构 在系统中给服务器 登记一个服务地址 在系统中给服务器 登记一个服务地址 Listen 通知TCP服 务器监听连接请求 Listen 通知TCP服 务器监听连接请求 Accept 阻塞直到 客户方连接 Accept 阻塞直到 客户方连接 Accept 接收到客 户方连接 Accept 接收到客 户方连接 创建输入输出流创建输入输出流 处理来自客户端数 据 处理来自客户端数 据 Send 返回结果给 客户端 Send 返回结果给 客户端 结束结束 创建Socket创建Socket 连接服务器连接服务器 创建输入输出 流 创建输入输出 流 用户一次操作完成用户一次操作完成 Send 发送数 据到服务方 Send 发送数 据到服务方 接受来自服务 器的消息 接受来自服务 器的消息 显示显示 创建Socket创建Socket 结束结束 DatabaseDatabase 连接连接 客户方服务器方数据库客户方服务器方数据库 过程模型 组织模型 角色 授权 设计人员 执行 任务 图 3 交互过程示意图 图 4 角色定义示意图 WebCAD 已不局限于 CAD Viewer 网络浏览 和 CAD Mark Up 网络审批 功能 它应该有健壮 的设计环境 在浏览的同时实现对某一产品的异 地设计 具体来说 应该包括工程图样的建立 浏览 修改 设计等 因此 本研究的一大重点 就是设计出完备的图形模块 提供强大的绘图功 能 把传统 CAD 的功能移植到网络 以网络为 载体 实现了资源共享 在本系统的图形模块设 计中 图形区域识别及填充模块的实现是一个重 点也是一个难点 下面将作详细的介绍和探讨 该 WebCAD 系统由 Java 语言开发完成 具 有平台无关性 并充分利用文字 声音等多媒体 的交流手段 使得不同背景 不同学科的工作人 员能够很好的交流 是一个真正意义上的网络 CAD 系统 2 系统中图形区域识别及填充模块 的实现方法 基于 Web 的 CAD 系统需要有完备的图形设 计模块 提供强大的绘图功能 以网络为载体 实现资源共享 这个系统的设计模块中 图形区 WebCAD 系统 网络集成 文件操作 设计环境 协同设计 html jsp 新建文件 打开文件 修改文件 保存文件 绘图工具 辅助工具 图层管理 Browser 显 示 逻 辑 服务器 事务 处理 逻辑 数据 处理 逻辑 数据 第 4 期 伍 梅等 基于 Web 的 CAD 系统中最小不规则封闭区域的识别方法 37 域识别及填充模块的实现是不可缺的 2 1 问题提出及主要思想介绍 已知一组由二维曲线构成的图形 要根据其 中的某一点 文中将其称为种子点 识别出包含 该点的最小封闭区域 如图 5 所示 P0点所在的 斜线填充区域 这种矢量化图形中寻找最小边界 的问题通常出现在矢量图形系统的填充功能及 边界识别功能中 在一些三维系统中 在利用二 维区域拉伸或旋转产生三维模型时也会遇到这 种问题 图 5 封闭区域示意图 本算法的主要思想是将二维曲线看成由两 条走向相反的边构成 开曲线的两条边形成一个 逆时针方向的外边界 闭曲线的两条边形成一个 逆时针方向的外边界和一个顺时针方向的内边 界 对自交的曲线可以在交点处将曲线分段处 理 曲线的相交可以看成是边界的相交 相交 之后的边界由一个外边界和若干个内边界组成 外边界和内边界都是一串首尾相接的有向曲线 构成的封闭曲线组 外边界为逆时针方向 内边 界为顺时针方向 如图 6 所示 这样 所求得 最小区域就由包含种子点的最小的内边界 和包 含在该内边界中的孤岛的外边界组成 图 6 曲线双边界示意图 这样处理以后得的边界不存在3条及以上的 边界线交于一点的情况 就是说在同一点 指边 界上的转折点 上将不再存有 3 条及 3 条以上的 曲线 使得循环搜索时的对象变得单纯 避免了 各种分支情况 从而使程序中的数据结构十分简 单 下面具体介绍一下应用此思想的区域识别实 现步骤 2 2 区域识别的具体实现步骤 第 1 步 确定线段与 P0的位置关系 从种子点 P0作一条向右无穷远的水平射线 分别与图面上的曲线相交于 P1 P2 Pn各点 如图 7 所示 将这些点按到 P0的距离从小到 大排序 将最近的点加入队列中 图 7 水平射线示意图 第 2 步 搜索最小封闭边界 设队列中最后加入的点为 Q1 此点所在曲线 L 的切向为 V1 如图 8 所示 利用 Q1和 V1寻找 经过点 Q1并且同 V1逆时针方向的夹角最小的曲 线 S 如果有多条曲线在 Q1点的切向相同 则按 曲率大小确定 令曲线 S 在 Q1点的切向为 V2 曲线 S 同其他曲线交点中在 V2上最接近 Q1的点 为 Q2 如果队列中已经存在 Q2点 则说明从 Q2 点开始队列中的各个点所在的曲线段组成了一 个封闭的边界 进行第 3 步 否则将 Q2加入队 列 重复第 2 步 图 8 边界搜索示意图 P0 c 38 工 程 图 学 学 报 2005 年 P0 P1 P2 V2 V1 V1 P Q1 4 L Q2 1 1 2 3 S 2 3 V2 第 3 步 判断种子点 P0是否在找到的封闭 边界之内 利用第2步找出的边界如果为外边界则不包 含种子点 P0 这样的边界不符合要求 因而 需 要检验种子点 P0是否在找到的封闭边界之内 从种子点 P0作一条向右的射线同边界相交 如 果交点的个数为奇数 则表明种子点在封闭边界 之内 该边界为内边界 否则种子点在边界之外 该边界为外边界 3 如果为内边界进行第 4 步 否则清空整个队列 将第 1 步中的下一个点放入 队列中 返回第 2 步 第 4 步 识别内边界内的孤岛 得到所求得 最小区域 到此为止 找到了包含种子点的最小内边 界 接下来需要去找边界内各孤岛 如图 5 斜线 填充的封闭区域中的圆 c 对不在内边界上的其 他曲线 判断每一条曲线是否在内边界以内 对 所有的内部曲线利用类似第2步的方法找到它们 的外边界 最小内边界及各个外边界合在一起就 构成了所求的最小区域 2 3 最小封闭区域识别的程序实现 用 Java 语言实现了由线段 圆 圆弧 椭圆 椭圆弧和样条曲线所构成的矢量图形组中最小 封闭区域的识别 整个程序的流程图如图9所示 最小封闭区域找到后就可以用传统的扫描 线算法实现对识别出的区域进行填充 3 方法在 WebCAD 系统中的实际 应用 在研发的一个基于 Web 的 CAD 系统中 笔 者利用该方法开发了如图 10 所示的协同环境中 的填充模块 图 10 的工具栏中用圆圈标出的图 标模块 图中以不同的填充图案以区分识别到 的不同最小区域 从图中可以看出 应用此方法可以正确的识 别出由样条 椭圆 直线 圆等构成的矢量图形 组中的最小封闭区域 取得了好的效果 多次测 试表明 运算稳定 从未出现误判 4 结 论 该 WebCAD 系统由 Java 语言开发完成 具 有平台无关性 并充分利用文字 声音等多媒体 的交流手段 使得不同背景 不同学科的工作人 员能够很好的交流 是一个真正意义上的网络 CAD 系统 文中介绍的最小不规则封闭区域识 别方法涉及的数据结构简单 计算量小 将二维 曲线看成由两条走向相反的边构成 通过一些布 尔运算识别出任意的最小不规则封闭区域方法 图 9 最小封闭区域识别程序流程图 获取鼠标输入点 记为 P0 从P0作无穷远的水平直线L L 与各曲线交点 P1 P2 Pn 并根据到 P0的距离排序 依次从 P1 到 Pn中寻找最近点P 清空队列 判断 P 和 L 是否已经存在 于队列中 将P和L的方向V记录到队列中 寻找所有经过P的曲线中顺时针 方向与 V 夹角最小的曲线 S 寻找 S 上距离 P 最近的点 Q 并 令 P Q L S 判断 P0是否 在队列所组成的区 域内部 对所有不在队列 中的曲线 判断是否有曲 线落在区域内部 找到包含该曲线的最外区域 并 将该区域加入队列中 成功失败 没有找到 已经存在 不存在 否 是 不存在 存在 找到 P 点 第 4 期 伍 梅等 基于 Web 的 CAD 系统中最小不规则封闭区域的识别方法 39 图 10 WebCAD 中的应用 通用性好且准确无误 利用这种最小不规则封闭 区域识别算法识别出最小区域后还可与其它算 法结合 实现扫描填充 笔者已实现 区域合 并 面积计算等功能 满足工程中的各种需要 参 考 文 献 1 马永军 李荣彬 张 曙 制造网络的发展状况 J 机械科学与技术 2000 3 458 462 2 Zeng Jianjiang Chen Wenliang Ding Qiuling A Web based CAD system J Journal of Materials Processing Technology 2003 139 229 232 3 奚梅成 数