毕设这两天飞一般的加速，终于可以写写源码解析了，嘿嘿，这周读两个跟性能相关的源码，首先是一个跟地图相关的，今天来看看一个数据结构在iOS开发中的妙用。
TBAnnotationClustering
我们都知道，MapView的实现机制其实和UITableView类似，首先他们都是基于UIScrollView支持滑动的，此外，他们都采用了循环服用的机制了来保持内存的开销。
但是，两者之间有个很大的区别就是数量级的差距，UITableView就算充满整个屏幕，充其量也就是10多个同时可见的VisibleCell，因此就多维护一个大小是VisibleCells数量 ＋ 2的这样一个循环队列，进行复用。但是MapView就不一样了，地图上同时展示一段范围内几千个Point of Interest是非常有可能的，这一下子的内存开销和性能卡顿就非常不得了，因此我们需要一种合理的手段来避免，这就是我们今天要讲解的TBAnnotationClustering的由来。
Github地址
Level of Detail
首先，让我们先介绍一下相关背景知识。
根据图像渲染的理论我们可以知道，人的视野存在焦点区域和盲点区域，总是更倾向于关注处于视线左上角到视线中心部分的。因此，在现实应用中，如游戏场景，当场景需要展现的模型距离视线焦点非常近时，就采用高精度的模型来进行展示；而到模型处于较远位置时，比如体育游戏的场外观众，就可以采用低精度模型进行替换，减少渲染时候的计算量；而到模型所处位置基本可以考虑成为背景时，则会采用基本图元进行展示。通过这种方法，即保证了场景的真实观感，同时又大大减少了不必要的计算量。这也就是通常计算机图形学领域所谓的Level Of Detail技术。
QuadTree
QuadTree可能很多人会比较陌生，但是一提到他的哥哥 － 二叉树，想必大家不会陌生，所以QuadTree又被称为四叉树，关于四叉树的定义，
A quadtree is a tree data structure in which each internal node has exactly four children.
四叉树被广泛的运用于空间划分。通过将空间递归划分不同层次的子结构，可以达到较高的空间数据插入和查询效果。
下面就是一张比较经典的四叉树构造，首先先将一个大空间划分为四个字空间 a b c d。然后根据每一个子空间内的节点个数再进行细分。这里要强调一点，四叉树的细分没有具体要求，你可以按你的需求划分成每个节点能只包含一个，也可以根据平衡减少划分次数。
TBAnnotationClustering源码讲解
打开这个项目，粗略过一下项目结构，大致需要关注的代码如下：
- TBQuadTree.h/.m
- TBCoordinateQuadTree.h/.m
让我们一个个来分析
TBQuadTree
毫无疑问，从文件名称来看，我们就知道，这个类就代表基础的四叉树数据结构，首先让我们来看看数据结构的定义
typedef struct TBQuadTreeNodeData {
double x;
double y;
void* data;
} TBQuadTreeNodeData;
TBQuadTreeNodeData TBQuadTreeNodeDataMake(double x, double y, void* data);
这个毫无疑问，就是代表的坐标系的数据节点。 (x, y)表征坐标点，void *data自由的指向附加的数据。
typedef struct TBBoundingBox {
double x0; double y0;
double xf; double yf;
} TBBoundingBox;
TBBoundingBox TBBoundingBoxMake(double x0, double y0, double xf, double yf);
这个同样很简单，用两个对角点限定了一个长方形区域，也就是一个四叉树的节点究竟包含哪些范围。
typedef struct quadTreeNode {
struct quadTreeNode* northWest
struct quadTreeNode* northEast
struct quadTreeNode* southWest
struct quadTreeNode* southEast
TBBoundingBox boundingBox;
int bucketCapacity;
TBQuadTreeNodeData *points
int count
} TBQuadTreeNode
TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity);
这个稍微复杂点，是四叉树的树节点，其中
- northWest, northEast, southWest, southEast分别代表四叉树的四个子细分区域。
- bondingBox代表的当前这个树节点的涵盖区域。
- bucketCapacity表示这个树节点最大容纳的数据节点个数
- points 数据节点数组
- count 当前包含了数据节点。
再次强调，千万不要把树节点和数据节点搞混。树节点指的是四叉树上的数据结构，每个树节点最多有四个子树节点，但是可以有bucketCapacity大小的数据节点，数据节点仅仅是用来封装坐标系和其相关的数据的一个数据结构，非四叉树特有。
看完了数据定义，我们再来看看其实现部分。
#pragma mark - Constructors
TBQuadTreeNodeData TBQuadTreeNodeDataMake(double x, double y, void* data)
{
TBQuadTreeNodeData d; d.x = x; d.y = y; d.data = data;
return d;
}
TBBoundingBox TBBoundingBoxMake(double x0, double y0, double xf, double yf)
{
TBBoundingBox bb; bb.x0 = x0; bb.y0 = y0; bb.xf = xf; bb.yf = yf;
return bb;
}
TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity)
{
TBQuadTreeNode* node = malloc(sizeof(TBQuadTreeNode));
node->northWest = NULL;
node->northEast = NULL;
node->southWest = NULL;
node->southEast = NULL;
node->boundingBox = boundary;
node->bucketCapacity = bucketCapacity;
node->count = 0;
node->points = malloc(sizeof(TBQuadTreeNodeData) * bucketCapacity);
return node;
}
这三个构造函数，分别是构造数据节点、长方形以及四叉树节点，默认情况下四叉树的节点并非满构造，而是初始化为空，根据需要插入新节点。
#pragma mark - Bounding Box Functions
bool TBBoundingBoxContainsData(TBBoundingBox box, TBQuadTreeNodeData data)
{
bool containsX = box.x0 <= data.x && data.x <= box.xf;
bool containsY = box.y0 <= data.y && data.y <= box.yf;
return containsX && containsY
}
bool TBBoundingBoxIntersectsBoundingBox(TBBoundingBox b1, TBBoundingBox b2)
{
return (b1.x0 <= b2.xf && b1.xf >= b2.x0 && b1.y0 <= b2.yf && b1.yf >= b2.y0);
}
随后就是上面两个判断长方形包含和相交的方法了，包含自然是整个包围。而相交的补集是不相交，即在横坐标上一个长方形的xf另一个长方形的x0抑或是一个长方形的x0完全大于另一个长方形的xf，当然在y轴上也是同理，因此通过补集很容易就理解TBBoundingBoxIntersectsBoundingBox的实现了。
然后来看看非常重要的几个函数，首先是TBQuadTreeNodeSubdivide
void TBQuadTreeNodeSubdivide(TBQuadTreeNode* node)
{
TBBoundingBox box = node->boundingBox;
double xMid = (box.xf + box.x0) / 2.0
double yMid = (box.yf + box.y0) / 2.0
TBBoundingBox northWest = TBBoundingBoxMake(box.x0, box.y0, xMid, yMid)
node->northWest = TBQuadTreeNodeMake(northWest, node->bucketCapacity);
TBBoundingBox northEast = TBBoundingBoxMake(xMid, box.y0, box.xf, yMid)
node->northEast = TBQuadTreeNodeMake(northEast, node->bucketCapacity);
TBBoundingBox southWest = TBBoundingBoxMake(box.x0, yMid, xMid, box.yf);
node->southWest = TBQuadTreeNodeMake(southWest, node->bucketCapacity);
TBBoundingBox southEast = TBBoundingBoxMake(xMid, yMid, box.xf, box.yf);
node->southEast = TBQuadTreeNodeMake(southEast, node->bucketCapacity);
}
这个函数负责将四叉树节点进行细分。首先获取当前节点负责的长方形区域的中点，然后根据中点到原有长方形的四个顶点，分成四个象限，进行划分。这个时候请注意，还只是进行四叉树节点的细分，还没重新更改数据节点的分布。
bool TBQuadTreeNodeInsertData(TBQuadTreeNode* node, TBQuadTreeNodeData data)
{
if (!TBBoundingBoxContainsData(node->boundingBox, data)) {
return false;
}
if (node->count < node->bucketCapacity) {
node->points[node->count++] = data;
return true;
}
if (node->northWest == NULL) {
TBQuadTreeNodeSubdivide(node);
}
if (TBQuadTreeNodeInsertData(node->northWest, data)) return true;
if (TBQuadTreeNodeInsertData(node->northEast, data)) return true;
if (TBQuadTreeNodeInsertData(node->southWest, data)) return true;
if (TBQuadTreeNodeInsertData(node->southEast, data)) return true;
return false;
}
这个函数则是真正的将数据插入到节点中。
- 首先先判断这个数据是否落在该长方形中，不是直接滚蛋。
- 如果当前包含的数据节点个数没有超过最大数目，直接应用在其中。
- 如果四个子节点为空，就先创建
- 然后再递归插入
void TBQuadTreeGatherDataInRange(TBQuadTreeNode* node, TBBoundingBox range, TBDataReturnBlock block)
{
if (!TBBoundingBoxIntersectsBoundingBox(node->boundingBox, range)) {
return;
}
for (int i = 0; i < node->count; i++) {
if (TBBoundingBoxContainsData(range, node->points[i])) {
block(node->points[i]);
}
}
if (node->northWest == NULL) {
return;
}
TBQuadTreeGatherDataInRange(node->northWest, range, block);
TBQuadTreeGatherDataInRange(node->northEast, range, block);
TBQuadTreeGatherDataInRange(node->southWest, range, block);
TBQuadTreeGatherDataInRange(node->southEast, range, block);
}
这个就是通过DFS进行节点的遍历，一旦有落在range内的数据节点，就进行回调。
综上所述，就是一个基本的四叉树，可以很明显的看到，在四叉树的构建、遍历中，都用了树的递归，也就是俗称的DFS算法。
TBCoordinateQuadTree
这个类呢，和实质上的四叉树或者性能优化并无太大关系，只是一层简单的封装，我们大致来了解一下就好。
TBBoundingBox TBBoundingBoxForMapRect(MKMapRect mapRect)
{
CLLocationCoordinate2D topLeft = MKCoordinateForMapPoint(mapRect.origin)
CLLocationCoordinate2D botRight = MKCoordinateForMapPoint(MKMapPointMake(MKMapRectGetMaxX(mapRect), MKMapRectGetMaxY(mapRect)))
CLLocationDegrees minLat = botRight.latitude;
CLLocationDegrees maxLat = topLeft.latitude
CLLocationDegrees minLon = topLeft.longitude
CLLocationDegrees maxLon = botRight.longitude;
return TBBoundingBoxMake(minLat, minLon, maxLat, maxLon)
}
MKMapRect TBMapRectForBoundingBox(TBBoundingBox boundingBox)
{
MKMapPoint topLeft = MKMapPointForCoordinate(CLLocationCoordinate2DMake(boundingBox.x0, boundingBox.y0));
MKMapPoint botRight = MKMapPointForCoordinate(CLLocationCoordinate2DMake(boundingBox.xf, boundingBox.yf));
return MKMapRectMake(topLeft.x, botRight.y, fabs(botRight.x - topLeft.x), fabs(botRight.y - topLeft.y))
}
这两个函数就是MKMapRect和我们的BoundingBox之间的转换，难度很小，但是很有意思啊。从中我们可以一窥MapView的一些实现。比如MapView不仅仅是传统的ContentView和ContainerView，更重要的其坐标系和传统的CGRect之间的无法换算，简而言之，就是，在MapView中，所有的东西都要拿经度纬度来谈。
- (NSArray *)clusteredAnnotationsWithinMapRect:(MKMapRect)rect withZoomScale:(double)zoomScale
{
double TBCellSize = TBCellSizeForZoomScale(zoomScale);
double scaleFactor = zoomScale / TBCellSize;
NSInteger minX = floor(MKMapRectGetMinX(rect) * scaleFactor);
NSInteger maxX = floor(MKMapRectGetMaxX(rect) * scaleFactor);
NSInteger minY = floor(MKMapRectGetMinY(rect) * scaleFactor);
NSInteger maxY = floor(MKMapRectGetMaxY(rect) * scaleFactor);
NSMutableArray *clusteredAnnotations = [[NSMutableArray alloc] init];
for (NSInteger x = minX; x <= maxX; x++) {
for (NSInteger y = minY; y <= maxY; y++) {
MKMapRect mapRect = MKMapRectMake(x / scaleFactor, y / scaleFactor, 1.0 / scaleFactor, 1.0 / scaleFactor);
__block double totalX = 0;
__block double totalY = 0;
__block int count = 0;
NSMutableArray *names = [[NSMutableArray alloc] init];
NSMutableArray *phoneNumbers = [[NSMutableArray alloc] init];
TBQuadTreeGatherDataInRange(self.root, TBBoundingBoxForMapRect(mapRect), ^(TBQuadTreeNodeData data) {
totalX += data.x;
totalY += data.y;
count++;
TBHotelInfo hotelInfo = *(TBHotelInfo *)data.data;
[names addObject:[NSString stringWithFormat:@"%s", hotelInfo.hotelName]];
[phoneNumbers addObject:[NSString stringWithFormat:@"%s", hotelInfo.hotelPhoneNumber]];
});
if (count == 1) {
CLLocationCoordinate2D coordinate = CLLocationCoordinate2DMake(totalX, totalY);
TBClusterAnnotation *annotation = [[TBClusterAnnotation alloc] initWithCoordinate:coordinate count:count];
annotation.title = [names lastObject];
annotation.subtitle = [phoneNumbers lastObject];
[clusteredAnnotations addObject:annotation];
}
if (count > 1) {
CLLocationCoordinate2D coordinate = CLLocationCoordinate2DMake(totalX / count, totalY / count);
TBClusterAnnotation *annotation = [[TBClusterAnnotation alloc] initWithCoordinate:coordinate count:count];
[clusteredAnnotations addObject:annotation];
}
}
}
return [NSArray arrayWithArray:clusteredAnnotations];
}
而上述的最后一个函数，就是根据传入的MKMapRect，返回簇类数组的。
- 1.首先根据放缩比例，或者Cell大小。
- 2.根据cell大小计算当前地图区域的范围所对应的minX - maxX，minY - maxY对应的网格。
什么是网格？就是根据Cell大小将地图划分成了一块块区域，通过minX， maxX, minY - maxY找到对应的网格。类似于array[1][2]找到第二行第三列的网格（从0开始索引）。
- 3.遍历每一个网格，获取当前网格对应的四叉树节点中的数据信息，并记录个数。
- 4.如果个数是1，那么直接显示，包含数据节点的附加信息，比如在这里就是酒店名称和酒店电话。
- 5.如果个数大于1的话，利用均值计算中心点，中心点是所有包含的数据节点平均值，同时信息只简单的显示个数。
至此，整个代码就解读完整啦。
