Weighted midpoint calculation for N geographical points

[jbnewell]

I'm trying to do this in PHP, and can't find a mathematical function to do this directly.

I have a class 'cluster' that contains a group of users that are close to each other geographically. I'm treating them like circles on the earth (ellipses, in reality probably). There's a 1:1 user:cluster ratio to start, each user gets their own.

I iterate through them, checking each one for overlaps (throwing out the more obviously distant points before I get to the more intensive calculations), and if they do overlap I merge the clusters, which entails adding the areas, and finding the new midpoint.

This isn't too complicated with 2 points (midpoint() below), but I'm having some trouble wrapping my head around what's involved when one cluster (or both) have multiple users. A N user cluster merging with a 1 user cluster should have it's midpoint count N times in the calculation.

I've got a little bit of recursive code that I believe handles this case, but I'm hoping there's a more efficient way to pull this off. I'm not entirely sure I've got the logic right either. It falls apart if I'm merging an X user cell with a Y user cell too, how could I handle that? Can I just subtract the two user counts, and if it's negative treat cell 2 as cell 1 in the functions below?

Here what I've got:

public function getCentroid() {
$counter = 0;
$points = array();
foreach ($this->cells as $cell) {
for ($x = 0; $x <= $cell->users; $x++) {
$points[$counter] = array('lat' => $cell->lat, 'lng' => $cell->lng);
$counter++;
}
}

$mp = array_shift($points);
$this->mpWeight++;
foreach ($points as $point) {
$p = $this->centroid($mp, $point, $this->mpWeight);
}
return $p;
}

private function centroid($p1, $p2, $p1Weight) {
if ($p1Weight == 1) {
return $this->midpoint($p1, $p2);
} else {
return $this->centroid($p1, $this->midpoint($p1, $p2), $p1Weight - 1);
}
}

private function midpoint($p1, $p2) {
if (($p1['lat'] == $p2['lat']) && ($p1['lng'] == $p2['lng'])){
return array('lat' => $p1['lat'], 'lng' => $p1['lng']);
}
$delta_lat = (deg2rad($p2['lat']) - deg2rad($p1['lat']));
$delta_lng = (deg2rad($p2['lng']) - deg2rad($p1['lng']));

$bx = cos(deg2rad($p2['lat'])) * cos($delta_lng);
$by = cos(deg2rad($p2['lat'])) * sin($delta_lng);

$rLat = rad2deg(atan2(sin(deg2rad($p1['lat']))+sin(deg2rad($p2['lat'])),
sqrt((cos(deg2rad($p1['lat']))+$bx)*(cos(deg2rad($p1['lat']))+$bx) + $by*$by)));
$rLng = $p1['lng'] + rad2deg(atan2($by, cos($p1['lat']) + $bx));
return array('lat' => $rLat, 'lng' => $rLng);
}

Any pointers? Thanks.

[jbnewell]

By the way, the distance between points that are clustered together should really only be a couple of miles at absolute maximum.
It's not for an engineering/mapping/etc application, so if the result is off by a couple of feet, it doesn't really matter.

Is this method serious overkill? Would I be ok doing my distance and midpoint calculations with just simple geometry? Is there some issue with that that I'm missing, where results would be seriously impacted?