二、    操作流程

    1．插入边


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



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

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




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

三、    图元显示
（。。。）
四、    数据保存
（。。。）

五、    核心算法

1．    搜索面SearchFace（）：
该函数为边的成员函数



参数：
从边搜索面，搜索方式分为两种：
前向和后向。例如：图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（）：
此函数是面的成员函数。
  

如图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
}

不懂，路过！

好帖，先mark,有时间详读。

高深！顶一个！

这样的回复是不对的，应该冷静下来仔细思考一下，有什么疑问什么的提出来，我不喜欢看到我的帖子后面都是捧场，而更希望的是批评！

同感。有时也存在另一种相反的回复。比如什么内容都没有，帖子后面都是BS。很不喜欢。

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

我欲实现两个多边形紧密贴合。怎么实现？