选择距离最小的随机GPS点

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

我想编写一个php程序，从我的数据库中的400个点中选择16个随机gps点

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

（点表：id - 标题 - 纬度 - 经度）。

lat 37.9824
lon -87.5781547

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 )

唯一要求16个随机点，每个点距离彼此至少1km（找到1KM范围内的点）

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.

它是一个选择每个药房之间最小距离为1公里的药房的系统。我在数据库中有400家药店，每周我必须选择16家药店。我不能非常接近选择两家药店。

example :

例子：

if the program return 3 pharmacies A B and C .

如果该计划返回3个药房A B和C.

the ditance between pharmacies must be :

药房之间的差异必须是：

A and B = 1 KM

A和B = 1公里

A and C = 1 KM

A和C = 1 KM

B and C = 1 KM

B和C = 1 KM

2 个解决方案

#1

An off the hat answer here:

这里有一个回答：

I would first create a view with the list of objects that are as close to the point you are interested in using the Cartesian distance formula and then apply PHP code to calculate the actual spherical distance.

我首先使用笛卡尔距离公式创建一个视图，其中的对象列表与您感兴趣的点相近，然后应用PHP代码来计算实际的球面距离。

@MY_LAT = 37.9824;
@MY_LONG = -87.5781547;

SELECT *, SQRT(
              ABS((latitude - @MY_LAT) * (latitude - @MY_LAT) + 
                  (longitude - @MY_LONG) * (longitude - @MY_LONG))) 
          AS DIST
FROM POINT_TABLE
ORDER BY DIST ASC

Select the top n rows from this view to get the closest 16 points from your 'point of interest'. To check if the points are within 1 KM of your point of reference you could write a small PHP snippet after you get the results. This should help you with the snippet:

从此视图中选择前n行，以从您的“兴趣点”获得最接近的16个点。要检查点是否在您的参考点1公里范围内，您可以在得到结果后编写一个小的PHP片段。这应该可以帮助你解决这个问题：

http://www.zipcodeworld.com/samples/distance.php.html

Here, I am using a Cartesian distance formula in the query which only serves the purpose of reducing the number of records you get to apply the spherical distance formula in PHP.x

在这里，我在查询中使用笛卡尔距离公式，仅用于减少在PHP.x中应用球面距离公式的记录数量。

#2

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

让我们努力尝试，因为你只有400条记录，它可能只需要几个小时...但是没有尝试过，但它可能会给你一个想法

$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;
}

#1