optimized-route.sql

-- First create a temporary table to store waypoints for better performance
CREATE TEMPORARY TABLE IF NOT EXISTS temp_waypoints (
    id SERIAL PRIMARY KEY,
    point_type VARCHAR(20),
    geom GEOMETRY(Point, 4326)
);

-- Insert origin point
INSERT INTO temp_waypoints (point_type, geom)
VALUES (
    'origin',
    ST_SetSRID(ST_MakePoint(108.2138, 16.0815), 4326)
);

-- Insert waypoints from JSON
INSERT INTO temp_waypoints (point_type, geom)
SELECT
    'waypoint' as point_type,
    ST_SetSRID(ST_MakePoint(lng, lat), 4326) as geom
FROM jsonb_to_recordset('[
      {
        "lat": 10.7700,
        "lng": 106.7043
      },
      {
        "lat": 21.0396,
        "lng": 105.8550
      },
      {
        "lat": 19.8206,
        "lng": 105.7687
      },
      {
        "lat": 20.4212,
        "lng": 106.1652
      },
      {
        "lat": 10.0342,
        "lng": 105.7834
      }
]') as waypoints(lat float, lng float);

-- Insert destination point
INSERT INTO temp_waypoints (point_type, geom)
VALUES (
    'destination',
    ST_SetSRID(ST_MakePoint(107.5847, 16.4661), 4326)
);

-- Create index for better spatial query performance
CREATE INDEX IF NOT EXISTS idx_temp_waypoints_geom ON temp_waypoints USING GIST(geom);

-- Recursive CTE to find optimal path
WITH RECURSIVE sorted_path AS (
    -- Base case: start with origin
    SELECT
        id,
        point_type,
        geom,
        1 as path_order,
        ARRAY[id] as visited_points
    FROM temp_waypoints
    WHERE point_type = 'origin'

    UNION ALL

    -- Recursive case: find next nearest point
    SELECT
        w.id,
        w.point_type,
        w.geom,
        sp.path_order + 1,
        sp.visited_points || w.id
    FROM sorted_path sp
    CROSS JOIN LATERAL (
        SELECT
            tw.id,
            tw.point_type,
            tw.geom
        FROM temp_waypoints tw
        WHERE tw.id != ALL(sp.visited_points)
        AND (
            tw.point_type != 'destination'
            OR NOT EXISTS (
                SELECT 1
                FROM temp_waypoints tw2
                WHERE tw2.id != ALL(sp.visited_points)
                AND tw2.point_type = 'waypoint'
            )
        )
        ORDER BY
            CASE
                WHEN tw.point_type = 'destination' AND EXISTS (
                    SELECT 1
                    FROM temp_waypoints tw2
                    WHERE tw2.id != ALL(sp.visited_points)
                    AND tw2.point_type = 'waypoint'
                ) THEN 2
                ELSE 1
            END,
            sp.geom <-> tw.geom
        LIMIT 1
    ) w
)

-- Final result with coordinates
SELECT
    sp.path_order,
    sp.point_type,
    ST_X(sp.geom) as longitude,
    ST_Y(sp.geom) as latitude,
    CASE
        WHEN sp.point_type = 'waypoint'
        THEN sp.path_order - 2  -- Subtract 2 to account for origin being 1
        ELSE NULL
    END as waypoint_index
FROM sorted_path sp
ORDER BY sp.path_order;

-- Clean up
DROP TABLE IF EXISTS temp_waypoints;
DROP INDEX IF EXISTS idx_temp_waypoints_geom;