[原创] 一种基于Mesh网格管理的通用2D矢量图形编辑工具解决方案
2007~2008年完成的一个算法,被该同事盗用了,
http://www.paper.edu.cn/index.php/default/releasepaper/downPaper/200902-1451
冒牌作者:黄洲,我要鄙视
一下先

本文是一个中长篇算法连载,研究图论在区域搜索算法中的应用;
而算法基于伪代码方式提供,清晰,易懂,其实原算法是基于C++开发,后来为了在其他平台语言开发特地的写出伪代码方式。

关于这个算法的说明简要:
原先写出该算法是为了解决一个区域智能识别的一个接口使用。后期开发遇到CorelDraw矢量图形软件开发需求,对算法进一步完善,效率,速度,资源占用率,如今过去了3年,算法的保密期已过,我共享出来,这个作为商业化应用的算法第一个版本,供大家学习,研究使用。
当然还有第二个版本,我在2009年整体优化,高速的识别任意复杂浮点坐标系的区域速度控制在毫秒级。由于保密协议在,就不方便透露了。但是整体思想还是一样,基于Graph算法!


  引言  
现代计算机图形编辑软件,能够给用户提供一种编辑位图的接口,使用户能方便直观地编辑各种图元,但又能以矢量方式来存储这些图元,以降低存储器的使用开销。本文所描述的解决方案,就能够支持以上两种特性。


一、    基本图元的概念
1.    节点[blockquote] 1.jpg [/blockquote]

1>    节点坐标:x,y
2>    其中保存了与该节点相连的边集,且该节点上的边,是按以节点为中心,逆时针方向排序。
如图1-1所示,节点A中保存了边1、边2、边3,且它们是以点A为中心,逆时针方向排序(以3点钟方向为最小)的,第一条边是边1,第二条是边2, 第三条边是边3。
3>    访问次数,在遍历网格的时候作访问计数之用。初始值为0,最大值为节点上的边数。
2.    
[blockquote] 2.jpg [/blockquote]

1>    其中保存了边的起始点,终止点。例如图2中的边EF,它的起始点是E,终止点是F。
2>    附加到边中的线段。可以是曲线,也可以是直线。例如:边AB中附加的是曲线段,而边EF中附加的线段是直线段。
3>    左、右面。一条边有一个方向,从起点指向终点。想像一个人,站在边的起点,面向边终点张开双臂,左手所在区域就是左面,右手所在区域就是右面。
如图2所示,边JE的左面是黄色区域,右面是红色区域。又如,边GJ的左面是黄色区域,右面是蓝色区域。边AB的左面是红色区域,右面区域为空。
        4> 边属性,目前只定义了边颜色。
3.    路径
[blockquote]   3.jpg [/blockquote]

它是遍历节点和边的结果,故而路径由边及路径的方向组成(即路径由路径边组成),且这些边必须是首尾相连。
如图1-3所示, 已知这些节点和边, 根据一定的遍历方式,此图有ABCFG、CDE两条路径。蓝虚线为路径ABCFG的方向,红虚线为路径CDE的方向。

4.    路径边
在路径的定义中,已经给出了路径边的定义:
路径边里包含边和路径的方向。如图3所示,路径ABCFG由边AB、BC、CF、FG组成,其中,边CF与已有边FC方向相反,故而路径边中会记录该边是否与路径方向相反。
5.    
1> 面继承了路径的所有属性,因此它也是路径,不同的是,它是闭合的路径。
2> 面是递归定义的,它可能有多个子面,也可能有一个父面
3> 面属性,目前只定义了面填充色。
如图1-2所示,红色面由边AB、BC、CD、DA构成,它没有父面,但有黄色和蓝色两个子面,
6.    网格(Mesh)
网格是管理节点、边、面以及边属性、面属性的对象,从数据结构来看,它仅仅直接保存了所有节点、边属性表、面属性表。通过节点,访问边,通过边访问面。
+1  学术分    novakon   2010-12-03   极优秀原创
来自:计算机科学 / 软件综合
 
