iOS 地图分割，四叉树数据结构C语言版

两个类，第一个OTMQuadTree是数据结构类（4叉树），第二个是树的操作OC类，OTMCoordinateTree。仍有许多地方需要完善，暂时还没有时间，后续抽时间完成。

OTMQuadTree.h文件

#ifndef OTMQuadTree_h
#define OTMQuadTree_h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

typedef struct OTMCoordinate {
    double lat;
    double lng;
}OTMCoordinate;
OTMCoordinate OTMCoordinateMake(double lat, double lng);

typedef struct OTMQuadTreeNodeData{
    OTMCoordinate coordinate;
    void* data;
}OTMQuadTreeNodeData;
OTMQuadTreeNodeData OTMQuadTreeNodeDataMake(double lat, double lng, void* data);
OTMQuadTreeNodeData OTMQuadTreeNodeDataMakeWithCoord(OTMCoordinate coord, void* data);

typedef struct OTMBoundingBox {
    struct OTMCoordinate leftTop;
    struct OTMCoordinate rightBottom;
}OTMBoundingBox;
OTMBoundingBox OTMBoundingBoxMakeWithCoordinate(OTMCoordinate leftTop , OTMCoordinate rightBottom);
OTMBoundingBox OTMBoundingBoxMake(double leftX, double leftY, double rightX , double rightY);

typedef struct OTMQuadTreeNode {
    struct OTMQuadTreeNode* leftTop;
    struct OTMQuadTreeNode* rightTop;
    struct OTMQuadTreeNode* leftBottom;
    struct OTMQuadTreeNode* rightBottom;
    OTMBoundingBox boundingBox;
    OTMQuadTreeNodeData* nodeDatas;
    int capacity;
    int count;
}OTMQuadTreeNode;
OTMQuadTreeNode* OTMQuadTreeNodeMake(OTMBoundingBox boundingBox, int capacity);

void freeNode(OTMQuadTreeNode* node);
bool nodeInserData(OTMQuadTreeNode* node, OTMQuadTreeNodeData data);

typedef void (^OTMQuadTreeReturnDataBlock)(OTMQuadTreeNodeData data);
typedef void (^OTMQuadTreeTraverseBlock)(OTMQuadTreeNode *node);

#pragma mark -
#pragma mark - Tree Function
void freeNode(OTMQuadTreeNode* node);
OTMQuadTreeNode* quadTreeBulidWithData(OTMQuadTreeNodeData *data, int count, int capacity, OTMBoundingBox box);
void quadTreeTraverse(OTMQuadTreeNode *node,OTMQuadTreeTraverseBlock block);
void gatherDataInBox(OTMQuadTreeNode *node, OTMBoundingBox box ,OTMQuadTreeReturnDataBlock block);
bool nodeInserData(OTMQuadTreeNode* node, OTMQuadTreeNodeData data);
void nodeSubDivide(OTMQuadTreeNode* node);

#pragma mark -
#pragma mark - Box Function
bool boxIntersectsBox(OTMBoundingBox box1, OTMBoundingBox box2);
bool boxContainData(OTMBoundingBox box, OTMQuadTreeNodeData data);
#endif /* OTMQuadTree_h */

OTMQuadTree.c文件

#include "OTMQuadTree.h"
#include <CoreFoundation/CoreFoundation.h>
OTMCoordinate OTMCoordinateMake(double lat, double lng) {
    OTMCoordinate coord;
    coord.lat = lat;
    coord.lng = lng;
    return coord;
}

OTMQuadTreeNodeData OTMQuadTreeNodeDataMakeWithCoord(OTMCoordinate coord, void* data) {
    OTMQuadTreeNodeData nodeData;
    nodeData.coordinate = coord;
    nodeData.data = data;
    return nodeData;
}

OTMQuadTreeNodeData OTMQuadTreeNodeDataMake(double lat, double lng, void* data) {
    return OTMQuadTreeNodeDataMakeWithCoord(OTMCoordinateMake(lat, lng), data);
};

OTMBoundingBox OTMBoundingBoxMakeWithCoordinate(OTMCoordinate leftTop , OTMCoordinate rightBottom) {
    OTMBoundingBox box;
    box.leftTop = leftTop;
    box.rightBottom = rightBottom;
    return box;
}

OTMBoundingBox OTMBoundingBoxMake(double leftX, double leftY, double rightX , double rightY) {
    OTMCoordinate lt = OTMCoordinateMake(leftX, leftY);
    OTMCoordinate rb = OTMCoordinateMake(rightX, rightY);
    return OTMBoundingBoxMakeWithCoordinate(lt, rb);
}

