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

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

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


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


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

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

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

100452

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

100453


设置每个小面的面属性及构成边的内面:例如面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.删除边 100455


如图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.选择面


100456


如图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之内,并离测试点最近的节点,该节点即为选中点。100454

折叠评论
加载评论中,请稍候...
折叠评论
joyeep(作者)
2楼
三、    图元显示
(。。。)
四、    数据保存
(。。。)
折叠评论
加载评论中,请稍候...
折叠评论
joyeep(作者)
3楼
100459
五、    核心算法

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

100457


参数:
从边搜索面,搜索方式分为两种:
前向和后向。例如:图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():
此函数是面的成员函数。
  100458


如图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-8 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) 的帖子
这样的回复是不对的,应该冷静下来仔细思考一下,有什么疑问什么的提出来,我不喜欢看到我的帖子后面都是捧场,而更希望的是批评!
折叠评论
加载评论中,请稍候...
折叠评论
8楼
回 7楼(joyeep) 的帖子
同感。有时也存在另一种相反的回复。比如什么内容都没有,帖子后面都是BS。很不喜欢。

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

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

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

{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png