<?php

class OptimizedFlightPathGenerator
{
    private $startPoint;
    private $points;
    private $noFlyZone;
    private $highVoltage;
    
    // 地球半径（米）
    const EARTH_RADIUS = 6371000;
    
    public function __construct($flightInput)
    {
        $this->startPoint = $flightInput['start_point'];
        $this->points = $flightInput['points'];
        $this->noFlyZone = $flightInput['no_fly_zone'];
        $this->highVoltage = $flightInput['high_voltage'];
    }
    
    /**
     * 生成优化的航线路径
     */
    public function generateOptimizedFlightPath()
    {
        // 使用凸包算法找到外围点，然后填充内部点
        $optimizedPath = $this->generateEfficientPath();
        
        // 检查并处理禁飞区相交 - 使用新的避让算法
        $pathAfterNoFly = $this->handleNoFlyZoneIntersectionsNew($optimizedPath);
        
        // 检查并处理高压线相交
        $finalPath = $this->handleHighVoltageIntersections($pathAfterNoFly);
        
        return $finalPath;
    }
    
    /**
     * 新的禁飞区相交处理方法 - 生成中间点并向外移动
     */
    private function handleNoFlyZoneIntersectionsNew($path)
    {
        $maxIterations = 10; // 最大迭代次数，防止无限循环
        $iteration = 0;
        
        do {
            $hasIntersection = false;
            $newPath = [];
            // echo '--aaaaaaaa-'.PHP_EOL;
            for ($i = 0; $i < count($path) - 1; $i++) {
                $currentPoint = $path[$i];
                $nextPoint = $path[$i + 1];
                
                // 检查当前线段是否与禁飞区相交
                $intersections = $this->checkLineCircleIntersection(
                    $currentPoint, 
                    $nextPoint, 
                    $this->noFlyZone['center'], 
                    $this->noFlyZone['radius']+50
                );
                // var_dump($intersections);
                
                if (!empty($intersections)) {
                    // 发现相交，生成中间点并向外移动
                    $hasIntersection = true;
                    
                    // 计算两个航点的中间点
                    $midPoint = $this->calculateMidpoint($currentPoint, $nextPoint);
                    //  var_dump($intersections);
                    // 将中间点向外移动到禁飞区外100米
                    $safePoint = $this->movePointAwayFromNoFlyZone($midPoint, 150);
                    
                    // 添加安全点到路径
                    $newPath[] = $currentPoint;
                    $newPath[] = [
                        'name' => '禁飞区避让点',
                        'lng' => $safePoint['lng'],
                        'lat' => $safePoint['lat'],
                        'type' => 'no_fly_zone_avoidance'
                    ];
                    // 不添加nextPoint，因为它会在下一次循环中作为currentPoint处理
                } else {
                    // 没有相交，保持原路径点
                    $newPath[] = $currentPoint;
                    
                    // 如果是最后一个点，也要添加
                    if ($i == count($path) - 2) {
                        $newPath[] = $nextPoint;
                    }
                }
            }
            
            $path = $newPath;
            $iteration++;
            
        } while ($hasIntersection && $iteration < $maxIterations);
        
        // if ($iteration >= $maxIterations) {
        //     echo "警告: 达到最大迭代次数，可能仍有禁飞区相交\n";
        // }
        
        return $path;
    }
    
    /**
     * 计算两个点的中间点
     */
    private function calculateMidpoint($point1, $point2)
    {
        return [
            'lng' => ($point1['lng'] + $point2['lng']) / 2,
            'lat' => ($point1['lat'] + $point2['lat']) / 2
        ];
    }
    
