如何在iOS地圖上以使用者可以了解并樂于接受的方式來處理和顯示大量資料?這個教程将會給大家進行示例說明。 我們要開發一款iOS的app應用,這個應用包含有87000個旅館的資訊,每個旅館的資訊中包括有一個坐标值,一個旅館名跟一個電話号碼。這款app可以在使用者拖動、放大縮小地圖時更新旅館資料,而不需要使用者重新進行搜尋。 為了達到這個目的,我們需要構造一個可快速檢索的資料結構。C語言的性能高,是以我們用C語言來構造這個資料結構。為了確定大量的資料不會讓使用者感到迷惑,是以我們還需要想出一個合并資料的解決方案。最後,為了更好的适應市場,我們需要把app做的更完善一些。 完成這個教學後,你将學到這款app的所有核心内容。
資料結構 首先我們先來分析下資料,搞清我們要如何處理資料。旅館資料中包含了一系列的坐标點(包括緯度和經度),我們需要根據這些坐标點在地圖上進行标注。地圖可以任意的拖動并放大縮小,是以我們不需要把所有的點都全部繪制出來,我們隻需要繪制可以顯示在螢幕上的點。核心問題是:我們需要查詢出顯示在螢幕上的所有的點,是以我們要想出一個查找算法,查找存在于一個矩形範圍内的所有點。 一個簡單的解決方式就是周遊所有的點,然後判斷(xMin<=x<=xMax并且yMin<=y<=yMax),很不幸,這是一個複雜度為O(N)的算法,顯然不适合我們的情況。 這兒有個更好的解決方法,就是我們可以利用對稱性來減少我們的查詢範圍。那麼如何能通過查詢的每一次的疊代來減少查詢的範圍呢?我們可以在每個區域内都加索引,這樣可以有效減少查詢的範圍。這種區域索引的方式可以用四叉樹來實作,查詢複雜度為O(H)(H是查詢的那個點所在的樹的高度) 四叉樹 四叉樹是一個資料結構,由一系列的結點(node)構成。每個結點包含一個桶(bucket)跟一個包圍框(boundingbox)。每個桶裡面有一系列的點(point)。如果一個點包含在一個外包圍框A中,就會被添加到A所在結點的桶(bucket)中。一旦這個結點的桶滿了,這個結點就會分裂成四個子結點,每個子節點的包圍框分别是目前結點包圍框的1/4。分裂之後那些本來要放到目前結點桶中的點就都會放到子容器的桶中。 那麼我們該如何來對四叉樹進行編碼呢? 我們先來定義基本的結構:
- typedef struct TBQuadTreeNodeData {
- double x;
- double y;
- void* data;
- } TBQuadTreeNodeData;
- TBQuadTreeNodeData TBQuadTreeNodeDataMake(double x, double 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);
TBQuadTreeNodeData結構包含了坐标點(緯度,經度)。void*data是一個普通的指針,用來存儲我們需要的其他資訊,如旅館名跟電話号碼。TBBoundingBox代表一個用于範圍查詢的長方形,也就是之前談到(xMin<=x<=xMax&&yMin<=y<=yMax)查詢的那個長方形。左上角是(xMin,yMin),右下角是(xMax,yMax)。 最後,我們看下TBQuadTreeNode結構,這個結構包含了四個指針,每個指針分别指向這個結點的四個子節點。它還有一個外包圍框和一個數組(數組中就是那個包含一系列坐标點的桶)。 在我們建立完四叉樹的同時,空間上的索引也就同時形成了。這是生成四叉樹的示範動畫。
下面的代碼準确描述了以上動畫的過程:
- 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)
- {
- // Bail if our coordinate is not in the boundingBox
- if (!TBBoundingBoxContainsData(node->boundingBox, data)) {
- return false;
- }
- // Add the coordinate to the points array
- if (node->count < node->bucketCapacity) {
- node->points[node->count++] = data;
- return true;
- }
- // Check to see if the current node is a leaf, if it is, split
- if (node->northWest == NULL) {
- TBQuadTreeNodeSubdivide(node);
- }
- // Traverse the tree
- 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;
- }
現在我們已經完成了四叉樹的構造,我們還需要在四叉樹上進行區域範圍查詢并傳回TBQuadTreeNodeData結構。以下是區域範圍查詢的示範動畫,在淺藍區域内的是所有的标注點。當标注點被查詢到在指定的區域範圍内,則會被标注為綠色。
以下是查詢代碼:
- typedef void(^TBDataReturnBlock)(TBQuadTreeNodeData data);
- void TBQuadTreeGatherDataInRange(TBQuadTreeNode* node, TBBoundingBox range, TBDataReturnBlock block)
- {
- // If range is not contained in the node's boundingBox then bail
- if (!TBBoundingBoxIntersectsBoundingBox(node->boundingBox, range)) {
- return;
- }
- for (int i = 0; i < node->count; i++) {
- // Gather points contained in range
- if (TBBoundingBoxContainsData(range, node->points[i])) {
- block(node->points[i]);
- }
- }
- // Bail if node is leaf
- if (node->northWest == NULL) {
- return;
- }
- // Otherwise traverse down the tree
- TBQuadTreeGatherDataInRange(node->northWest, range, block);
- TBQuadTreeGatherDataInRange(node->northEast, range, block);
- TBQuadTreeGatherDataInRange(node->southWest, range, block);
- TBQuadTreeGatherDataInRange(node->southEast, range, block);
- }
用四叉樹這種結構可以進行快速的查詢。在一個包含成百上千條資料的資料庫中,可以以60fps的速度查詢上百條資料。 用旅館資料來填充四叉樹 旅館的資料來自于POIplaza這個網站,而且已經格式化成csv檔案。我們要從硬碟中讀取出資料并對資料進行轉換,最後用資料來填充四叉樹。 建立四叉樹的代碼在TBCoordinateQuadTree類中:
- typedef struct TBHotelInfo {
- char* hotelName;
- char* hotelPhoneNumber;
- } TBHotelInfo;
- TBQuadTreeNodeData TBDataFromLine(NSString *line)
- {
- // Example line:
- // -80.26262, 25.81015, Everglades Motel, USA-United States, +1 305-888-8797
- NSArray *components = [line componentsSeparatedByString:@","];
- double latitude = [components[1] doubleValue];
- double longitude = [components[0] doubleValue];
- TBHotelInfo* hotelInfo = malloc(sizeof(TBHotelInfo));
- NSString *hotelName = [components[2] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
- hotelInfo->hotelName = malloc(sizeof(char) * hotelName.length + 1);
- strncpy(hotelInfo->hotelName, [hotelName UTF8String], hotelName.length + 1);
- NSString *hotelPhoneNumber = [[components lastObject] stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
- hotelInfo->hotelPhoneNumber = malloc(sizeof(char) * hotelPhoneNumber.length + 1);
- strncpy(hotelInfo->hotelPhoneNumber, [hotelPhoneNumber UTF8String], hotelPhoneNumber.length + 1);
- return TBQuadTreeNodeDataMake(latitude, longitude, hotelInfo);
- }
- - (void)buildTree
- {
- NSString *data = [NSString stringWithContentsOfFile:[[NSBundle mainBundle] pathForResource:@"USA-HotelMotel" ofType:@"csv"] encoding:NSASCIIStringEncoding error:nil];
- NSArray *lines = [data componentsSeparatedByString:@"\n"];
- NSInteger count = lines.count - 1;
- TBQuadTreeNodeData *dataArray = malloc(sizeof(TBQuadTreeNodeData) * count);
- for (NSInteger i = 0; i < count; i++) {
- dataArray[i] = TBDataFromLine(lines[i]);
- }
- TBBoundingBox world = TBBoundingBoxMake(19, -166, 72, -53);
- _root = TBQuadTreeBuildWithData(dataArray, count, world, 4);
- }
現在我們用iPhone上預加載的資料建立了一個四叉樹。接下來我們将處理app的下一個部分:合并資料(clustering)。 合并資料(clustering) 現在我們有了一個裝滿旅館資料的四叉樹,可以用來解決合并資料的問題了。首先,讓我們來探索下合并資料的原因。我們合并資料是因為我們不想因為資料過于龐大而使使用者迷惑。實際上有很多種方式可以解決這個問題。GoogleMaps根據地圖的縮放等級(zoomlevel)來顯示搜尋結果資料中的一部分資料。地圖放的越大,就越能清晰的看到更細節的标注,直到你能看到所有有效的标注。我們将采用這種合并資料的方式,隻顯示出來旅館的個數,而不在地圖上顯示出所有的旅館資訊。 最終呈現的标注是一個中心顯示旅館個數的小圓圈。實作的原理跟如何把圖檔縮小的原理差不多。我們先在地圖上畫一個格子。每個格子中包含了很多個小單元格,每個小單元格中的所有旅館資料合并出一個标注。然後通過每個小單元格中所有旅館的坐标值的平均值來決定合并後這個标注的坐标值。 這是以上處理的示範動畫。
以下是代碼實作過程。在TBCoordinateQuadTree類中添加了一個方法。
- - (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;
- TBQuadTreeGatherDataInRange(self.root, TBBoundingBoxForMapRect(mapRect), ^(TBQuadTreeNodeData data) {
- totalX += data.x;
- totalY += data.y;
- count++;
- });
- 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];
- }
上面的方法在指定小單元格大小的前提下合并資料生成了最終的标注。現在我們需要做的就是把這些标注繪制到MKMapView上。首先我們建立一個UIViewController的子類,然後用MKMapView作為它的view視圖。在可視區域改變的情況下,我們需要實時更新标注的顯示,是以我們要實作mapView:regionDidChangeAnimated:的協定方法。
- - (void)mapView:(MKMapView *)mapView regionDidChangeAnimated:(BOOL)animated
- {
- [[NSOperationQueue new] addOperationWithBlock:^{
- double zoomScale = self.mapView.bounds.size.width / self.mapView.visibleMapRect.size.width;
- NSArray *annotations = [self.coordinateQuadTree clusteredAnnotationsWithinMapRect:mapView.visibleMapRect withZoomScale:zoomScale];
- [self updateMapViewAnnotationsWithAnnotations:annotations];
- }];
- }
隻添加必要的标注 在主線程中我們期望盡可能花費較少時間來做運算,這意味着我們要盡可能的把所有内容都放到背景的線程中。為了在主線程中花費更少的時間來做計算,我們隻需要繪制一些必要的标注。這可以避免使用者滑動過程中感到很卡,進而保證流暢的使用者體驗。 開始之前,我們看一下下面的圖檔:
左邊的螢幕截圖是地圖進行滑動前的地圖快照。這個快照中的标注就是目前mapView中的标注,我們稱這個為“before集合”。 右邊的螢幕截圖是地圖進行滑動後的地圖快照。這個快照中的标注就是從clusteredAnnotationsWithinMapRect:withZoomScale:這個函數中得到的傳回值。我們稱這個為“after集合”。 我們期望保留兩個快照中都存在的标注點(即重合的那些标注點),去除在“after集合”中不存在的那些标注點,同時添加那些新的标注點。
- - (void)updateMapViewAnnotationsWithAnnotations:(NSArray *)annotations
- {
- NSMutableSet *before = [NSMutableSet setWithArray:self.mapView.annotations];
- NSSet *after = [NSSet setWithArray:annotations];
- // Annotations circled in blue shared by both sets
- NSMutableSet *toKeep = [NSMutableSet setWithSet:before];
- [toKeep intersectSet:after];
- // Annotations circled in green
- NSMutableSet *toAdd = [NSMutableSet setWithSet:after];
- [toAdd minusSet:toKeep];
- // Annotations circled in red
- NSMutableSet *toRemove = [NSMutableSet setWithSet:before];
- [toRemove minusSet:after];
- // These two methods must be called on the main thread
- [[NSOperationQueue mainQueue] addOperationWithBlock:^{
- [self.mapView addAnnotations:[toAdd allObjects]];
- [self.mapView removeAnnotations:[toRemove allObjects]];
- }];
- }
這樣我們盡可能的確定在主線程上做少量的工作,進而提升地圖滑動的流暢性。 接下來我們來看下如何繪制标注,并且在标注上顯示出來旅館的個數。最後我們給标注加上點選事件,這樣使得app從頭到腳都可以表現的非常完美。 繪制标注 由于我們在地圖上并沒有完全顯示出全部旅館,是以我們需要在剩餘的這些标注上表現出真實的旅館總量。 首先建立一個圓形的标注,中間顯示合并後的個數,也就是旅館的真實總量。這個圓形的大小同樣可以反映出合并後的個數。 為了實作這個需求,我們要找出一個方程式,允許我們在1到500+的數值中生成一個縮小後的數值。用這個數值來作為标注的大小。我們将用到以下的方程式。
x值較低的時候f(x)增長的比較快,x在值變大的時候f(x)增長變緩慢,β值用來控制f(x)趨于1的速度。α值影響最小值(在我們的項目中,我們的最小合并值(也就是1)能占總共最大值的60%)。
- static CGFloat const TBScaleFactorAlpha = 0.3;
- static CGFloat const TBScaleFactorBeta = 0.4;
- CGFloat TBScaledValueForValue(CGFloat value)
- {
- return 1.0 / (1.0 + expf(-1 * TBScaleFactorAlpha * powf(value, TBScaleFactorBeta)));
- }
- - (void)setCount:(NSUInteger)count
- {
- _count = count;
- // Our max size is (44,44)
- CGRect newBounds = CGRectMake(0, 0, roundf(44 * TBScaledValueForValue(count)), roundf(44 * TBScaledValueForValue(count)));
- self.frame = TBCenterRect(newBounds, self.center);
- CGRect newLabelBounds = CGRectMake(0, 0, newBounds.size.width / 1.3, newBounds.size.height / 1.3);
- self.countLabel.frame = TBCenterRect(newLabelBounds, TBRectCenter(newBounds));
- self.countLabel.text = [@(_count) stringValue];
- [self setNeedsDisplay];
- }
現在标注的大小已經OK了。讓我們再來把這個标注做漂亮些。
- - (void)setupLabel
- {
- _countLabel = [[UILabel alloc] initWithFrame:self.frame];
- _countLabel.backgroundColor = [UIColor clearColor];
- _countLabel.textColor = [UIColor whiteColor];
- _countLabel.textAlignment = NSTextAlignmentCenter;
- _countLabel.shadowColor = [UIColor colorWithWhite:0.0 alpha:0.75];
- _countLabel.shadowOffset = CGSizeMake(0, -1);
- _countLabel.adjustsFontSizeToFitWidth = YES;
- _countLabel.numberOfLines = 1;
- _countLabel.font = [UIFont boldSystemFontOfSize:12];
- _countLabel.baselineAdjustment = UIBaselineAdjustmentAlignCenters;
- [self addSubview:_countLabel];
- }
- - (void)drawRect:(CGRect)rect
- {
- CGContextRef context = UIGraphicsGetCurrentContext();
- CGContextSetAllowsAntialiasing(context, true);
- UIColor *outerCircleStrokeColor = [UIColor colorWithWhite:0 alpha:0.25];
- UIColor *innerCircleStrokeColor = [UIColor whiteColor];
- UIColor *innerCircleFillColor = [UIColor colorWithRed:(255.0 / 255.0) green:(95 / 255.0) blue:(42 / 255.0) alpha:1.0];
- CGRect circleFrame = CGRectInset(rect, 4, 4);
- [outerCircleStrokeColor setStroke];
- CGContextSetLineWidth(context, 5.0);
- CGContextStrokeEllipseInRect(context, circleFrame);
- [innerCircleStrokeColor setStroke];
- CGContextSetLineWidth(context, 4);
- CGContextStrokeEllipseInRect(context, circleFrame);
- [innerCircleFillColor setFill];
- CGContextFillEllipseInRect(context, circleFrame);
- }
添加最後的touch事件 目前的标注可以很好的呈現出我們的資料了,讓我們最後添加一些touch事件來讓我們的app用起來更有趣。 首先,我們需要為新添加到地圖上的标注做一個動畫。如果沒有添加動畫的話,新的标注就會在地圖上突然出現,體驗效果将會大打折扣。
- - (void)addBounceAnnimationToView:(UIView *)view
- {
- CAKeyframeAnimation *bounceAnimation = [CAKeyframeAnimation animationWithKeyPath:@"transform.scale"];
- bounceAnimation.values = @[@(0.05), @(1.1), @(0.9), @(1)];
- bounceAnimation.duration = 0.6;
- NSMutableArray *timingFunctions = [[NSMutableArray alloc] init];
- for (NSInteger i = 0; i < 4; i++) {
- [timingFunctions addObject:[CAMediaTimingFunction functionWithName:kCAMediaTimingFunctionEaseInEaseOut]];
- }
- [bounceAnimation setTimingFunctions:timingFunctions.copy];
- bounceAnimation.removedOnCompletion = NO;
- [view.layer addAnimation:bounceAnimation forKey:@"bounce"];
- }
- - (void)mapView:(MKMapView *)mapView didAddAnnotationViews:(NSArray *)views
- {
- for (UIView *view in views) {
- [self addBounceAnnimationToView:view];
- }
- }
接下來,我們想要根據地圖的縮放比例來改變在合并時的小單元格(cell)的大小。在地圖進行放大時,小單元格變小。是以我們需要定義一下目前地圖的縮放比例。也就是scale=mapView.bounds.size.width/mapView.visibleMapRect.size.width:
- NSInteger TBZoomScaleToZoomLevel(MKZoomScale scale)
- {
- double totalTilesAtMaxZoom = MKMapSizeWorld.width / 256.0;
- NSInteger zoomLevelAtMaxZoom = log2(totalTilesAtMaxZoom);
- NSInteger zoomLevel = MAX(0, zoomLevelAtMaxZoom + floor(log2f(scale) + 0.5));
- return zoomLevel;
- }
我們為每個地圖縮放的比例都定義一個常量。
- float TBCellSizeForZoomScale(MKZoomScale zoomScale)
- {
- NSInteger zoomLevel = TBZoomScaleToZoomLevel(zoomScale);
- switch (zoomLevel) {
- case 13:
- case 14:
- case 15:
- return 64;
- case 16:
- case 17:
- case 18:
- return 32;
- case 19:
- return 16;
- default:
- return 88;
- }
- }
現在我們放大地圖,我們将看到逐漸變小的标注,直到最後我們能看到代表每個旅館的那個标注。 源代碼:thecompleteworkingversionoftheapponGitHub. https://github.com/thoughtbot/TBAnnotationClustering