TOP

矢量图形(line和circle)在非自交多边形边界中的裁剪显示
2015-02-06 10:08:25 来源: 作者: 【 】 浏览:18219

 第四届“中国软件杯”大学生软件设计大赛

赛题原型反馈表

赛题名称: 矢量图形(line和circle)在非自交多边形边界中的裁剪显示

组类( A ): A 本科及以上   B 高职组

赛题简介:介绍整个赛题的思路和整体要求

在计算机图形学中,为了描述图形对象,我们必须存储它的全部信息,但有时为了达到分区描述或重点描述某一部分的目的,往往将要描述的部分置于一个窗口内,而将窗口外的部分“剪掉”,这个处理过程叫做裁剪,裁剪在计算机图形处理中具有十分重要的意义。裁剪涉及到两点:

1、图形元素与窗口边界的求交;

2、图形元素在窗口内外的判别。

裁剪的效率将影响到图形计算、处理、显示的速度和用户体验。本题要求实现一个可执行程序,该程序中使用的算法可以原创,也可以是对经典算法的改进和优化,该程序能实时高效地计算矢量图形(line、circle)与任意多边形区域(本题特指非矩形的且非自交的凸多边形及凹多边形)的交点,并且判断图形的哪些部分在多边形边界内部,哪些部分在多边形边界外部,同时能正确显示位于多边形边界内部的图形部分,不显示位于多边形边界外部的图形部分。

整体要求:

1)实现基本功能的基础上,并尽可能提升时间和空间效率;

2)开发语言不限(C++、Java均可),该题已提供两套源码框架供参赛者使用(C++、Java各一套),参赛选手也可自行搭建框架,只要能满足“功能性需求”所提出要求即可。

赛题业务场景:描述赛题相关的真实企业业务背景。从真实场景中,适当简化或者提炼出适合比赛的赛题场景

在计算机辅助设计(Computer    Aided  Design, 以下简称CAD)软件中,用户一般在模型空间绘制图形,在布局空间打印出图。由于工程图需要从不同角度综合反映工程模型的空间尺寸和几何关系,例如主视图、左侧图、俯视图、局部详图等。在打印出图时,需要输出模型空间所绘图形的不同视图。在CAD软件的布局空间中,可以将任意闭合区域作为裁剪边界(视口)输出图形,用户往往只关注视口内部的图形,所以需要裁剪掉视口区域以外的图形,即该题涉及的算法。

功能性需求

1)软件由一个可执行程序(.exe程序或其他扩展名)组成,画布大小为1440pixel*900pixel,通过读取xml文件(附件中提供示例)生成裁剪边界和被裁剪的图形,如下图所示:

2)软件提供一个Button用于执行“裁剪显示”操作(如上图所示),点击后统计裁剪显示所需要的时间,并统计图形复杂度,具体输出信息如下图所示:

注:Circle与多边形内切时,认为Circle位于边界内部;Circle与多边形外切时,认为Circle位于边界外部,此时不对交点进行计数。

3)任意line和circle,与凸多边形裁剪边界相交时能够正确裁剪显示(图形在裁剪边界外的部分不显示,在裁剪边界内的部分正确显示)

4)任意line和circle,与凹多边形裁剪边界相交并且跨凹多边形的优角时能够正确裁剪显示(图形在裁剪边界外的部分不显示,在裁剪边界内的部分正确显示)

非功能性需求

当有百万级的line和circle需要裁剪显示时,执行“裁剪显示”操作后,统计的完成裁剪显示的时间不超过10s,内存占用不超过100MB(PC配置见“其他要求”),在此基础上,时间和内存开销越小越好。

其他限制条件:开发环境、实验平台、开发语言、数据库、编译器等限制条件(请尽量明确)

1)能够运行于Windows XP和Window7等Win32平台

2)语言:C/C++、Java

3)开发环境:VC6/VS2003/VS2005/VS2008/VS2010/Eclipse任选

4)Java实现的程序用VisualVM_V1.3.5测试裁剪显示的内存占用,C++实现的程序用VMMap_V3.12测试裁剪显示的内存占用

测试数据或平台:提供给参赛者的测试环境和测试数据。(可提供电子档)

1)读入附件TestData1.xml中的TestCase-1生成图形和裁剪边界,测试Line在凸多边形边界中裁剪显示是否正确,得10分

2)读入附件TestData1.xml中的TestCase-2生成图形和裁剪边界,测试Circle在凸多边形边界中裁剪显示是否正确,得10分

3)读入附件TestData1.xml中的TestCase-3生成图形和裁剪边界,测试Line在凹多边形边界中裁剪显示是否正确,得15分

4)读入附件TestData1.xml中的TestCase-4生成图形和裁剪边界,测试Circle在凹多边形边界中裁剪显示是否正确,得15分

5)读入附件TestData2.xml生成海量(百万级)图形和裁剪边界,统计的裁剪显示的内存和时间开销若不能满足非功能性需求,该项得0分;否则以100分为基础,每占用1MB内存,扣1分;每耗时1秒,扣3分。扣分超过100分的,该项得0分。例如用时8.5秒内存开销55.4MB,则该项得分为100-8.5*3-55.4*1 = 19.1分。

注:

(1)此处所指的内存及时间开销仅针对点击“裁剪显示”按钮后统计,不包含加载文件阶段所占用的内存和时间,要求所有参赛选手的代码必须在点击“裁剪显示”按钮后开始执行。

(2)该赛题总分150分,功能正确性50分,效率100分,仅当功能正确时才计算效率考核得分。

开发所需设备及设备指标需求说明

附件:

1、源码框架

Demo_ClipView_VC.rar

Demo_ClipView_Java.rar

2、测试数据

GetTestData.rar

TestData1.xml

TestData2.xml

3、效率测试工具

VisualVM_1.3.5.rar

VMMap_3.12.rar

参赛队伍可以在中望软件网站上http://www.zwcad.com/community/thread-19767-1-1.html下载所有需要的附件

其他要求

1)PC配置:CPU I5-2320 3.GHz,内存4GB,硬盘250GB

2)不限制使用多线程技术

3)裁剪显示时可不考虑自交多边形边界的情况

4) 可以使用GDI的绘制接口来绘制图形,但不允许使用GDI的裁剪接口来实现裁剪功能

5)只能使用矢量计算方式进行裁剪,不得使用位图的像素处理变向达到裁剪显示效果

6)提供的TestData1.xml和TestData2.xml测试数据仅供测试、调试用,作品验收时不限于此二xml测试数据文件

7) 提交相关文档:

系统设计说明书:详细描述设计理念、算法思路等;

程序源代码:指未编译的按照一定的程序设计语言规范书写的程序代码,包括代码结构说明书;

可执行程序:编译好的二进制可执行程序。

 


关键字: 责任编辑:zhaoshuo
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到QQ空间
分享到: 
上一篇移动端无线WiFi侦测及位置分析软件 下一篇解密陌生人-移动社交应用

相关栏目