    /**
     * 将点从禁飞区中心向外移动指定距离
     */
    private function movePointAwayFromNoFlyZone($point, $safeDistance)
    {
        $center = $this->noFlyZone['center'];
        $radius = $this->noFlyZone['radius'];
        
        // 计算点到禁飞区中心的距离
        $distanceToCenter = $this->calculateDistance($point, $center);
        
        if ($distanceToCenter <= $radius + $safeDistance) {
            // 计算从禁飞区中心指向点的方向向量
            $dx = $point['lng'] - $center['lng'];
            $dy = $point['lat'] - $center['lat'];
            
            // 计算方向向量的长度
            $vectorLength = sqrt($dx * $dx + $dy * $dy);
            
            if ($vectorLength > 0) {
                // 归一化方向向量
                $dx /= $vectorLength;
                $dy /= $vectorLength;
                
                // 计算需要移动的总距离（从当前位置移动到禁飞区外safeDistance米）
                $moveDistance = $radius + $safeDistance - $distanceToCenter;
                
                // 计算新的点位置
                $newLng = $point['lng'] + $dx * $moveDistance * 0.00001; // 调整缩放因子
                $newLat = $point['lat'] + $dy * $moveDistance * 0.00001;
                
                return [
                    'lng' => $newLng,
                    'lat' => $newLat
                ];
            }
        }
        
        // 如果已经在安全距离外，返回原點
        return $point;
    }
    
    // 以下是原有的方法，保持不变
    private function generateEfficientPath()
    {
        if (count($this->points) <= 2) {
            return $this->nearestNeighborPath();
        }
        
        $center = $this->calculateCenter($this->points);
        $sortedPoints = $this->sortPointsByAngle($this->points, $center);
        $path = $this->improvedNearestInsertion($sortedPoints);
        
        $fullPath = [$this->startPoint];
        foreach ($path as $point) {
            $fullPath[] = $point;
        }
        $fullPath[] = $this->startPoint;
        
        return $fullPath;
    }
    
    private function calculateCenter($points)
    {
        $totalLng = 0;
        $totalLat = 0;
        $count = count($points);
        
        foreach ($points as $point) {
            $totalLng += $point['lng'];
            $totalLat += $point['lat'];
        }
        
        return [
            'lng' => $totalLng / $count,
            'lat' => $totalLat / $count
        ];
    }
    
    private function sortPointsByAngle($points, $center)
    {
        $angles = [];
        
        foreach ($points as $index => $point) {
            $angle = atan2(
                $point['lat'] - $center['lat'],
                $point['lng'] - $center['lng']
            );
            $angles[$index] = $angle;
        }
        
        asort($angles);
        
        $sortedPoints = [];
        foreach ($angles as $index => $angle) {
            $sortedPoints[] = $points[$index];
        }
        
        return $sortedPoints;
    }
    
    private function improvedNearestInsertion($points)
    {
        if (empty($points)) {
            return [];
        }
        
        $firstPointIndex = $this->findNearestPoint($this->startPoint, $points);
        $path = [$points[$firstPointIndex]];
        $remainingPoints = $points;
        unset($remainingPoints[$firstPointIndex]);
        $remainingPoints = array_values($remainingPoints);
        
        while (!empty($remainingPoints)) {
            $bestPointIndex = null;
            $bestPosition = null;
            $minIncrease = PHP_FLOAT_MAX;
            
            foreach ($remainingPoints as $pointIndex => $point) {
                for ($i = 0; $i <= count($path); $i++) {
                    $increase = $this->calculateInsertionCost($path, $point, $i);
                    
                    if ($increase < $minIncrease) {
                        $minIncrease = $increase;
                        $bestPointIndex = $pointIndex;
                        $bestPosition = $i;
                    }
                }
            }
            
            array_splice($path, $bestPosition, 0, [$remainingPoints[$bestPointIndex]]);
            unset($remainingPoints[$bestPointIndex]);
            $remainingPoints = array_values($remainingPoints);
        }
        
        return $path;
    }
    
