选择距离最小的随机GPS点[关闭]

Question

I want to write a php program to select 16 random gps points from 400 points in my database

(point table : id - Title - latitude - longitude ).

lat 37.9824
lon -87.5781547

The only requirement 16 random points, each of which is at least 1km from each other point ( find the points that are in 1KM range )

it is a system that selects pharmacies with a minimum distance of 1 km between each pharmacy. I have 400 pharmacies in the database and every week I must select 16 pharmacies. I can not select two pharmacies very close.

example :

if the program return 3 pharmacies A B and C .

the ditance between pharmacies must be :

A and B = 1 KM

A and C = 1 KM

B and C = 1 KM

Answer 1

Let's try that the hard way, since you have only 400 records, It might only take a few hours ... Havn't tried it, but it might give you an idea

$min =1;
$n =16;

$pharmas = fillUp();

// main function 
function fillUp(){
   $points = array();
   while(count($points)< $n){
      $tmp = getRandomPoint();
      if(checkAll($tmp, $points){
         $points[] = $tmp;
      }
}
return $points;  // after a few hours ??
 }

// get a random point
// after all we might get lucky
function getRandomPoint(){
//...
// return array with ['latitude'] & ['longitude']
}

// check that all points meet the requirements
function checkAll($pt, $points){
    foreach($points as $point){
         if(distance($point, $pt) < $min {
              return false;
          }
    }
    return true;
}

// calculate the distance between 2 points
function distance ($point1, $point2, $uom='km') {
    //  Use Haversine formula to calculate the great circle distance
    //      between two points identified by longitude and latitude
    switch (strtolower($uom)) {
        case 'km' :
            $earthMeanRadius = 6371.009; // km
            break;
        case 'm' :
            $earthMeanRadius = 6371.009 * 1000; // km
            break;
        case 'miles' :
            $earthMeanRadius = 3958.761; // miles
            break;
        case 'yards' :
        case 'yds' :
            $earthMeanRadius = 3958.761 * 1760; // miles
            break;
        case 'feet' :
        case 'ft' :
            $earthMeanRadius = 3958.761 * 1760 * 3; // miles
            break;
        case 'nm' :
            $earthMeanRadius = 3440.069; // miles
            break;
    }
    $deltaLatitude = deg2rad($point2['latitude'] - $point1['latitude']);
    $deltaLongitude = deg2rad($point2['longitude'] - $point1['longitude']);
    $a = sin($deltaLatitude / 2) * sin($deltaLatitude / 2) +
            cos(deg2rad($point1['latitude'])) * cos(deg2rad($point2['latitude'])) *
            sin($deltaLongitude / 2) * sin($deltaLongitude / 2);
    $c = 2 * atan2(sqrt($a), sqrt(1 - $a));
    $distance = $earthMeanRadius * $c;
    return $distance;
}