八叉树三维数据结构及示例程序

《八叉树三维数据结构及示例程序》由会员分享，可在线阅读，更多相关《八叉树三维数据结构及示例程序（19页珍藏版）》请在装配图网上搜索。

1、八叉树三维数据结构（一）基本原理用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80 年代后 才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以 认为是用三维体素阵列表示形体方法的一种改进。八叉树的逻辑结构如下：假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2 n,形体V C,它的八叉树可以用以下的递归方法来定义：八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果V = C,那么V 的八叉树仅有树根，如果VHC,则将C等分为八个子立方体，每个子立方体与树根的一个 子节点相对应。只要某个子立方体不是完全空白或完全为V所占

2、据，就要被八等分（图 2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点 所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小， 并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。图2-5-1某个子立方体被八等分如此所生成的八叉树上的节点可分为三类：灰节点，它对应的立方体部分地为V所占据；白节点，它所对应的立方体中无V的内容；黑节点，它所对应的立方体全为V所占据。后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的：它是一颗树，其上 的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其它

3、节点与C 的某个子立方体相对应。因为八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全 沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规的、线性 的、一对八的八叉树等等。另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存 贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的 主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算（例如可以 求两个物体的并、交、差等运算），而这些恰是其它表示方法比较难以处理或者需要耗费许 多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因

4、而对显示精度和速度的 平衡、隐线和隐面的消除等，带来了很大的方便，特别有用。（二）八叉树的存贮结构八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八 叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用 率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。1、规则八叉树规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段 用来描述该结点的特性（在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可）， 其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的 存贮结构方式。规

5、则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字 节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94。因此，这种方 法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2、线性八叉树 线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树（例如以 深度第一的方式），将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相 对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是 叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧 凑的方式来表示线性表，可以不用指针或者仅