    private function calculateInsertionCost($path, $point, $position)
    {
        if (empty($path)) {
            return 0;
        }
        
        if ($position == 0) {
            return $this->calculateDistance($this->startPoint, $point) +
                   $this->calculateDistance($point, $path[0]) -
                   $this->calculateDistance($this->startPoint, $path[0]);
        } elseif ($position == count($path)) {
            return $this->calculateDistance($path[count($path)-1], $point) +
                   $this->calculateDistance($point, $this->startPoint) -
                   $this->calculateDistance($path[count($path)-1], $this->startPoint);
        } else {
            return $this->calculateDistance($path[$position-1], $point) +
                   $this->calculateDistance($point, $path[$position]) -
                   $this->calculateDistance($path[$position-1], $path[$position]);
        }
    }
    
    private function nearestNeighborPath()
    {
        $unvisited = $this->points;
        $currentPoint = $this->startPoint;
        $path = [$currentPoint];
        
        while (!empty($unvisited)) {
            $nearestIndex = $this->findNearestPoint($currentPoint, $unvisited);
            $nearestPoint = $unvisited[$nearestIndex];
            
            $path[] = $nearestPoint;
            $currentPoint = $nearestPoint;
            
            array_splice($unvisited, $nearestIndex, 1);
        }
        
        $path[] = $this->startPoint;
        
        return $path;
    }
    
    private function findNearestPoint($currentPoint, $points)
    {
        $minDistance = PHP_FLOAT_MAX;
        $nearestIndex = 0;
        
        foreach ($points as $index => $point) {
            $distance = $this->calculateDistance($currentPoint, $point);
            if ($distance < $minDistance) {
                $minDistance = $distance;
                $nearestIndex = $index;
            }
        }
        
        return $nearestIndex;
    }
    
    /**
     * 原有的禁飞区处理方法（保留用于参考）
     */
    private function handleNoFlyZoneIntersections($path)
    {
        $finalPath = [];
        
        for ($i = 0; $i < count($path) - 1; $i++) {
            $currentPoint = $path[$i];
            $nextPoint = $path[$i + 1];
            
            $finalPath[] = $currentPoint;
            
            $intersections = $this->checkLineCircleIntersection(
                $currentPoint, 
                $nextPoint, 
                $this->noFlyZone['center'], 
                $this->noFlyZone['radius']
            );
            
            if (!empty($intersections)) {
                foreach ($intersections as $intersection) {
                    $finalPath[] = [
                        'name' => '禁飞区相交点',
                        'lng' => $intersection['lng'],
                        'lat' => $intersection['lat'],
                        'type' => 'no_fly_zone_intersection'
                    ];
                }
            }
        }
        
        $finalPath[] = $path[count($path) - 1];
        
        return $finalPath;
    }
    
    private function handleHighVoltageIntersections($path)
    {
        $finalPath = [];
        
        for ($i = 0; $i < count($path) - 1; $i++) {
            $currentPoint = $path[$i];
            $nextPoint = $path[$i + 1];
            
            $finalPath[] = $currentPoint;
            
            $intersections = $this->checkHighVoltageIntersections(
                $currentPoint, 
                $nextPoint
            );
            
            if (!empty($intersections)) {
                foreach ($intersections as $intersection) {
                    $finalPath[] = [
                        'name' => '高压线相交点',
                        'lng' => $intersection['lng'],
                        'lat' => $intersection['lat'],
                        'type' => 'high_voltage_intersection',
                        'tower1' => $intersection['tower1'],
                        'tower2' => $intersection['tower2']
                    ];
                }
            }
        }
        
        $finalPath[] = $path[count($path) - 1];
        
        return $finalPath;
    }
    
    private function checkHighVoltageIntersections($pointA, $pointB)
    {
        $intersections = [];
        $towers = $this->highVoltage['towers'];
        
        for ($i = 0; $i < count($towers) - 1; $i++) {
            $tower1 = $towers[$i];
            $tower2 = $towers[$i + 1];
            
            $intersection = $this->checkLineSegmentIntersection(
                $pointA, $pointB, $tower1, $tower2
            );
            
            if ($intersection !== null) {
                $intersections[] = [
                    'lng' => $intersection['lng'],
                    'lat' => $intersection['lat'],
                    'tower1' => $tower1,
                    'tower2' => $tower2
                ];
            }
        }
        
        return $intersections;
    }
    