2010-12-3 16:03:27
joyeep(作者)
1楼
二、    操作流程

    1.插入边

4.jpg
1>    将Mesh里的边集与插入边集求交
如图所示:紫色线段LR插入Mesh中,与Mesh中的边AB、JE、GJ、IH、CD、DK分别交于节点M、N、O、P、Q 、R,将这些节点和节点L、S放进Mesh的节点表中。
2>    获取Mesh中被交到的边,分割它们, 将它们用分割后的子边替换
例如:将AB分割成AM和MB,然后将边AB分别从节点A和B的边表中移除,再将AM加进节点A的边表,AM和MB加进节点M的边表,MB加进节点B的边表。同时将AM和MB的边属性也设置成AB的。
3>    分割插入的线段,并将线段转成边,加进Mesh
如图所示:将LR分割成线段LM、MN、NO、OP、PQ、QR、RS,根据这些线段,生成对应的边,再将线段附加进边里,最后把这些边,加进各对应节点的边表中。
4>    搜索并处理新形成的面
遍历每个插入边,按插入边方向搜索面,判断环的时针顺序,若搜索结果为顺时针面,则处理新面的面属性、构成边的内外面、父子关系,若为逆时针面,则将该面分成小面,再处理面属性、构成边的内外面、父子关系。
如图所示:
按插入边方向搜索面:以边LM为入边,访问节点M,逆时针获取下一条边MB。发现边MB的左面存在红色面,且当前搜索该面的顺序是逆时针顺序,那么将红色面AMBCQDA分割成小面:ADQPIJNMA、QCBMNEFGHPQ、NJON、JIPOJ、PHGOP、GFENOG

5.jpg

设置每个小面的面属性及构成边的内面:例如面NJON,它有3条边: JN、NO、OJ,其中JN和OJ的左面为旧面(黄色面EFJG),NO为新插入边,它的左面为空,故而将新面NJON设置为它3条边的左面,并且将旧面EFJG的属性赋予新面NJON。

设置每个小面构成边的外面:
JN的右面为红色旧面ABCQDA,它为被分割面。如果它真被分割,JN的右面将是ABCQDA被分割后小面的内面,可以等到设置小面内面时设置;而如果它未被分割,则JN的右面应该保持不变,所以此时不应该改变JN的右面。
OJ的右面为蓝色旧面JGHIJ (即新面NJON的外面),对蓝色旧面而言,边OJ的右面是它的内面,所以无论蓝色面是否被分割,OJ右面都是蓝色面(或分割成的小面)的内面,在设置蓝色面或分割后小面的内面时,都会处理。故而不用处理。
        NO为新插入边,它的左面已经被设置成新面,表示该边分割了黄色旧面,所以它的右面必为被分割的黄色旧面后生成的另一新面GFENOG的内面。故也可以等到设置GFENOG内面时再处理。

设置每个小面的父子关系:
        如果被分割面ABCQDA有父面ParentFace,则将其子面的父面设为ParentFace,此时将被分割面从ParentFace的子面表中移除,然后将分割后的子面放入ParentFace的子面表。

    2.删除边 6.jpg

如图2-2所示:
删除边有两种情况,
1>    将边JE删除
判断JE的内面,若有将内面(JE有内面JEFGJ)所有边的内面设置成空。
判断JE的外面,如果是父面(JE有父面ABCDA),将JE内面从其父面的子面表中移除,并将JE内面JEFGJ的所有非公共边的外面设置成空。
2>    将边GJ删除
判断GJ的内面,若有,则任选一内面(JE有内面JGHIJ),并将所有边的内外面设置成空。
判断GJ的外面,如果是兄弟面(GJ有兄弟面JEFGJ),将GJ外面(黄色兄弟面JEFGJ)从其父面的子面表中移除,并将GJ外面JEFGJ的所有非公共边的外面设置成空
            
        如果判断一个边的外面是父面还是兄弟面,如果是兄弟面,则此边一定在兄弟面内
