itsbonczek/kingpin — pull request #26 by stanislaw (2014-03-22 01:13:54+00:00)
Title: Relaxed implementation of mergeOverlappingClusters

This pull request is based on previous pull requests: #21, #22, #23, #24, #25 and fullfils the third of my promises, the one about improving `mergeOverlappingClusters`:

> 1) I want eliminate these two large similar sections of buildTree() by writing a one instead, but the one without "X or Y" branching.
2) I want to reduce a number of malloc-allocations of temporary arrays even further to make a process of building of a tree a bit more faster.
3) Work on _mergeOverlappingClusters to back out of all these convertCoordinate and CGRect-based calculations. Strong knowledge of zooms and zoom scales described here: http://troybrant.net/blog/2010/01/mkmapview-and-zoom-levels-a-visual-guide/ promises to be extremely helpful to this issue - I just need to understand it better than I currently do. If I succeed on this, you will never need to make this step optional at all by disabling it by configuration flag - it might become unnoticeable when written efficiently. Hopefully, I will come up with this.

Performance results are very good:

for 20000 annotations on iPhone 4 (2010) I don't have any problems with `_mergeOverlappingClusters` method itself - now this method takes 150ms at maximum (usually 10-40ms) and has at maximum ar. 500 loop iterations, while the previous (current master's) implementation had 500 000 - 1 000 000 - 1 500 000 on viewports fully covered with clusters (the worst I saw was 2 300 000 OMG iterations) and could take up to tens of seconds depending on distribution of clusters. Now we can consider `_mergeOverlappingClusters` method to be performance-safe. The next bottleneck is the code about `oldClusters + animations` - having it disabled I see pretty decent results for 20 000, even 100 000 annotations on iPhone 4.

The two things are very important now:

1) Is it all clear with the current implementation of mergeOverlappingClusters or should I annotate the code with even more explanatory comments?
2) The current clustering code quite begs for refactoring: there is an obvious need for some class like KPClusteringDriver or KPClusterizer or {you name it}... which would encapsulate the clustering code of `-_updateVisibileMapAnnotationsOnMapView` and `-_mergeOverlappingClusters` away from KPTreeController. I didn't make such change myself because I think it is up to you to decide how it should be done.

Now I am going to wait for your review of these changes (actually all sequence: #21-#26).

__P.S.__ I still have even more ideas about kingpin, but I believe I need to get all these 21-26 prs merged, because these next steps: 1) are unrelated to current changes, but will like to have them merged 2) will require changing overall kingpin design which I think is really a next story after we finalize current work.