    private function checkLineSegmentIntersection($line1A, $line1B, $line2A, $line2B)
    {
        $p1 = $this->latLngToMeters($line1A['lat'], $line1A['lng']);
        $p2 = $this->latLngToMeters($line1B['lat'], $line1B['lng']);
        $p3 = $this->latLngToMeters($line2A['lat'], $line2A['lng']);
        $p4 = $this->latLngToMeters($line2B['lat'], $line2B['lng']);
        
        $denominator = (($p4[1] - $p3[1]) * ($p2[0] - $p1[0]) - ($p4[0] - $p3[0]) * ($p2[1] - $p1[1]));
        
        if ($denominator == 0) {
            return null;
        }
        
        $ua = (($p4[0] - $p3[0]) * ($p1[1] - $p3[1]) - ($p4[1] - $p3[1]) * ($p1[0] - $p3[0])) / $denominator;
        $ub = (($p2[0] - $p1[0]) * ($p1[1] - $p3[1]) - ($p2[1] - $p1[1]) * ($p1[0] - $p3[0])) / $denominator;
        
        if ($ua >= 0 && $ua <= 1 && $ub >= 0 && $ub <= 1) {
            $x = $p1[0] + $ua * ($p2[0] - $p1[0]);
            $y = $p1[1] + $ua * ($p2[1] - $p1[1]);
            
            $latLng = $this->metersToLatLng($x, $y);
            
            return [
                'lng' => $latLng['lng'],
                'lat' => $latLng['lat']
            ];
        }
        
        return null;
    }
    
    
   /**
 * 检测线段与圆是否相交并返回交点坐标
 * @param array $pointA 线段端点A，包含lat和lng键
 * @param array $pointB 线段端点B，包含lat和lng键  
 * @param array $circleCenter 圆心坐标，包含lat和lng键
 * @param float $radius 圆的半径（米）
 * @return array 交点坐标数组，每个元素包含lat和lng键
 */
function checkLineCircleIntersection($pointA, $pointB, $circleCenter, $radius)
{
    $intersections = [];
    $earthRadius = 6378137; // 地球半径（米）
    $epsilon = 1e-12; // 容差
    
    // 度转弧度
    function toRadians($deg) {
        return $deg * M_PI / 180;
    }
    
    // 弧度转度
    function toDegrees($rad) {
        return $rad * 180 / M_PI;
    }
    
    // Haversine公式计算两点间距离（米）[1,3,5](@ref)
    function getDistanceFromLatLng($lat1, $lng1, $lat2, $lng2) {
        global $earthRadius;
        
        $φ1 = toRadians($lat1);
        $φ2 = toRadians($lat2);
        $Δφ = toRadians($lat2 - $lat1);
        $Δλ = toRadians($lng2 - $lng1);
        
        $a = sin($Δφ/2) * sin($Δφ/2) +
             cos($φ1) * cos($φ2) *
             sin($Δλ/2) * sin($Δλ/2);
        $c = 2 * atan2(sqrt($a), sqrt(1-$a));
        return $earthRadius * $c;
    }
    
    // 经纬度转墨卡托米坐标
    function latLngToMeters($lat, $lng) {
        global $earthRadius;
        
        $x = $earthRadius * toRadians($lng);
        $y = $earthRadius * log(tan(M_PI/4 + toRadians($lat)/2));
        return [$x, $y];
    }
    
    // 墨卡托米坐标转经纬度
    function metersToLatLng($x, $y) {
        global $earthRadius;
        
        $lng = ($x / $earthRadius) * 180 / M_PI;
        $lat = (2 * atan(exp($y / $earthRadius)) - M_PI/2) * 180 / M_PI;
        return [$lat, $lng];
    }
    
    // 判断点是否在圆内（用实际距离）[1](@ref)
    function isPointInCircle($point) {
        global $circleCenter, $radius, $epsilon;
        
        $dist = getDistanceFromLatLng(
            $point['lat'], $point['lng'], 
            $circleCenter['lat'], $circleCenter['lng']
        );
        return $dist <= $radius + $epsilon;
    }
    
    // 转换坐标为墨卡托米
    $A = latLngToMeters($pointA['lat'], $pointA['lng']);
    $B = latLngToMeters($pointB['lat'], $pointB['lng']);
    $C = latLngToMeters($circleCenter['lat'], $circleCenter['lng']);
    
    // 向量计算[2,7](@ref)
    $AB = [$B[0] - $A[0], $B[1] - $A[1]];
    $AC = [$C[0] - $A[0], $C[1] - $A[1]];
    $ab2 = $AB[0]**2 + $AB[1]**2;
    
    // 线段为点的情况
    if ($ab2 < $epsilon) {
        if (isPointInCircle($pointA)) {
            return [[
                'lng' => $pointA['lng'],
                'lat' => $pointA['lat']
            ]];
        }
        return [];
    }
    
    // 计算最近点参数t[2](@ref)
    $t = ($AC[0] * $AB[0] + $AC[1] * $AB[1]) / $ab2;
    $closest = [$A[0] + $t * $AB[0], $A[1] + $t * $AB[1]];
    $distToClosest = sqrt(($closest[0]-$C[0])**2 + ($closest[1]-$C[1])**2);
    
    // 判断跨圆场景[7,8](@ref)
    $isPointAIn = isPointInCircle($pointA);
    $isPointBIn = isPointInCircle($pointB);
    $isCrossing = $isPointAIn !== $isPointBIn;
    
    // 关键修复：跨圆场景强制计算交点，即使最近点在圆外
    if ($distToClosest <= $radius + $epsilon || $isCrossing) {
        $discriminant = $radius**2 - $distToClosest**2;
        $dt = $discriminant >= 0 ? sqrt($discriminant / $ab2) : 0;
        
        $t1 = $t - $dt;
        $t2 = $t + $dt;
        
        // 添加交点的辅助函数
        $addIntersection = function($tVal) use ($A, $AB, $pointA, $pointB, $circleCenter, $radius) {
            // 允许tVal在[-0.1, 1.1]范围内（补偿墨卡托误差）
            if ($tVal >= -0.1 && $tVal <= 1.1) {
                $tClamped = max(0, min(1, $tVal)); // 强制夹紧到线段上
                $x = $A[0] + $tClamped * $AB[0];
                $y = $A[1] + $tClamped * $AB[1];
                list($lat, $lng) = metersToLatLng($x, $y);
                
                // 额外验证：确保交点到圆心的实际距离≈半径（容错5米）
                $intersectionDist = getDistanceFromLatLng($lat, $lng, $circleCenter['lat'], $circleCenter['lng']);
                if (abs($intersectionDist - $radius) <= 5) {
                    return [
                        'lat' => round($lat, 6),
                        'lng' => round($lng, 6)
                    ];
                }
            }
            return null;
        };
        
        $p1 = $addIntersection($t1);
        $p2 = $addIntersection($t2);
        
        if ($p1) {
            $intersections[] = $p1;
        }
        if ($p2 && !in_array($p2, $intersections, true)) {
            $intersections[] = $p2;
        }
        
        // 跨圆场景但无交点时，手动计算线段与圆的交点（最终保障）[6](@ref)
        if ($isCrossing && empty($intersections)) {
            // 用参数方程暴力求解（t从0到1逐步计算）
            for ($tForce = 0; $tForce <= 1; $tForce += 0.001) {
                $x = $A[0] + $tForce * $AB[0];
                $y = $A[1] + $tForce * $AB[1];
                list($lat, $lng) = metersToLatLng($x, $y);
                $dist = getDistanceFromLatLng($lat, $lng, $circleCenter['lat'], $circleCenter['lng']);
                
                if (abs($dist - $radius) <= 1) { // 误差≤1米
                    $intersection = [
                        'lat' => round($lat, 6),
                        'lng' => round($lng, 6)
                    ];
                    if (!in_array($intersection, $intersections, true)) {
                        $intersections[] = $intersection;
                    }
                    break;
                }
            }
        }
    }
    
    return $intersections;
}
    
