五、    核心算法

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
}