而如果是父面,则此边一定不在父面中。
公共边的意思是说,该边的左右两个面是兄弟面,而非公共边就是该边的左右面不为兄弟面,可能左右面都为空,可能一个面不为空,另一个为空,或者都存在,但它们是父子关系。
    3.选择面


7.jpg

如图2-3所示:用户在虚线所示射线起点位置pt点了一下,此时应该选择出面EFGJE。那么,
2.    从pt点引一条水平向左的射线,将射线与已经存在的Mesh中的边求交,交点如图粉红色点1、2、3所示,
3.    并将交点按离pt的近远从小到大排序,排序后被交到的边依次为:GK、EF、BC。
4.    找出其中一个合格的最近的边,并获取该边的绝对右面。所谓合格,是指该边左右两面至少有一面不为空。所以GK不合格,而EF的两面都不为空,所以EF为合格边。(通过边的左右面情况确定边是否合格)
5.    获取EF的绝对右面,本来EF的右面是红色面,但它的左面相对于屏幕而言,是在右方,所以黄色面为边EF的绝对右面,故而黄色面EFGJE被选中。(为什么要用绝对右面)

4.    选择边
选择边或者点时,都会有一个允许的误差范围,本文中,把它定义为一个正方形rt,在构建网格时,作为参数传入,并且可以在构建后修改。
1.    将rt的中心移到测试点上
2.    将rt与Mesh中的边求交,找出相交边
3.    找出与测试点最近的相交边,即相交边上的交点与测试点的距离最短,该边就为选中边。
5.    选择点1.    将rt的中心点移到测试点上。
2.    在Mesh中找出在rt之内,并离测试点最近的节点,该节点即为选中点。 6.jpg
折叠评论
加载评论中,请稍候...
折叠评论
2010-12-3 16:16:47
joyeep(作者)
2楼
三、    图元显示
(。。。)
四、    数据保存
(。。。)
折叠评论
加载评论中,请稍候...
折叠评论
joyeep(作者)
3楼
3.jpg 五、    核心算法

1.    搜索面SearchFace():
该函数为边的成员函数

1.jpg

参数:
从边搜索面,搜索方式分为两种:
前向和后向。例如:图5-1中,边LM前向搜索,是以节点M为起点,LM为
入度,获取下一条边的。本例中,若按逆时针顺序访问节点M,获取的是边MB。
是否考虑已存在的旧面。例如:从边MN前向搜索,从节点N逆时针获取的边是NE,那么当前访问的边是NE,获取当前搜索方向的右面,本例中当前搜索方向与NE一致,故当前搜索方向右面就是NE的右面(红色面),若不一致,则获取NE的左面(黄色面)。获取的面就是已存在的旧面,如果考虑旧面,且该旧面不为空,则直接返回该旧面。否则继续搜索,直到找到闭环、或所有边均被访问。
搜索结果有两种方式输出:
1>    只要搜到一个顺时针面,从该搜索函数返回顺时针面,函数返回。
2>    搜到逆时针面,放进搜索函数的传出参数 面表 中,继续搜索。

用到的临时数据结构:
访问过的边,        每条边还附加了是否与访问方向一致的信息(即当前搜索方向)
访问过的边表,    是一个栈,将访问过的边按顺序保存在里面。
当前搜索状态,    是前进,还是后退。在访问某个节点获取下条边时,若可以获取到,则当前状态为前进,获取不到,则状态为后退。

当前边、当前节点, 下条边、下个节点,搜索时,以当前边为入边,访问当前节点,
获取节点的某个时针方向的下条边。下个节点是下条边上不为当前节点的节点。
例如:当前边为LM,当前节点为M,逆时针获取的下条边为MB。MB上不为当
前点M的节点是B,所以下个节点就是B。

        搜索起点、搜索终点,若为前向搜索,搜索起点是本边的终点,搜索终点是本边的
起点,否则相反。例如:从边LM前向搜索,搜索起点为M,终点为L。


