基于Zipcode和Ranges Within创建用户团队算法

Question

In my application we have teams of users based on their location (zipcode) and then an encompassing radius of 100 miles (zipcodes within) to operate with.

My problem is: user one signs up and is designated a team based on his zipcode and the radius encompassing it. when user two signs up, and he has a zipcode that is let's say within the radius of the first users team, then we are supposed to assign him to that same team. However, the second user has a radius that exceeds the teams assigned radius because he is operating within his zipcode, not user A.

So, the problem becomes that right now we need to create a new team for each zipcode to ensure that every user in that team has the correct radius. This is not a solution though. We cannot have a new team for every zipcode.

My first thought was to create teams based on regions containing zipcodes and then just assign the user to that team since they're zipcode is in the region. I do not like this thought though.

Any help would be appreciated. This is a very difficult algorithm for me so please take the time to explain as simple as possible so I can clearly understand your solution.

Answer 1

Given that you know how to resolve a Zip Code to a pair of coordinates (using Google Maps API for example) the problem is to find N teams having at least one user each. and where the distance between any 2 users within the same team is less than or equals 100 miles.

You could use a distance-based clustering algorithm to cluster users into the smallest number of teams (that's what you intuitively thought of as 'regions')

It's like creating one team per user, then iteratively removing a team at a time, reassigning its users to existing teams, until you can't remove a team because you'd break the 100 miles rule (or a more sophisticated rule as your application evolves).

You'll find a PHP implementation here (this one converts miles to pixels, but you can easily modify it) http://rtsoftwaregroup.io/server-side-google-map-markers-clustering/

More theory here http://www.cs.colostate.edu/~cs545/fall13/dokuwiki/lib/exe/fetch.php?media=wiki:12_clustering.pdf

And a very useful question about optimizing (and scaling) it: Map Clustering Algorithm