OTMQuadTreeNode* OTMQuadTreeNodeMake(OTMBoundingBox boundingBox, int capacity) {
    OTMQuadTreeNode *node = malloc(sizeof(OTMQuadTreeNode));
    node->leftTop = NULL;
    node->rightTop = NULL;
    node->leftBottom = NULL;
    node->rightBottom = NULL;
    node->boundingBox = boundingBox;
    node->capacity = capacity;
    node->count = 0;
    node->nodeDatas = malloc(sizeof(OTMQuadTreeNodeData) * capacity);
    return node;
}

#pragma Box Function
bool boxContainData(OTMBoundingBox box, OTMQuadTreeNodeData data) {
    double maxLat = box.leftTop.lat;
    double minLat = box.rightBottom.lat;
    double minLng = box.leftTop.lng;
    double maxLng = box.rightBottom.lng;
    bool latContain = data.coordinate.lat >= minLat && data.coordinate.lat <= maxLat;
    bool lngContain = data.coordinate.lng >= minLng && data.coordinate.lng <= maxLng;
    return latContain && lngContain;
}

bool boxIntersectsBox(OTMBoundingBox box1, OTMBoundingBox box2) {
    bool latInter = box1.leftTop.lat >= box2.rightBottom.lat && box1.rightBottom.lat <= box2.leftTop.lat;
    bool lngInter = box1.leftTop.lng <= box2.rightBottom.lng && box1.rightBottom.lng >= box2.leftTop.lng;
    return latInter && lngInter;
}

#pragma Tree Function

void nodeSubDivide(OTMQuadTreeNode* node) {
    
    double midLat = fabs(node->boundingBox.rightBottom.lat + node->boundingBox.leftTop.lat) / 2;
    double midLng = fabs(node->boundingBox.rightBottom.lng + node->boundingBox.leftTop.lng) / 2;
    OTMCoordinate midCoord = OTMCoordinateMake(midLat, midLng);
    
    OTMBoundingBox ltBox = OTMBoundingBoxMakeWithCoordinate(node->boundingBox.leftTop, midCoord);
    node->leftTop = OTMQuadTreeNodeMake(ltBox, node->capacity);
    
    OTMBoundingBox rtBox = OTMBoundingBoxMake(midLat, node->boundingBox.leftTop.lng, node->boundingBox.rightBottom.lat, midLng);
    node->rightTop = OTMQuadTreeNodeMake(rtBox, node->capacity);
    
    OTMBoundingBox lbBox = OTMBoundingBoxMake(node->boundingBox.leftTop.lat, midLng, midLat, node->boundingBox.rightBottom.lng);
    node->leftBottom = OTMQuadTreeNodeMake(lbBox, node->capacity);
    
    OTMBoundingBox rbBox = OTMBoundingBoxMake(midLat, midLng, node->boundingBox.rightBottom.lat, node->boundingBox.rightBottom.lng);
    node->rightBottom = OTMQuadTreeNodeMake(rbBox, node->capacity);
}

bool nodeInserData(OTMQuadTreeNode* node, OTMQuadTreeNodeData data) {
    
    // box不包涵data的点则失败
    if (!boxContainData(node->boundingBox, data)) {
        return false;
    }
    
    if (node->count < node->capacity) {
        node->nodeDatas[node->count] = data;
        node->count++;
        return true;
    }
    
    //父box满了
    if (node->leftTop == NULL) { //如果没有子box
        //分割
        nodeSubDivide(node);
    }
    
    //递归查找插入位置，直到成功
    if (nodeInserData(node->leftTop, data)) return true;
    if (nodeInserData(node->rightTop, data)) return true;
    if (nodeInserData(node->leftBottom, data)) return true;
    if (nodeInserData(node->rightBottom, data)) return true;
    
    return false;
}

void gatherDataInBox(OTMQuadTreeNode *node, OTMBoundingBox box ,OTMQuadTreeReturnDataBlock block) {
    if (!boxIntersectsBox(node->boundingBox, box)) {
        //两个box不相交不合并
        return;
    }
    //遍历node中所有的数据，判断某个数据是否在目标范围呢，在则执行block
    for (int i = 0 ; i < node->count; i++) {
        if (boxContainData(box, node->nodeDatas[i])) {
            if (block) {
                block(node->nodeDatas[i]);
            }
        }
    }
    //没有子区域了直接返回
    if (node->leftTop == NULL) {
        return;
    }
    
    //递归假如到子box中
    gatherDataInBox(node->leftTop, box, block);
    gatherDataInBox(node->rightTop, box, block);
    gatherDataInBox(node->leftBottom, box, block);
    gatherDataInBox(node->rightBottom, box, block);
}

void quadTreeTraverse(OTMQuadTreeNode *node,OTMQuadTreeTraverseBlock block){
    
    if (block) {
        block(node);
    }
    
    if (node->leftTop == NULL) {
        return;
    }
    
    quadTreeTraverse(node->leftTop,block);
    quadTreeTraverse(node->rightTop,block);
    quadTreeTraverse(node->leftBottom,block);
    quadTreeTraverse(node->rightBottom,block);
}