流程:
1>    初始化搜索,当前边为自己,若前向搜索,当前节点为当前边的终点,否则为起点。例如:起始搜索边为LM,前向搜索,当前边是LM,当前节点为M。
2>    获取当前边的旧面(搜索方向的右面),若考虑旧面,且旧面不为空,则返回。例如:当前边为LM,搜索方向与LM的方向一致,若考虑旧面,LM的右面为空。
3>    当前搜索状态 = 前进,将当前边设为已访问,将搜索终点的访问次数加1。并将当前边压进已访问边表。例如:当前边为LM,将LM设为已访问,将L的访问次数加1,将LM放进已访问边表。
do{
    3> 若当前节点等于搜索终点,有两种可能,如果当前搜索状态为前进,
表示找到了一个面; 否则为后退,表示退到了起始搜索边,都没有找出面,它们之间在访问过的边表上表现为,前者已访问边表不为空,后者为空。例如:从EF开始搜索,搜索终点为E,经过几次访问后,当前边为NE,当前节点为E,它与搜索终点相同,且当前搜索状态为前进,那么表示找到了一个面,且已访问边表不为空。
break
    4> 以当前节点为起点,在已访问边表中搜索是否有节点跟当前节点相
同,若相同,表明广义找到了一个面(起始搜索边不在闭环上),则
创建一个面,将已访问边表中的边放进面里。然后判断该闭环的时针
顺序,若为顺时针,返回该面,否则放进面表中。例如:从边LM开始
搜索,经过几次访问后,当前边为AM,当前节点为M,那么此时已
访问边表里有边MB、BC、CQ、QD、DA、AM,搜索找边MB的
节点M与当前节点相同,则创建一个面,将MB、BC、CQ、QD、
DA、AM放进该面里,再判断该面的时针顺序,若为顺时针,则将
边表按逆时针存储,返回该面,否则如果是在插入边的话,就直接返
回,若不是则放进面表中。
                5> 下条边 = 以当前边为入边,访问当前节点,逆时针获取下一条未被
访问过的边。例如:当前边为LM,当前节点为M,已LM为入边,
逆时针找出下条边MB,且MB未被访问过,那么下条边就是MB,
否则下条边为空。
                    if(下条边不为空)
{
    判断下条边的方向是否和搜索方向一致(即下条边的终点是否不
等于当前节点)。例如:当前节点为M,下条边为MB,其终点
为B,它不等于当前节点M,那么当前节点 = B。

获取下条边的旧面(搜索方向的右面),若考虑旧面,且旧面不
为空,则返回。例如:同2>

当前边 = 下条边
当前节点 = 下条边上不为当前节点的节点

将当前边压入已访问过的边表
}
else
{
    如果已访问边表为空,无边可选,返回0。
    否则,当前边 = 边表最后一条边,当前节点 = 等于边表最后
一条边上不为当前节点的节点。
当前搜索状态为后退
将最后一条边从边表中弹出。
例如:从LM开始前向搜索,经过LM、MB、BC、CQ、QR、
RK,节点K只有一条边,并且就是从RK进来的(已访问),那
么从K点获取下条边就只能为空,但已访问边表中有LM、MB、
BC、CQ、QR、RK这些边(不为空),那么当前边 = RK,当前
节点 = R,将搜索状态设为后退,最后将RK从已访问边表中弹
出。

}
}while(true)

if(已访问边表不为空)
{
创建一个面,将已访问边表中的边放进面里。然后判断该闭环的时针
顺序,若为顺时针,将该面中的边按逆时针存储,返回该面。否则放进面表中,
返回空。例子同4>
}
返回空

2.    判断面的时针顺序ClockOrder():
此函数是面的成员函数。
   2.jpg

如图5-2所示,若搜出的蓝色面JGHI里,边的顺序依次为:JG、GH、HI、IJ
找出节点中最高的那一点,J(也可以是I),
1> 在J中插入一条竖直边XJ(虚线所示)。
2> 以XJ为入边,逆时针获取节点J的下条边为JG。
3> 在蓝色面的边表里,找出节点J的前一条边IJ,下一条边JG
4> 逆时针从最高节点J获取的下一条边和边表里该节点的下条边相同,则当前环
为逆时针。
        如果蓝色面里边的顺序依次为:JI、IH、HG、GJ,同样找出最高节点为J,插入竖
