gistfile1.txt

- (void)addAnnotationsInBoundingBox:(RMProjectedRect)aBoundingBox
                     toMutableArray:(NSMutableArray *)someArray
           createClusterAnnotations:(BOOL)createClusterAnnotations
           withProjectedClusterSize:(RMProjectedSize)clusterSize
      andProjectedClusterMarkerSize:(RMProjectedSize)clusterMarkerSize
                  findGravityCenter:(BOOL)findGravityCenter
{
    if (createClusterAnnotations)
    {
        double halfWidth     = _boundingBox.size.width / 2.0;
        BOOL forceClustering = (_boundingBox.size.width >= clusterSize.width && halfWidth < clusterSize.width);

        NSArray *enclosedAnnotations = nil;

        // Leaf clustering
        if (forceClustering == NO && _nodeType == nodeTypeLeaf && [_annotations count] > 1)
        {
            NSMutableArray *annotationsToCheck = [NSMutableArray arrayWithArray:[self enclosedWithoutUnclusteredAnnotations]];
            
            NSArray* annotationTypes = [annotationsToCheck valueForKeyPath:@"@distinctUnionOfObjects.clusterIdentifier"];

            for (NSString* annotationIdentifier in annotationTypes) {
                annotationsToCheck = [NSMutableArray arrayWithArray: [annotationsToCheck filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"(self.clusterIdentifier == %@)", annotationIdentifier]]];
                
                for (NSInteger i=[annotationsToCheck count]-1; i>0; --i)
                {
                    BOOL similarAnnotationIdentifier = NO;
                    BOOL mustBeClustered = NO;
                    RMAnnotation *currentAnnotation = [annotationsToCheck objectAtIndex:i];
                    
                    for (NSInteger j=i-1; j>=0; --j)
                    {
                        RMAnnotation *secondAnnotation = [annotationsToCheck objectAtIndex:j];

                        // This is of course not very accurate but is good enough for this use case
                        double distance = RMEuclideanDistanceBetweenProjectedPoints(currentAnnotation.projectedLocation, secondAnnotation.projectedLocation) / _mapView.metersPerPixel;
                        similarAnnotationIdentifier = [currentAnnotation.clusterIdentifier isEqualToString:secondAnnotation.clusterIdentifier];
                        
                        if (distance < kMinPixelDistanceForLeafClustering && similarAnnotationIdentifier)
                        {
                            mustBeClustered = YES;
                            break;
                        }
                    }

                    if (!mustBeClustered)
                    {
                        [someArray addObject:currentAnnotation];
                        [annotationsToCheck removeObjectAtIndex:i];
                    }
                }

                forceClustering = ([annotationsToCheck count] > 0);

                if (forceClustering)
                {
                    @synchronized (_cachedClusterAnnotation)
                    {
                         _cachedClusterEnclosedAnnotations = nil;
                         _cachedClusterAnnotation = nil;
                    }

                    enclosedAnnotations = [NSArray arrayWithArray:annotationsToCheck];
                }
            
            }
        }

        if (forceClustering)
        {
            if (!enclosedAnnotations)
                enclosedAnnotations = [self enclosedWithoutUnclusteredAnnotations];
            
            NSArray* annotationTypes = [enclosedAnnotations valueForKeyPath:@"@distinctUnionOfObjects.clusterIdentifier"];
            
            for (NSString* annotationIdentifier in annotationTypes) {
                enclosedAnnotations = [NSMutableArray arrayWithArray: [enclosedAnnotations filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"(self.clusterIdentifier == %@)", annotationIdentifier]]];
                
                if ([enclosedAnnotations count] > 0){
                
                    @synchronized (_cachedClusterAnnotation)
                    {
                        if (_cachedClusterAnnotation && [enclosedAnnotations count] != [_cachedClusterEnclosedAnnotations count])
                        {
                             _cachedClusterEnclosedAnnotations = nil;
                             _cachedClusterAnnotation = nil;
                        }
                    }

                    if (!_cachedClusterAnnotation)
                    {
                        NSUInteger enclosedAnnotationsCount = [enclosedAnnotations count];

                        if (enclosedAnnotationsCount < 2)
                        {
                            @synchronized (_annotations)
                            {
                                [someArray addObjectsFromArray:enclosedAnnotations];
                                [someArray addObjectsFromArray:[self unclusteredAnnotations]];
                            }

                            return;
                        }

                        RMProjectedPoint clusterMarkerPosition;

                        if (findGravityCenter)
                        {
                            double averageX = 0.0, averageY = 0.0;

                            for (RMAnnotation *annotation in enclosedAnnotations)
                            {
                                averageX += annotation.projectedLocation.x;
                                averageY += annotation.projectedLocation.y;
                            }

                            averageX /= (double)enclosedAnnotationsCount;
                            averageY /= (double)enclosedAnnotationsCount;

                            double halfClusterMarkerWidth = clusterMarkerSize.width / 2.0,
                                   halfClusterMarkerHeight = clusterMarkerSize.height / 2.0;

                            if (averageX - halfClusterMarkerWidth < _boundingBox.origin.x)
                                averageX = _boundingBox.origin.x + halfClusterMarkerWidth;
                            if (averageX + halfClusterMarkerWidth > _boundingBox.origin.x + _boundingBox.size.width)
                                averageX = _boundingBox.origin.x + _boundingBox.size.width - halfClusterMarkerWidth;
                            if (averageY - halfClusterMarkerHeight < _boundingBox.origin.y)
                                averageY = _boundingBox.origin.y + halfClusterMarkerHeight;
                            if (averageY + halfClusterMarkerHeight > _boundingBox.origin.y + _boundingBox.size.height)
                                averageY = _boundingBox.origin.y + _boundingBox.size.height - halfClusterMarkerHeight;

                            // TODO: anchorPoint
                            clusterMarkerPosition = RMProjectedPointMake(averageX, averageY);
                        }
                        else
                        {
                            clusterMarkerPosition = RMProjectedPointMake(_boundingBox.origin.x + halfWidth, _boundingBox.origin.y + (_boundingBox.size.height / 2.0));
                        }

                        CLLocationCoordinate2D clusterMarkerCoordinate = [[_mapView projection] projectedPointToCoordinate:clusterMarkerPosition];

                        _cachedClusterAnnotation = [[RMAnnotation alloc] initWithMapView:_mapView
                                                                             coordinate:clusterMarkerCoordinate
                                                                               andTitle:[NSString stringWithFormat:@"%lu", (unsigned long)enclosedAnnotationsCount]];
                        _cachedClusterAnnotation.isClusterAnnotation = YES;
                        _cachedClusterAnnotation.userInfo = self;

                        _cachedClusterEnclosedAnnotations = [[NSArray alloc] initWithArray:enclosedAnnotations];
                    }

                    [someArray addObject:_cachedClusterAnnotation];
                    [someArray addObjectsFromArray:[self unclusteredAnnotations]];
                }
            }
            return;
        }

        if (_nodeType == nodeTypeLeaf)
        {
            @synchronized (_annotations)
            {
                [someArray addObjectsFromArray:_annotations];
            }

            return;
        }
    }
    else
    {
        if (_nodeType == nodeTypeLeaf)
        {
            @synchronized (_annotations)
            {
                [someArray addObjectsFromArray:_annotations];
            }

            return;
        }
    }

    if (RMProjectedRectIntersectsProjectedRect(aBoundingBox, _northWestBoundingBox))
        [_northWest addAnnotationsInBoundingBox:aBoundingBox toMutableArray:someArray createClusterAnnotations:createClusterAnnotations withProjectedClusterSize:clusterSize andProjectedClusterMarkerSize:clusterMarkerSize findGravityCenter:findGravityCenter];
    if (RMProjectedRectIntersectsProjectedRect(aBoundingBox, _northEastBoundingBox))
        [_northEast addAnnotationsInBoundingBox:aBoundingBox toMutableArray:someArray createClusterAnnotations:createClusterAnnotations withProjectedClusterSize:clusterSize andProjectedClusterMarkerSize:clusterMarkerSize findGravityCenter:findGravityCenter];
    if (RMProjectedRectIntersectsProjectedRect(aBoundingBox, _southWestBoundingBox))
        [_southWest addAnnotationsInBoundingBox:aBoundingBox toMutableArray:someArray createClusterAnnotations:createClusterAnnotations withProjectedClusterSize:clusterSize andProjectedClusterMarkerSize:clusterMarkerSize findGravityCenter:findGravityCenter];
    if (RMProjectedRectIntersectsProjectedRect(aBoundingBox, _southEastBoundingBox))
        [_southEast addAnnotationsInBoundingBox:aBoundingBox toMutableArray:someArray createClusterAnnotations:createClusterAnnotations withProjectedClusterSize:clusterSize andProjectedClusterMarkerSize:clusterMarkerSize findGravityCenter:findGravityCenter];

    @synchronized (_annotations)
    {
        for (RMAnnotation *annotation in _annotations)
        {
            if (RMProjectedRectIntersectsProjectedRect(aBoundingBox, annotation.projectedBoundingBox))
                [someArray addObject:annotation];
        }
    }
}