OTMQuadTreeNode* quadTreeBulidWithData(OTMQuadTreeNodeData *data, int count, int capacity, OTMBoundingBox box) {
    OTMQuadTreeNode *root = OTMQuadTreeNodeMake(box, capacity);
    for (int i = 0; i < count; i++) {
        nodeInserData(root, data[i]);
    }
    return root;
}

void freeNode(OTMQuadTreeNode* node) {
    if (node->leftTop != NULL) freeNode(node->leftTop);
    if (node->rightTop != NULL) freeNode(node->rightTop);
    if (node->leftBottom != NULL) freeNode(node->leftBottom);
    if (node->rightBottom != NULL) freeNode(node->rightBottom);
    
    for (int i = 0 ; i < node -> count; i++) {
        OTMQuadTreeNodeData nodeData = node->nodeDatas[i];
//        free(nodeData.data);
        //如果data是oc对象需要用CFRelease()释放，导入头文件#include <CoreFoundation/CoreFoundation.h>
        CFRelease(nodeData.data);
    }
    free(node->nodeDatas);
    free(node);
}

OTMCoordinateTree.h文件

#import <Foundation/Foundation.h>
#import "OTMQuadTree.h"
#import <MapKit/MapKit.h>
#import "OTMValueDefinitions.h"

@interface OTMCoordinateTree : NSObject
@property (nonatomic, assign) OTMQuadTreeNode *root;
@property (nonatomic, strong) NSArray<OTMPhotoModel *> *modelsArray;
@property (nonatomic, assign) CLLocationCoordinate2D requestLeftTopCoord;
@property (nonatomic, assign) CLLocationCoordinate2D requestRightBottomCoord;

- (NSArray *)clusteredAnnotationsWithinMapRect:(MKMapRect)rect withZoomScale:(double)zoomScale;
- (NSArray *)clusteredMaskAnnotationsOn:(MKMapView *)mapView;

- (void)buildTree;
- (void)rebuildTree;
- (void)clean;
@end

OTMCoordinateTree.m文件

#import "OTMCoordinateTree.h"
#import <CoreLocation/CoreLocation.h>

OTMBoundingBox boxFormMapRect(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 OTMBoundingBoxMakeWithCoordinate(OTMCoordinateMake(topLeft.latitude, topLeft.longitude), OTMCoordinateMake(botRight.latitude, botRight.longitude));
//    return OTMBoundingBoxMake(maxLat, minLon, minLat, maxLon);
}

MKMapRect mapRectFormBox(OTMBoundingBox box) {
    MKMapPoint topLeft = MKMapPointForCoordinate(CLLocationCoordinate2DMake(box.leftTop.lat, box.leftTop.lng));
    MKMapPoint botRight = MKMapPointForCoordinate(CLLocationCoordinate2DMake(box.rightBottom.lat, box.rightBottom.lng));

    return MKMapRectMake(topLeft.x, botRight.y, fabs(botRight.x - topLeft.x), fabs(botRight.y - topLeft.y));
}

NSInteger zoomScaleToZoomLevel(MKZoomScale scale)
{
    double totalTilesAtMaxZoom = MKMapSizeWorld.width / 256.0;
    NSInteger zoomLevelAtMaxZoom = log2(totalTilesAtMaxZoom);
    NSInteger zoomLevel = MAX(0, zoomLevelAtMaxZoom + floor(log2f(scale) + 0.5));
    
    return zoomLevel;
}

@implementation OTMCoordinateTree

- (void)buildTree {
    @autoreleasepool {
        if (self.modelsArray.count == 0) {
            return;
        }
        NSInteger count = self.modelsArray.count;

        OTMQuadTreeNodeData *dataArray = malloc(sizeof(OTMQuadTreeNodeData) * count);
        for (int i = 0 ; i < count; i++) {
            OTMPhotoModel *model = self.modelsArray[i];
            dataArray[i] = OTMQuadTreeNodeDataMake(model.coordinate.latitude, model.coordinate.longitude, (__bridge void *)(model));
        }
        
//        for (int i = 0; i < count; i++) {
//            OTMPhotoModel *model = (__bridge OTMPhotoModel *)(dataArray[i].data);
//            NSLog(@"omt test model index:%d url = %@",i,model.preview_url);
//        }
        
        OTMBoundingBox box = OTMBoundingBoxMake(self.requestLeftTopCoord.latitude,
                                                self.requestLeftTopCoord.longitude,
                                                self.requestRightBottomCoord.latitude,
                                                self.requestRightBottomCoord.longitude);
        
        self.root = quadTreeBulidWithData(dataArray,(int)count, 4, box);
    }
}

- (void)rebuildTree {
    [self clean];
    [self buildTree];
}