    private function latLngToMeters($lat, $lng)
    {
        $x = $lng * (M_PI / 180) * self::EARTH_RADIUS * cos($lat * M_PI / 180);
        $y = $lat * (M_PI / 180) * self::EARTH_RADIUS;
        return [$x, $y];
    }
    
    private function metersToLatLng($x, $y)
    {
        $lng = $x / (self::EARTH_RADIUS * cos($y / self::EARTH_RADIUS));
        $lat = $y / self::EARTH_RADIUS;
        
        return [
            'lng' => $lng * (180 / M_PI),
            'lat' => $lat * (180 / M_PI)
        ];
    }
    
    private function calculateDistance($point1, $point2)
    {
        $lat1 = $point1['lat'];
        $lng1 = $point1['lng'];
        $lat2 = $point2['lat'];
        $lng2 = $point2['lng'];
        
        $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 self::EARTH_RADIUS * $c;
    }
    
    public function printPathInfo($path)
    {
        echo "生成的优化航线路径:\n";
        echo "总点数: " . count($path) . "\n\n";
        
        $totalDistance = 0;
        $pathSequence = [];
        $intersectionCount = 0;
        $avoidanceCount = 0;
        
        for ($i = 0; $i < count($path); $i++) {
            $point = $path[$i];
            $name = isset($point['name']) ? $point['name'] : '起点/终点';
            $type = isset($point['type']) ? " ({$point['type']})" : "";
            
            echo ($i + 1) . ". {$name}{$type}\n";
            echo "   经度: {$point['lng']}, 纬度: {$point['lat']}\n";
            
           
        }
      
    }
    
