<?php
function kmeansClustering($data, $k, $maxIterations = 100) {
    $centroids = array_slice($data, 0, $k); // Ambil k titik awal sebagai centroid

    for ($iteration = 0; $iteration < $maxIterations; $iteration++) {
        $clusters = array_fill(0, $k, []);

        // Assign titik ke centroid terdekat
        foreach ($data as $point) {
            $minDist = PHP_FLOAT_MAX;
            $bestCluster = 0;
            foreach ($centroids as $index => $centroid) {
                $dist = haversineDistance($point, $centroid);
                if ($dist < $minDist) {
                    $minDist = $dist;
                    $bestCluster = $index;
                }
            }
            $clusters[$bestCluster][] = $point;
        }

        // Hitung centroid baru
        $newCentroids = [];
        foreach ($clusters as $cluster) {
            if (count($cluster) > 0) {
                $latSum = $lngSum = 0;
                foreach ($cluster as $point) {
                    $latSum += $point['lat'];
                    $lngSum += $point['lng'];
                }
                $newCentroids[] = ['lat' => $latSum / count($cluster), 'lng' => $lngSum / count($cluster)];
            } else {
                $newCentroids[] = $centroids[array_rand($centroids)];
            }
        }

        if ($centroids == $newCentroids) break; // Konvergen
        $centroids = $newCentroids;
    }
    return $centroids;
}

function haversineDistance($point1, $point2) {
    $earthRadius = 6371; // Radius bumi dalam km
    $lat1 = deg2rad($point1['lat']);
    $lng1 = deg2rad($point1['lng']);
    $lat2 = deg2rad($point2['lat']);
    $lng2 = deg2rad($point2['lng']);

    $dlat = $lat2 - $lat1;
    $dlng = $lng2 - $lng1;

    $a = sin($dlat / 2) ** 2 + cos($lat1) * cos($lat2) * sin($dlng / 2) ** 2;
    $c = 2 * atan2(sqrt($a), sqrt(1 - $a));

    return $earthRadius * $c;
}

// Contoh data 2000 titik di Jawa Timur (disimulasikan)
$data = [];
for ($i = 0; $i < 2000; $i++) {
    $data[] = [
        'lat' => -8 + (rand(-500, 500) / 1000),
        'lng' => 112 + (rand(-500, 500) / 1000)
    ];
}

// Menyederhanakan menjadi 40 titik
$reducedPoints = kmeansClustering($data, 40);

// Output hasil
header('Content-Type: application/json');
echo json_encode($reducedPoints, JSON_PRETTY_PRINT);