- (NSArray *)clusteredMaskAnnotationsOn:(MKMapView *)mapView {
    CGFloat gridWidth = kOTMPhotoAnnotationWidth;
    //计算每个图片的对应的maprect
    __block NSMutableArray *needRemoveModels = [[NSMutableArray alloc] init];
    [self.modelsArray enumerateObjectsUsingBlock:^(OTMPhotoModel * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        OTMPhotoModel *currentModel = obj;
        if (obj.gathered) {
            return ;
        }

        CGPoint centerPt = [mapView convertCoordinate:obj.coordinate toPointToView:mapView];
        CGRect objClusterRect = CGRectMake(centerPt.x -gridWidth, centerPt.y - gridWidth, gridWidth * 2, gridWidth * 2);
        MKCoordinateRegion objClusterRegion = [mapView convertRect:objClusterRect toRegionFromView:mapView];
        MKMapRect mapRect = [self mapRectForCoordinateRegion:objClusterRegion];
        [self.modelsArray enumerateObjectsUsingBlock:^(OTMPhotoModel * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            if (currentModel == obj || obj.gathered) {
                return ;
            }
            MKMapPoint point = MKMapPointForCoordinate(obj.coordinate);
            if (MKMapRectContainsPoint(mapRect, point)) {
                //有重叠的
                obj.gathered = YES;
                [currentModel.gatheredModels addObject:obj];
                [needRemoveModels addObject:obj];
            }
        }];
    }];
    
    if (needRemoveModels.count > 0) {
        NSMutableArray *arr = [NSMutableArray arrayWithArray:self.modelsArray];
        [arr removeObjectsInArray:needRemoveModels];
        self.modelsArray = arr;
    }
    return self.modelsArray;
}

- (MKMapRect)mapRectForCoordinateRegion:(MKCoordinateRegion)coordinateRegion
{
    CLLocationCoordinate2D topLeftCoordinate =
    CLLocationCoordinate2DMake(coordinateRegion.center.latitude
                               + (coordinateRegion.span.latitudeDelta/2.0),
                               coordinateRegion.center.longitude
                               - (coordinateRegion.span.longitudeDelta/2.0));
    
    MKMapPoint topLeftMapPoint = MKMapPointForCoordinate(topLeftCoordinate);
    
    CLLocationCoordinate2D bottomRightCoordinate =
    CLLocationCoordinate2DMake(coordinateRegion.center.latitude
                               - (coordinateRegion.span.latitudeDelta/2.0),
                               coordinateRegion.center.longitude
                               + (coordinateRegion.span.longitudeDelta/2.0));
    
    MKMapPoint bottomRightMapPoint = MKMapPointForCoordinate(bottomRightCoordinate);
    
    MKMapRect mapRect = MKMapRectMake(topLeftMapPoint.x,
                                      topLeftMapPoint.y,
                                      fabs(bottomRightMapPoint.x-topLeftMapPoint.x),
                                      fabs(bottomRightMapPoint.y-topLeftMapPoint.y));
    
    return mapRect;
}

- (NSArray *)clusteredAnnotationsWithinMapRect:(MKMapRect)rect withZoomScale:(double)zoomScale
{
    double cellSize = 88;
    /// zoomScale = point * (1 / mapPoint)  * (1 / size) ==  point / size / mapPoint
    double scaleFactor = zoomScale / cellSize;
    
    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 *models = [[NSMutableArray alloc] init];
            
            gatherDataInBox(self.root, boxFormMapRect(mapRect), ^(OTMQuadTreeNodeData data) {
                totalX += data.coordinate.lat;
                totalY += data.coordinate.lng;
                count ++;
                
                OTMPhotoModel *model = (__bridge OTMPhotoModel *)(data.data);
                [models addObject:model];
            });
            
            if (count == 1) {
                CLLocationCoordinate2D coordinate = CLLocationCoordinate2DMake(totalX, totalY);
                OTMPhotoModel *model = (OTMPhotoModel *)models[0]; //默认使用第一个图片
                model.coordinate = coordinate;//修改显示的坐标
                [clusteredAnnotations addObject:model];
            }
            
            if (count > 1) {
                CLLocationCoordinate2D coordinate = CLLocationCoordinate2DMake(totalX / count, totalY / count);
                OTMPhotoModel *model =(OTMPhotoModel *)models[0]; //默认使用第一个图片
                model.coordinate = coordinate; //修改显示的坐标
                model.count = @(count); //从新计算count
                [clusteredAnnotations addObject:model];
            }
        }
    }
    
    return [NSArray arrayWithArray:clusteredAnnotations];
}

- (void)clean {
    if (self.root) {
        freeNode(self.root);
    }
}

- (NSArray<OTMPhotoModel *> *)modelsArray {
    if (!_modelsArray) {
        _modelsArray = [NSArray array];
    }
    return _modelsArray;
}

@end