    private function generateRandomPath()
    {
        $points = $this->points;
        shuffle($points);
        
        $path = [$this->startPoint];
        foreach ($points as $point) {
            $path[] = $point;
        }
        $path[] = $this->startPoint;
        
        return $path;
    }
    
    private function calculatePathDistance($path)
    {
        $totalDistance = 0;
        for ($i = 0; $i < count($path) - 1; $i++) {
            $totalDistance += $this->calculateDistance($path[$i], $path[$i + 1]);
        }
        return $totalDistance;
    }
    
    public function visualizePath($path)
    {
        echo "\n路径可视化:\n";
        
        $lngs = array_map(function($point) { return $point['lng']; }, $path);
        $lats = array_map(function($point) { return $point['lat']; }, $path);
        
        $minLng = min($lngs);
        $maxLng = max($lngs);
        $minLat = min($lats);
        $maxLat = max($lats);
        
        $width = 60;
        $height = 20;
        
        $grid = array_fill(0, $height, array_fill(0, $width, ' '));
        
        foreach ($path as $index => $point) {
            $x = (int)(($point['lng'] - $minLng) / ($maxLng - $minLng) * ($width - 1));
            $y = (int)(($point['lat'] - $minLat) / ($maxLat - $minLat) * ($height - 1));
            
            $char = '•';
            if ($index === 0 || $index === count($path)-1) {
                $char = 'S';
            } elseif (isset($point['type'])) {
                if ($point['type'] === 'no_fly_zone_intersection') {
                    $char = 'X';
                } elseif ($point['type'] === 'high_voltage_intersection') {
                    $char = 'H';
                } elseif ($point['type'] === 'no_fly_zone_avoidance') {
                    $char = 'A'; // 避让点
                }
            }
            
            $grid[$y][$x] = $char;
        }
        
        $cx = (int)(($this->noFlyZone['center']['lng'] - $minLng) / ($maxLng - $minLng) * ($width - 1));
        $cy = (int)(($this->noFlyZone['center']['lat'] - $minLat) / ($maxLat - $minLat) * ($height - 1));
        
        $radius = 3;
        for ($a = 0; $a < 2 * M_PI; $a += 0.1) {
            $dx = (int)($radius * cos($a));
            $dy = (int)($radius * sin($a));
            if ($cx+$dx >= 0 && $cx+$dx < $width && $cy+$dy >= 0 && $cy+$dy < $height) {
                $grid[$cy+$dy][$cx+$dx] = 'O';
            }
        }
        
        $towers = $this->highVoltage['towers'];
        for ($i = 0; $i < count($towers) - 1; $i++) {
            $tower1 = $towers[$i];
            $tower2 = $towers[$i + 1];
            
            $x1 = (int)(($tower1['lng'] - $minLng) / ($maxLng - $minLng) * ($width - 1));
            $y1 = (int)(($tower1['lat'] - $minLat) / ($maxLat - $minLat) * ($height - 1));
            $x2 = (int)(($tower2['lng'] - $minLng) / ($maxLng - $minLng) * ($width - 1));
            $y2 = (int)(($tower2['lat'] - $minLat) / ($maxLat - $minLat) * ($height - 1));
            
            $grid[$y1][$x1] = 'T';
            $grid[$y2][$x2] = 'T';
            
            $this->drawLine($grid, $x1, $y1, $x2, $y2, '=');
        }
        
        for ($y = 0; $y < $height; $y++) {
            for ($x = 0; $x < $width; $x++) {
                echo $grid[$y][$x];
            }
            echo "\n";
        }
        
        echo "\n图例: S=起点/终点, •=航点, A=禁飞区避让点, X=禁飞区相交点, H=高压线相交点, O=禁飞区边界, T=高压线塔, ===高压线\n";
    }
    