6、用一个指针表示即可。R0(234.G HA 屁 C D E123.7CDEFGH树根韭叶结原其线性表为严吧02-5-2线性八旻树线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是丧失了 一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其 余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存 取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但 是仍很难令人满意。3、一对八式的八叉树一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6， 7。从上面的介绍可以看到，

7、如果一个记录与一个结点相对应，那么在这个记录中描述的是 这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而 且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的（例如， 该结点已是叶结点），那么相应的存贮位置也必须空闲在那里（图2-5-3），以保证不会错 误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所 有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。RECD0302-5-3 一对八式的八叉树012 S QG H能34.为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一

8、定的信息， 使计算工作适当减少或者更方便。栅格数据压缩存储方式之四叉树、八叉树编码 四叉树编码（quad-tree code）四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值 （ 或灰度） 。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则 还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值 或灰度为止。四叉树编码法有许多有趣的优点：容易而有效地计算多边形的数量特征；阵列各部 分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细 节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减

9、少存贮量；栅格到四叉 树及四叉树到简单栅格结构的转换比其它压缩方法容易;多边形中嵌套异类小多边形的表 示较方便。四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同 的四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓 “洞”这种结构存在，使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这 些压缩数据的方法应视图形的复杂情况合理选用，同时应在系统中备有相应的程序。另外， 用户的分析目的和分析方法也决定着压缩方法的选取。四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录 叶结点之外，还要记录中间结点。结点之间借助

10、指针联系，每个结点需要用六个量表达：四 个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存 量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰 度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结 点的位置和深度信息。最常用的地址码是四进制或十进制的Mor ton码。八叉树结构就是将空间区域不断地分解为八个同样大小的子区域（即将一个六面的立方 体再分解为八个相同大小的小立方体），分

11、解的次数越多，子区域就越小，一直到同区域 的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按定的分辨率将三维 空间划分为三维栅格网，然后按规定的顺序每次比较3 个相邻的栅格单元，如果其属性值相 同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位，即八个 指向子结点的指针，个指向父结点的指针和一个属性值（或标识号）。而线性八叉树则只需 要记录叶结点的地址码和属性值。因此，它的主要优点是，其一节省存储空间，因为只需对 叶结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到某一特定结 点的方

12、向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程 度；其次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码（称编 码），而不必实际建立八叉树，并且定位码本身就是坐标的另种形式，不必有意去存储坐 标值。若需要的话还能从定位码中获取其坐标值（称解码）；其三，在操作方面，所产生的定 位码容易存储和执行，容易实现象集合、相加等组合操作。八叉树主要用来解决地理信息系统中的三维问题。#include stdafx.h#include #include #include #include #include #include octree.h/*/*/*/Vec3

13、makeVec3( double x, double y, double z)Vec3 v3 = (Vec3) malloc(3 * sizeof(double);v30 = x; v31 = y; v32 = z;return v3;Vec3 copyVec3( Vec3 src )Vec3 v3 = (Vec3) malloc(3 * sizeof(double);v30 = src0; v31 = src1; v32 = src2;return v3;/* Octree* make_octree( Vec3 min, Vec3 max )/Octree* o = (Octree*) ma

14、lloc(sizeof(Octree);Octree* o = new Octree;o-min = copyVec3(min); o-max = copyVec3(max);o-children = 0; o-at_max_depth = 0;/*printf(creating octree %.3lf,%.3lf,%.3lf . %.3lf,%.3lf,%.3lfn, o-min2, o-min1, o-min0, o-max2, o-max1, o-max0 );*/return o;void subpoint( Octree* o,int oc,Vec3 min, Vec3 max)

15、pvex_nor *m_p1,*m_p2;POSITION pos1,pos2; for(pos1=o-vex.GetHeadPosition(),pos2=o-normal.GetHeadPosition();pos1!=NULL;) /pos1=o-vex.FindIndex(i);/pos2=o-normal.FindIndex(i);m_p1=(pvex_nor*)o-vex.GetNext(pos1);m_p2=(pvex_nor*)o-normal.GetNext(pos2); if(m_p1-xmin0&m_p1-xymin1&m_p1-yzmin2&m_p1-zchildren

16、oc-vex.AddHead(new pvex_nor(m_p1-x,m_p1-y,m_p1-z); o-childrenoc-normal.AddHead(new pvex_nor(m_p2-x,m_p2-y,m_p2-z);void split_octree( Octree* o )double oc_min3;double oc_max3;Vec3 mid = makeVec3( (o-min0 + o-max0) * 0.5,(o-min1 + o-max1) * 0.5,(o-min2 + o-max2) * 0.5 );int xp, yp, zp;int oc = 0;/o-ch

17、ildren = (Octree*) malloc( 8 * sizeof(Octree*);o-children = new Octree*;for(zp=0; zp min2;oc_max2 = mid2;elseoc_min2 = mid2;oc_max2 = o-max2;for(yp=0; yp min1; oc_max1 = mid1;elseoc_min1 = mid1; oc_max1 = o-max1;for(xp=0; xp min0; oc_max0 = mid0;elseoc_min0 = mid0; oc_max0 = o-max0;o-children (zp*4)

18、 + (yp*2) + xp = make_octree( oc_min, oc_max ); subpoint( o,(zp*4) + (yp*2) + xp,oc_min,oc_max); */* int recursively_evaluate_octree( int min_depth, int max_depth, int current_depth, Octree* o ) int deepest_child = current_depth;/int xp, yp, zp;int oc;int cd;/pvex_nor *m_p;/POSITION pos;/*Vec3 point

19、 = makeVec3(0,0,0);int p = 0; for(zp=0; zp min2 : o-max2;for(yp=0; yp min1 : o-max1;for(xp=0; xp min0 : o-max0;o-value p+ = evaluate_point( point,o);*/ o-density=evaluate1_point(o);current_depth+;o-not_fully_divided = (char) octree_needs_to_be_split( o );if( current_depth = max_depth )if( current_de

20、pth not_fully_divided )/if(deepest_child=current_depth|deepest_child=0)/split_octree( o );/ for(oc = 0; oc x,m_p-y,m_p-z);*/if(deepest_child=current_depth|deepest_child=0)/cd = recursively_evaluate_octree( min_depth, max_depth, current_depth, o-children oc );/if(cd deepest_child) deepest_child = cd;

21、else o-at_max_depth = 1;return deepest_child;/*/int subdivide_octree( int min_depth, int max_depth, Octree* o ) return recursively_evaluate_octree(min_depth, max_depth, 0, o ); double demo1( Vec3 pos ) /* demo 1: the surface is a sphere of radius 0.75 centered at 0,0,0function returns 1.0 if point i

22、nside sphere, 0.0 otherwise */double dist_sq = (pos0 * pos0) + (pos1 * pos1) + (pos2 * pos2);return ( dist_sq 0.5625 ) ? 1.0 : 0.0;double demo2( Vec3 pos )/* demo 2: the surface is two spheres,A: radius 0.25 centered at -.25,-.5,0and B: radius 0.5 centered at -0.5,0,0function returns 1.0 if point in

23、side sphere A, 2.0 for sphere B, 0.0 for neither*/double dist_sq_a = (pos0+.25) * (pos0+.25) + (pos1+.5) * (pos1+.5) + (pos2 * pos2);double dist_sq_b = (pos0+.8) * (pos0+.8) + (pos1 * pos1) + (pos2 * pos2);if( dist_sq_a = .0625 )return 1.0;if( dist_sq_b = .25 )return 2.0;return 0.0;double demo3( Vec

24、3 pos )/* demo 3: the surface is tiny sphere, radius 0.1 centered at -.5,.5,0function returns 1.0 if point inside sphere A, 0.0 otherwise*/double dist_sq = (pos0+.5) * (pos0+.5) + (pos1-.5) * (pos1-.5) + (pos2 * pos2);return ( dist_sq 0.01 ) ? 1.0 : 0.0;double demo4( Vec3 pos )/* demo 4: wavey surfa

25、cefunction returns 1.0 if point near surface , 0.0 otherwise*/double surface_height = sin( (pos0 * 3.0) ) * cos ( (pos1 * 3.0) );double distance_sq = (pos2 - surface_height) * (pos2 - surface_height);return ( distance_sq 0.01 ) ? 1.0 : 0.0;double demo5( Vec3 pos )/* demo 5: hemisphere, center 0,0,0

26、radius 0.5, cut by plane at z=0*/double abs_dist_sq = (pos0) * (pos0) + (pos1) * (pos1) + (pos2 * pos2);double surf_dist_sq = abs_dist_sq - 0.5625;if(surf_dist_sq 0) & (surf_dist_sq 0.1 )return 1.0;elsereturn .0;double demo6( Vec3 pos )/* demo 6: another wavey surfacefunction returns 1.0 if point ne

27、ar surface , 0.0 otherwise*/double surface_height = sin( (pos0 * 2.0) ) + sin ( (pos1 * 2.0) );double distance_sq = (pos2 - surface_height) * (pos2 - surface_height);return ( distance_sq 0.01 ) ? 1.0 : 0.0;double demo7( Vec3 pos )/* demo 7: a cylinderfunction returns 1.0 if point near surface , 0.0

28、otherwise*/double disc_dist_sq = (pos1) * (pos1) + (pos2 * pos2);double surf_dist_sq = disc_dist_sq - 0.5625;if(surf_dist_sq -0.75 ) & ( pos0 0.75 ) )if( surf_dist_sq 0.001) | (pos2 -0.001) return .0;zr = cr = (pos0 * 2.0);zi = ci = (pos1 * 2.0);while(it_count max_iters) & (inside) /* z = zA2 + c */

29、it_count+;new_zr = (zr*zr) - (zi*zi) + cr;new_zi = (2*zr*zi) + ci;zr = new_zr;zi = new_zi;inside = (zr * zr) + (zi * zi) (2.0 * 20);return (it_count = max_iters) ? 1.0 : 0.0;double demo9( Vec3 pos, Octree *o)pvex_nor *m_p1,*m_p2;POSITION po;double dis;double zx,zy,zz,tempx,tempy,tempz,temp;for(int i

30、=0;ivex.GetCount();i+)po=o-vex.FindIndex(i);m_p1=(pvex_nor *)o-vex.GetAt(po);m_p2=(pvex_nor *)o-normal.GetAt(po); tempx=pos0-m_p1-x;tempy=pos1-m_p1-y;tempz=pos2-m_p1-z; temp=tempx*m_p2-x+tempy*m_p2-y+tempz*m_p2-z;zx=m_p1-x-temp*m_p2-x;zy=m_p1-y-temp*m_p2-y;zz=m_p1-z-temp*m_p2-z; dis=sqrt(pos0-zx)*(p

31、os0-zx)+(pos1-zy)*(pos1-zy)+(pos2-zz)*(pos2-zz); /dis=sqrt(pos0-m_p1-x)*(pos0-m_p1-x)+(pos1-m_p1-y)*(pos1-m_p1-y) /+(pos2-m_p1-y)*(pos2-m_p1-y);if(dis0.1) goto loop;loop:return (disvex.GetCount()+1; return(tCnt);/*/* returns 1 if the octree should be split, 0 otherwise */*this implementation checks

32、whether all 8 corner values are the same(if any corner 1.7 is different to corner 0 then the function returns 1) */int octree_needs_to_be_split( Octree* o )/*int i;double v = o-value0;for(i=1; i valuei != v)return 1;/* if we got here, then all corners have the same value */return 0; if(o-density40)

33、return 1;else return 0;void isoface(Octree* o)char bf2;/CPtrList vexlist,norlist;float v1,v2,v3;ifstream file(ww9.obj);if(!o-vex.IsEmpty()o-vex.RemoveAll();if(!o-normal.IsEmpty()o-normal.RemoveAll();if(!file.fail()while(!file.eof() filebfv1v2v3; if(bf0=v&bf1=0)o-vex.AddTail(new pvex_nor(v1,v2,v3); i

34、f(bf0=v&bf1=n)o-normal.AddTail(new pvex_nor(v1,v2,v3); /o-vex=vexlist;file.close();/*Linearly interpolate the position where an isosurface cutsan edge between two vertices, each with their own scalar value*/Vec3 VertexInterp(double isolevel,Vec3 p1,Vec3 p2,double valp1,double valp2) double mu;Vec3 p

35、= makeVec3(0,0,0);if (fabs(isolevel-valp1) 0.00001) return(p1);if (fabs(isolevel-valp2) 0.00001) return(p2);if (fabs(valp1-valp2) 0.00001)return(p1);mu = (isolevel - valp1) / (valp2 - valp1);p0 = p10 + mu * (p20 - p10);p1 = p11 + mu * (p21 - p11);p2 = p12 + mu * (p22 - p12);return(p);/*Given a grid

36、cell and an isolevel, calculate the triangular facets required to represent the isosurface through the cell. Return the number of triangular facets, the array triangles will be loaded up with the vertices at most 5 triangular facets.0 will be returned if the grid cell is either totally aboveof total

37、ly below the isolevel.*/int Polygonise(GRIDCELL grid,double isolevel,TRIANGLE *triangles)int i,ntriang;int cubeindex;Vec3 vertlist12;int edgeTable256=0x0 , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49

38、f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 0x4

39、60, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c, 0xe5c, 0xf55, 0xc5f, 0x

40、d56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc , 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0

41、xf55, 0xe5c, 0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460, 0xca0,

42、0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596,

43、 0x29a, 0x393, 0x99 , 0x190, 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 ; int triTable25616 = -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, -1, -1

44、, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 8, 3, 2, 10,

45、8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1, 3, 10, 1, 11, 10, 3,

46、-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1, 3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1, 9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0, 7, 3, 4, -1,

47、 -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, 9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1,

48、 -1, -1, -1, -1, -1, 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1, 8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1, 9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1,

49、 3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1, 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1, 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1, 4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 5, 4,

50、0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1, 1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1, 5, 2, 10, 5, 4, 2, 4, 0

51、, 2, -1, -1, -1, -1, -1, -1, -1, 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1,9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1, 0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1

52、, -1, -1, 10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1, 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1, 5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, 9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 3,

53、 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1, 0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1, 1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1, 10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1, 8, 0, 2, 8, 2, 5, 8, 5, 7, 1

54、0, 5, 2, -1, -1, -1, -1, 2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, 7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1, 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1, 11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1,

55、9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1, 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1, 11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1, 11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 5, 10,

56、6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, 1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1, 9, 6, 5, 9, 0, 6, 0, 2, 6, -1

57、, -1, -1, -1, -1, -1, -1, 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1, 2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1,

58、-1, -1, 6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1, 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1, 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1, 6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1, 5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1, 1, 9, 0, 5, 10, 6,