现在大家对烦(ch)引有?jin)感性认识，那什么是“I间索引“呢？”I间索引“也是”索引“Q是对空间图形集合做的一?#8221;目录“Q提高在q个囑Ş集合中查找某个图形对象的效率。比如说Q我们在一个地囑֛层上q行矩Ş选择Q确定这个图层上哪些囑օ被这个矩形所完全包含呢，在没?#8221;I间索引“的情况下Q我们会(x)把这个图层上的所有图元，一一拿来与这个矩形进行几何上的包含判断，以确定到底哪些图元被完全包含在这个矩形内。?zhn)是不是觉得这样做很合理呢Q其实不?dng)我们先看一个网格烦(ch)引的例子Q?/p>
我们对这个点囑ֱ作了(jin)|格索引Q判断哪些点在这个矩形选择框内Q是不需要把q个囑ֱ里所有的炚w要与矩Şq行几何包含q算的，只对a,b,c,d,e,f,gq七个点做了(jin)q算。可以推想一下，如果一个点囑ֱ有十万个点，不徏立空间烦(ch)引，M地图操作都将Ҏ(gu)个图层的所有图元遍历一ơ，也就是要For循环10万次Q徏立烦(ch)引将使得For循环的次C降很多很多，效率自然提高很多Q?/p>
呵呵…惛_大家都知道空间烦(ch)引的好处?jin)，也不知不觉向大家介绍了(jin)点囑ֱ的网格?ch)引，q有哪些常用的空间烦(ch)引呢Q这些空间烦(ch)引又该如何实现呢Q带着q样的问题，下面介绍几种常用的空间烦(ch)引?/p>
|格索引
|格索引是在一个地囑֛层上Q按每个网格宽△w,高△h打上均匀的格|，计算每个囑օ所占据的网格或者所l过的网格单元集合，
在这些网格单元中Q记录下囑օ对象的地址或者引用，比如Q声明一个对象二l数l?font face="Times New Roman"> List grid[m][n]; m代表|格的行敎ͼn代表|格的列敎ͼ每个数组元素Z?#8220;集合对象”Q用于存储这个网格单元所兌的所有图元的地址或引用，q样|格索引徏立好?jin)。下一步，我们该怎么用这个网格烦(ch)引呢Q?span style="font-size: 10.5pt">所有的囑Ş昄和操作都可以借助?#8220;I间索引”来提高效率。D几个例子来说?#8220;I间索引“的用：(x)
1Q确定所ȝ形左上角和右下角所在的|格数组元素Q即可得到这个矩形所兌覆盖的所有网格集合；
2Q遍历这个网格集合中的元素，取到每个|格元素List中所记录的图元；
3Q画?gu)些图元即可。（当然整个q程涉及(qing)C点：(x)1Q屏q坐标和地图坐标的互相变换；2Q窗口裁减，也可以不裁减Q?/p>
二?/font>包含判断Q给Z个点point和一个多边ŞpolygonQ判断点是否在面内，首先判断q个Ҏ(gu)在的|格Q是否同时关联这?font face="Times New Roman">polygonQ如果不是，表明点不在面内，如果是，可以下一步的_解析几何判断Q或者精度允许的情况下，卛_?font face="Times New Roman">polygon是包?font face="Times New Roman">point的?/p>
另外Q?font face="Times New Roman">Google Map应该也是采用地理|格的方式，对地囑֛象进行烦(ch)引的Q可见一斑，|格索引在图形显C，选择Q拓扑判断上的广泛应用。但同时也存在很严重的缺P(x)当被索引的图元对象是U，或者多边Ş的时候，存在索引的冗余，即一个线或者多边Ş的引用在多个|格中都有记录。随着冗余量的增大Q效率明显下降。所以，很多学者提Z(jin)各种Ҏ(gu)来改q网格烦(ch)引，q个在下面的章节中介绍。而点囑օ非常适合|格索引Q不存在冗余问题?/p>
四叉?wi)?ch)引（QuadtreeQ?/span>
cM于前面介l的|格索引,也是对地理空间进行网格划分，对地理空间递归q行四分来构建四叉树(wi)Q本文将在普通四叉树(wi)的基上，介绍一U改q的四叉?wi)?ch)引结构?span style="font-size: 10.5pt">首先Q先介绍一?/span>GISQ?/span>Geographic Information SystemQ或者计机囑Ş学上非常重要的概念—?span style="color: red">最外包矩?/span>(MBR-Minimum Bounding Rectangle)Q?/span>
最外包矩?/span>MBR是包围囑օQ且q?font face="Times New Roman">XQ?font face="Times New Roman">Y轴的最外接矩形?font face="Times New Roman">MBR到底有什么用处呢Qؓ(f)什么要引入q个概念呢？因ؓ(f)Q图元的形状是不规则的，?font face="Times New Roman">MBR是^行于XQ?font face="Times New Roman">Y轴的规则囑ŞQ设想一下，如果所有的囑օ都是q?font face="Times New Roman">XQ?font face="Times New Roman">Y轴的矩ŞQ那针对q样的矩形进行几何上的Q何判断，是不是要单很多呢Q不我们h自己写公式算法或者编写程序运行，是不是都要比原本复杂的图形几何运要z很多呢Q答案很昄?/p>
可见Q过滤阶D，通过I间索引可以排除掉一些明显不W合条g的图元，得到后选集合，然后对后选图元集合进行精几何运，得到最l结果。大家可能会(x)有这L(fng)疑问Q这h必要吗？是不是反而把问题复杂化了(jin)Q合适的I间索引只会(x)提高计算机的效率Q没有空间烦(ch)引，我们无疑要对集合中的每个囑օq行_几何q算Q而这L(fng)q算是复杂的Q是非常占用CPU的，所以需要空间烦(ch)引，采取量的内存和单的CUPq算Q来量减少那种高?font face="Times New Roman">CUP的精运的ơ数Q这样做是完全值得的。至于精的几何q算到底复杂在哪里，该如何进行精的几何q算Q将在下面的章节中详l描qͼq里主要介绍qo(h)阶段的空间烦(ch)引?/p>
四叉?wi)?ch)引就是递归地对地理I间q行四分Q直到自行设定的l止条gQ比如每个节点关联图元的个数不超q?font face="Times New Roman">3个，过3个，再四分Q，最lŞ成一颗有层次的四叉树(wi)。图中有数字标识的矩形是每个囑օ?font face="Times New Roman">MBRQ每个叶子节点存储了(jin)本区域所兌的图元标识列表和本区域地理范_(d)非叶子节点仅存储?jin)区域的地理范围。大家可以发玎ͼ同样存在一个图元标识被多个区域所兌Q相应地存储在多个叶子节点上Q比?#8220;6“所代表的图元，分别存储在四个分枝上。这P存在烦(ch)引的冗余Q与|格索引存在同样的弊端。下面我们介l一U改q的四叉?wi)?ch)引，或者说是分层的|格索引?/p>
可以看出Q?font face="Times New Roman">3?font face="Times New Roman">13分别都跨了(jin)两个区域Q要被一?span style="color: red">最区?span style="color: red">完全包含Q就只能是根节点所代表的区域，2Q?font face="Times New Roman">5跨越?jin)两个区域?font face="Times New Roman">6跨越?jin)四个区域，要被一?span style="color: red">最区?span style="color: red">完全包含Q就只能?/span>NW区域。怎么判断一个图元被哪个最区?span style="color: red">完全包含呢？从直观上看，递归地对地理I间q行四分Q如果图元与一个区域四分的划分U相交，则这个图元就归属于这个区域，或者直C再划分了(jin)Q那属于这个不再划分的区域。呵c(din)。。可能有点绕口，看图Q结?#8220;最?/span>”“完全包含”q两个字|(zhn)就明白?jin)。这颗四叉树(wi)中，囑օ的标识不再仅仅存储在叶子节点上，而是每个节点都有可能存储Q这样也避免了(jin)索引冗余。同时每个节点存储本节点所在的地理范围?/span> 有了(jin)四叉?wi)?ch)引，下面又该如何利用q颗?wi)来帮助(g)索查扑֑Q还是矩形选择Z吧！Qؓ(f)什么我L拿这个例子来说事呢？因ؓ(f)q个例子单，Ҏ(gu)理解Q有代表性！Q我们在地图上画一个矩形，判断地图上哪些图元落在这个矩形里或者和q个所ȝ形相交。方法很多，q里介绍一U简单的(g)索步骤，如下Q?/p>
1Q首先，从四叉树(wi)的根节点开始，把根节点所兌的图元标识都加到一?font face="Times New Roman">List里； 2Q比较此矩Ş范围与根节点的四个子节点Q或者叫子区域）(j)是否有交集（怺或者包含）(j)Q如果有Q则把相应的区域所兌的图元标识加?font face="Times New Roman">List集合中，如果没有Q则以下q颗子树(wi)都不再考虑?/p>
3Q以上过E的递归Q直到树(wi)的叶子节点终止，q回List?/p>
4Q从List集合中根据标识一一取出囑օQ先判断囑օMBR与矩形有无交集，如果有，则进行下面的_几何判断Q如果没有，则不再考虑此图元。（当然Q这里只说了(jin)一个基本思\Q其实还有其他一些不同的Ҏ(gu)Q比如，l合I间数据盘的物理存储会(x)有一些调_(d)(j) ȝQ改q的四叉?wi)?ch)引解决了(jin)U，面对象的索引冗余Q具有较好的性能Q而被大型I间数据库引擎所采用Q如ArcSDEQ?font face="Times New Roman">Oracle Spatial{，同时q种l构也适用于空间数据的盘索引Q配合空间排序聚c，Z分Ş?font face="Times New Roman">Hilbert法数据l织Q将在空间数据格式的定义中发挥重要作用?/p>
]]>
]]>
]]>
(2) if满出口条gthen
(3) 出口操作|
(4) d
(5) Wn层的准备性操作P(n)Q?br /> (6) Wn层具休性操作G(n)|
(7) q入探层递归前的恢复性操作H(n)Q?br /> (8) q入深层递归reeurslon(n一1)
(9) endif
(10)end sub
]]>
p = malloc(n * sizeof(int));
for (i = 0; i < n; i++)
p[i] = i;
output(p, n);
for (i = n - 1; i > 0; i--)
if (p[i] > p[i - 1])
{
for (j = n - 1; p[j] < p[i - 1]; j--);
swap(&(p[i - 1]), &(p[j]));
for (j = i, k = n - 1; j < k; j++, k--)
swap(&(p[j]), &(p[k]));
ouput(p, n);
i = n;
}
free(p);
]]>
]]>
首先Qg递是很好理解的。比如：(x)
public class test {
int a = 3;
public void plus(int b){
b = b+1;
}
public static void main(String args[])
{
test t = new test();
t.plus(t.a);
System.out.println(t.a);
}
}
输出的结果是3.q就是g递。其实我们可以这L(fng)解：(x)
在plus(int b)函数里，int b是作个函数的一个局部变量，在调用这个函数的时候开始位q个变量的内存空间。当我把变量a传给q个函数的时候，实际上是把a变量当时的值拷贝一个放到变量b的分配空间里Qb = b+1Q这句改变的只是函数的局部变量b的|当调用结束的时候，变量b的作用范围也q束了(jin)Q而你在什么时候修改了(jin)变量a的分配空间呢Q当然是没有啦（除非你理解成变量a的空间整个放qb的空间里:)Q?
而所谓的引用传递，我觉得这个名ơv的很h视听。以我自q理解Q一切传递都是拷贝传递。因为对象的标识W代表的是对象的存储地址Q所以你把对象的标识W号传递给函数的时候，实际上是把对象地址的拷贝传递给?jin)函数。虽然也是拷贝，但是2个地址拯都是指向一个地址的，所以如果在函数里修改了(jin)对象Q那么也实际上就修改?jin)原先的?
归根到底一句话QJava一切参数的传递都是拷贝传递！
]]>
]]>