    private function drawLine(&$grid, $x1, $y1, $x2, $y2, $char)
    {
        $dx = abs($x2 - $x1);
        $dy = abs($y2 - $y1);
        $sx = ($x1 < $x2) ? 1 : -1;
        $sy = ($y1 < $y2) ? 1 : -1;
        $err = $dx - $dy;
        
        while (true) {
            if ($grid[$y1][$x1] === ' ' || $grid[$y1][$x1] === '=') {
                $grid[$y1][$x1] = $char;
            }
            
            if ($x1 == $x2 && $y1 == $y2) break;
            
            $e2 = 2 * $err;
            if ($e2 > -$dy) {
                $err -= $dy;
                $x1 += $sx;
            }
            if ($e2 < $dx) {
                $err += $dx;
                $y1 += $sy;
            }
        }
    }
}


// 使用示例
$flightInput = [
    "start_point" => ["lng" => 119.728918245, "lat" => 29.158205373],
    "points" => [
        ["name" => "航点1", "lng" => 119.731844828, "lat" => 29.155170432],
        ["name" => "航点2", "lng" => 119.734061703, "lat" => 29.157567795],
        ["name" => "航点3", "lng" => 119.731450602, "lat" => 29.163489386],
        ["name" => "航点4", "lng" => 119.727492742, "lat" => 29.165032019],
        ["name" => "航点5", "lng" => 119.727926162, "lat" => 29.162911848]
    ],
    "no_fly_zone" => [
        "center" => ["lng" => 119.729029043, "lat" => 29.161302197],
        "radius" => 200
    ],
    "high_voltage" => [
        "towers" => [
            ["lng" => 119.728687943, "lat" => 29.156864388],
            ["lng" => 119.735076462, "lat" => 29.160592962]
        ]
    ]
];

// 创建航线生成器实例
$flightGenerator = new OptimizedFlightPathGenerator($flightInput);

// 生成优化航线
$flightPath = $flightGenerator->generateOptimizedFlightPath();

// 输出航线信息
$flightGenerator->printPathInfo($flightPath);


?>