Menyederhanakan 2000 koordinat menjadi 40 koordninat dengan PHP

Adakalanya 4000 koordinat akan terlalu gendut, makanya perlu disederhanakan menjadi 40 saja. Di sini memakai kmean clustering dengan PHP sehingga walaupun tidak gendut tapi sudah mewakili titik titik tadinya

Feb 24, 2025 - 19:01

Menyederhanakan 2000 koordinat menjadi 40 koordninat dengan PHP

Adakalanya 4000 koordinat akan terlalu gendut, makanya perlu disederhanakan menjadi 40 saja.

Di sini memakai kmean clustering dengan PHP sehingga walaupun tidak gendut tapi sudah mewakili titik titik tadinya


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);