132 lines
3.9 KiB
PHP
132 lines
3.9 KiB
PHP
<?php
|
|
|
|
namespace App\Helpers;
|
|
|
|
class GeoHelper
|
|
{
|
|
/**
|
|
* Calculate distance between two coordinates using Haversine formula
|
|
*
|
|
* @param float $lat1 Latitude of point 1
|
|
* @param float $lng1 Longitude of point 1
|
|
* @param float $lat2 Latitude of point 2
|
|
* @param float $lng2 Longitude of point 2
|
|
* @return float Distance in kilometers
|
|
*/
|
|
public static function haversineDistance(float $lat1, float $lng1, float $lat2, float $lng2): float
|
|
{
|
|
$R = 6371; // Earth's radius in km
|
|
|
|
$dLat = deg2rad($lat2 - $lat1);
|
|
$dLng = deg2rad($lng2 - $lng1);
|
|
|
|
$a = sin($dLat / 2) * sin($dLat / 2) +
|
|
cos(deg2rad($lat1)) * cos(deg2rad($lat2)) *
|
|
sin($dLng / 2) * sin($dLng / 2);
|
|
|
|
$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
|
|
|
|
return $R * $c;
|
|
}
|
|
|
|
/**
|
|
* Optimize route using Nearest Neighbor algorithm
|
|
*
|
|
* @param array $targets Array of targets with lat/lng properties
|
|
* @return array ['order' => array, 'totalDistance' => float]
|
|
*/
|
|
public static function optimizeRouteNearestNeighbor(array $targets): array
|
|
{
|
|
$n = count($targets);
|
|
|
|
if ($n <= 2) {
|
|
$totalDistance = 0;
|
|
if ($n === 2) {
|
|
$totalDistance = self::haversineDistance(
|
|
$targets[0]['latitude'] ?? $targets[0]['lat'],
|
|
$targets[0]['longitude'] ?? $targets[0]['lng'],
|
|
$targets[1]['latitude'] ?? $targets[1]['lat'],
|
|
$targets[1]['longitude'] ?? $targets[1]['lng']
|
|
);
|
|
}
|
|
return [
|
|
'order' => array_keys($targets),
|
|
'totalDistance' => round($totalDistance, 2)
|
|
];
|
|
}
|
|
|
|
$visited = array_fill(0, $n, false);
|
|
$route = [];
|
|
$totalDistance = 0;
|
|
|
|
// Start from first target
|
|
$current = 0;
|
|
$visited[$current] = true;
|
|
$route[] = $current;
|
|
|
|
// Find nearest unvisited neighbor
|
|
for ($i = 1; $i < $n; $i++) {
|
|
$nearest = -1;
|
|
$minDist = PHP_FLOAT_MAX;
|
|
|
|
$currentLat = $targets[$current]['latitude'] ?? $targets[$current]['lat'];
|
|
$currentLng = $targets[$current]['longitude'] ?? $targets[$current]['lng'];
|
|
|
|
for ($j = 0; $j < $n; $j++) {
|
|
if (!$visited[$j]) {
|
|
$targetLat = $targets[$j]['latitude'] ?? $targets[$j]['lat'];
|
|
$targetLng = $targets[$j]['longitude'] ?? $targets[$j]['lng'];
|
|
|
|
$dist = self::haversineDistance($currentLat, $currentLng, $targetLat, $targetLng);
|
|
|
|
if ($dist < $minDist) {
|
|
$minDist = $dist;
|
|
$nearest = $j;
|
|
}
|
|
}
|
|
}
|
|
|
|
if ($nearest !== -1) {
|
|
$visited[$nearest] = true;
|
|
$route[] = $nearest;
|
|
$totalDistance += $minDist;
|
|
$current = $nearest;
|
|
}
|
|
}
|
|
|
|
return [
|
|
'order' => $route,
|
|
'totalDistance' => round($totalDistance, 2)
|
|
];
|
|
}
|
|
|
|
/**
|
|
* Calculate total distance of a route
|
|
*
|
|
* @param array $targets Array of targets in order
|
|
* @return float Total distance in kilometers
|
|
*/
|
|
public static function calculateRouteDistance(array $targets): float
|
|
{
|
|
if (count($targets) < 2) {
|
|
return 0;
|
|
}
|
|
|
|
$totalDistance = 0;
|
|
|
|
for ($i = 0; $i < count($targets) - 1; $i++) {
|
|
$t1 = $targets[$i];
|
|
$t2 = $targets[$i + 1];
|
|
|
|
$totalDistance += self::haversineDistance(
|
|
$t1['latitude'] ?? $t1['lat'],
|
|
$t1['longitude'] ?? $t1['lng'],
|
|
$t2['latitude'] ?? $t2['lat'],
|
|
$t2['longitude'] ?? $t2['lng']
|
|
);
|
|
}
|
|
|
|
return round($totalDistance, 2);
|
|
}
|
|
}
|