直边XJ,逆时针获取的下条边为GJ,但在蓝色面的边表里,找出节点J的下一条
边为JI,它与GJ不相同,所以当前环为顺时针。

3.    分割大面SplitIntoSmallFaces():

该函数为面的成员函数
如图5-3所示,将面AMBCDA分割成小面。
1>    将面AMBCDA中的边AM、MB、BC、CQ、QD、DA全加进当前轮廓(它是一个边表)
2>    nBigFaceEdges = 当前轮廓.size() = 6, nDiscardedEdges = 0
while(轮廓边表不为空)
{
        前路径边 = 轮廓边表.front()
        if(路径边访问过)    continue;
3>    因为所有的面都是按逆时针顺序存储的,所以,按顺时针顺序(与逆时针顺序反向)就能搜索出小面。本例中,如果当前路径边为AM,则以AM为起始搜索边,反向搜索,将搜出AM、DA、QD、PQ、IP、JI、NJ、MN被设为已访问,它们所组成的面ADQPIJNMA,一定是顺时针的。
4>    重构轮廓, 即将搜出的小面ADQPIJNMA剥离出轮廓。
遍历轮廓中每条边,若被访问过,则将其从轮廓中移除,并设为未访问。本例中,当前轮廓为:AM、MB、BC、CQ、QD、DA,被设为未访问且被移除的边为AM、DA、QD、
遍历小面中的边,将已访问过的边设为未访问,并加入到外轮廓中,将未访问的边设成已访问。本例中:组成小面的边为AM、DA、QD、PQ、IP、JI、NJ、MN,其中AM、DA、QD被标记为未访问,将它们再设成已访问,剩下的PQ、IP、JI、NJ、MN是已访问过的,将它们设置成未访问,并按顺序加到轮廓边表的尾部。此时,轮廓边表为MB、BC、CQ、PQ、IP、JI、NJ、MN
}
折叠评论
加载评论中,请稍候...
折叠评论
4楼
不懂,路过!
折叠评论
加载评论中,请稍候...
折叠评论
5楼
好帖,先mark,有时间详读。
折叠评论
加载评论中,请稍候...
折叠评论
2010-12-08 23:43:19
2010-12-8 23:43:19
6楼
高深!顶一个!
折叠评论
加载评论中,请稍候...
折叠评论
2010-12-23 21:29:08
2010-12-23 21:29:08
joyeep(作者)
7楼
回 6楼(dingdingyyo) 的帖子
这样的回复是不对的,应该冷静下来仔细思考一下,有什么疑问什么的提出来,我不喜欢看到我的帖子后面都是捧场,而更希望的是批评!
折叠评论
加载评论中,请稍候...
折叠评论
dctyu
8楼
回 7楼(joyeep) 的帖子
同感。有时也存在另一种相反的回复。比如什么内容都没有,帖子后面都是BS。很不喜欢。

亟待高手讲讲多边形的碰撞检测。和碰撞后的行为。

我欲实现两个多边形紧密贴合。怎么实现?
折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

joyeep
学者 笔友
文章
88
回复
564
学术分
8
2009/05/25注册,3 年前活动
暂无简介
插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
插入表情
我的表情
共享表情
Emoji
上传
注意事项
最大尺寸100px,超过会被压缩。为保证效果,建议上传前自行处理。
建议上传自己DIY的表情,严禁上传侵权内容。
点击重试等待上传{{s.progress}}%处理中...已上传
空空如也~
草稿箱
加载中...
此处只插入正文,如果要使用草稿中的其余内容,请点击继续创作。
{{fromNow(d.toc)}}
{{getDraftInfo(d)}}
标题:{{d.t}}
内容:{{d.c}}
继续创作
删除插入插入
{{forum.displayName}}
{{forum.countThreads}}
篇文章,
{{forum.countPosts}}
条回复
{{forum.description || "暂无简介"}}
ID: {{user.uid}}
学术分隐藏
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png