Cluster position changes every time when clustermanager.cluster() is called

[burhanshakir]

Environment details

1. API : Maps Utils
2. OS : >= Android M
3. Library version : 0.6.1

Code Example

private fun displayClusterItems(items: List<ClusterItem>) {
    clusterManager.clearItems()
    clusterManager.addItems(items)
    clusterManager.cluster()
}

Whenever I call the displayClusterItems() and pass in the exact same items, there is a change in the cluster positions. The zoom position is same as well.

Why are the cluster position changing even though the items being passed are same in the same order with the same location data ?

[barbeau]

I'm able to reproduce this in this branch:
https://github.com/CUTR-at-USF/android-maps-utils/tree/test-recluster-change

I modified ClusteringDemoActivity to update the item titles every second. When it does a deep-copy of the list, the clusters/markers change position every second. even though it's otherwise the same items in the same order with same positions.

I'm guessing this is a side-effect of changing from an ArrayList to a HashSet in #368.

NonHierarchicalDistanceBasedAlgorithm says:

1. Iterate over items in the order they were added (candidate clusters).
   ...
   Clusters have the center of the first element (not the centroid of the items within it).

ArrayLists maintain insertion order of the elements when iterating over them later, while HashSets do not. Because the cluster has the center of the first element, that center will change if the iteration order of the elements change.

A possible fix is to switch to using LinkedHashSet, which should give the same constant time performance benefits as the Set for add/remove over the List, but still maintains insertion order.

[barbeau]

PR at #624