二叉树代码我写得很乱！！！整理一下思路

从初始话开始，一个是构造，一个是更新：

 

原来的意思是没有分割。。。但是：

 

     由于总的三角形的数量在分割过程中不断地更新，因此要不断地去构造新的三角形列表。因此所有的LIST必须保存真实的。而不能仅仅保存一个索引！！！

 

先说怎么构造：

 

1. 

   //这个可以写一个函数用来筛选！

   得到三角形列表，和已经用过的平面列表，构造备用分割面列表；

   //首先，从中剔除相同的面。思路是：

   for each  i in sanjiaoxing{

      //检查是否已经存在

      bool InUse=false;

       for each j in  BeiyongDividList 

       {

             if(已经存在)

              {

                    InUse=true；break;

              }

       }    

      for each j in  DividList 

       {

             if(已经存在)

              {

                    InUse=true；break;

              }

       }     

      //在这里根据INUSE的值来确定是否ADD

      if(!InUse)DividList.add(i);

  }

 

 

2。从备用的LIST里面选择一个最佳的的分割面，这个分割面可以用来分割所有的三角形集合。

 

     把这个分割面加到已经用过的分割面列表里。

 

3. 用最佳的分割面来分割所有的三角形集合为前集合，和后集合。

 

   

   

节点组成： 一个分割面。

叶子组成： 一组面的集合。

 

如果把这两个结合起来，那就是：

 

 

class Node {

   bool IsLeaf;

   DivideFlat flat；

   Pologons plos;

};

 

 

二：更新：

 

   1.节点获得三角形列表

   2.如果这个节点是节点：

         {

             利用分割面分割这些三角形列表。

             调用子节点的更新（方法）。也就是递归调用。

         } 

   3.如果是叶子。我们把这个三角形表加到自身的三角形表里面。调用自身的创建方法。

三。两者结合：

算法：

   0.初始化根节点为叶子。没有分割面，没有多变形列表。

   1.节点通过函数参数获得三角形列表。

   2.如果是叶子，我们把这个三角形表加到自身的三角形表里面，从中选择最好的分割面。       

   3.如果找不到，函数返回。

   4.如果找到了，分割三角形列表。把自己提升为节点，同时，设置子节点为叶子，把三角形列表传给子节点的本函数。转1.

   5.如果不是叶子，利用已经存在的分割面来分割此三角形列表。调用子节点的本函数。转1.

四。附加数据：

   一个是已用的三角形列表。。。这个应该是每棵树一个。。

   一个是备用的分割面列表。。。这个只有是叶子的时候才会起作用，而且是局部变量。  

 

五。我也在想这样一个问题：

 

      如果说，一开始对所有的三角形，按照所在平面进行分类，每一个或者更多三角形对应于平面列表中的某一个索引。

 

      也就是说创建一个List数组，来将三角形本身的数组索引与平面索引对应起来。。。。

    

      如果这样做：

           一个是平面的管理：只需要添加，坚决不能删除。

           一个是三角形的管理：不允许删除，只能添加或者更新。

七。因此：

        作为一个 BSP 树，我们需要如下的数据：一个三个LIst：

         class BSPTREE

        {

            NODE* root;

            LIST　TriangleList;

　　　　ＬＩＳＴ　ＭＡＰＬＩＳＴ；／／它的大小跟三角形数量一样多。

　　　　ＬＩＳＴ pingmianLIST；

　　　　ｂｏｏｌ　ＩＮＵＳＥＬＩＳＴ；／／它的大小跟ｐｉｎｇＭＩＡＮＬＩＳＴ一样。

        }

    而NODE中，仅仅需要保存的是这些索引。

 

八。构造与更新树：

 

      需要用一个三角形列表来构造，同时构造三个list，然后，根据这三个LIST来构造我们的节点。

 

      如果是叶子，则保留的是自身的三角形索引数组。。

 

      如果是节点，则保留的是平面的索引。

 

     class NODE{

　　　　　bool ＩＳＬＥＡＦ；

     　　　int Triangles_ｉｎｄｅｘ[n];

     　　　int flat_INDEX ;  

     }

 

　　这样的好处是，如果我们如果我们找到一个分割面，我们可以直接检查这个平面是否已经被使用作为分割面。

 

九。如果把４个ＬＩＳＴ给封装起来，提供增，删，改，查四种操作，这将是一个更加不错的注意：

 

　　class　Ａ｛

　　ｐｒｉｖａｔｅ：

　　　　LIST　TriangleList;

　　　　ＬＩＳＴ　ＭＡＰＬＩＳＴ；／／它的大小跟三角形数量一样多。

　　　　ＬＩＳＴ pingmianLIST；

　　　　ｂｏｏｌ　ＩＮＵＳＥＬＩＳＴ；／／它的大小跟ｐｉｎｇＭＩＡＮＬＩＳＴ一样。　

　　｝

十。我们提供这样一些接口：

 

　　　　ｂｏｏｌ　ＡｄｄＴｒｉａｎｇｌｅ（Ｔｒｉａｎｇｌｅ）；

 

　　　　ｂｏｏｌ　ＵｐｄａｔｅＴｒｉａｎｇｌｅ（ｉｎｄｅｘ，Ｔｒｉａｎｇｌｅ）；

 

　　　　Ｔｒｉａｎｇｌｅ　ＧｅｔＴｒｉａｎｇｌｅ（ｉｎｄｅｘ）；  

 

　　　　Ｆｌａｔ　ＧｅｔＦｌａｔ（ｉｎｔ　ｉｎｄｅｘ）； 

 

　　　　ｉｎｔ　ＧｅｔＴｒｉａｎｇｌｅＦｌａｔ（ｉｎｔ　ｉｎｄｅｘ）；

　　　　

　　　　ｂｏｏｌ　ＡｄｄＦｌａｔ（ｆｌａｔ　ｆａｌｔ）；

　　　

　　　　ｂｏｏｌ　ＩｓＴｒｉａｎｇｌｅＵｓｅｄＡｓＦＬＩＰ（ｉｎｄｅｘ）；

 

　　　　ｂｏｏｌ　ＩｓＦｌａｔＵｓｅｄＡｓＦＬＩＰ（ｉｎｄｅｘ）；

 

　　　　ＵｓｅＴｒｉａｎｇｌｅＡｓＦｌｉｐ（ｉｎｔ　ｉｎｄｅｘ）；

　　　　

　　　　ＵｓｅＦｌａｔＡｓＦｌｉｐ（ｉｎｔ　ｉｎｄｅｘ）；

 

　　　　ＧｅｔＮｏｔＵｓｅｄＦＬｉｐＬｉｓｔ（）；

 

十一。这样的话，可以直接得到可用的分割面列表。仅仅需要做的是：

 

　　　　ＧｅｔＴｈｅＢｅｓｔＦｌｉｐ（ｉｎｔ　Ｔｒｉａｎｇｌｅｓ【】）；

 

　　　　int  ＤｉｖｉｄＴｒｉａｎｇｌｅＢｙＦｌａｔ（ｉｎｔ　Ｔｒｉａｎｇｌｅ，ｉｎｔ Flat，int *index）；

 

            int IsInFrontOrBackOrDividedByFlat(int Triangl,int flat );

 

十二。一切。。。的一切。。行动中，