"use strict";

const fs = require("fs");
const { osm: { parseOsm }, laneGeometry: {
  appendCoordinates,
  haversineMeters,
  laneCenterline,
  lateralOffsetFrom,
  orientPolyline,
  polylineLength,
  polylineMidpoint,
} } = require("@osm-asset/road-compiler");

const MAX_ROUTES = 5;
const MAX_PATH_EDGES = 7;
const MIN_ROUTE_EDGES = 3;
const MAX_LANE_DISTANCE_METERS = 20;
const MIN_LATERAL_SEPARATION_METERS = 0.25;
const JUNCTION_TRIM_METERS = 6.0;
const CONNECTOR_SURFACE_TOLERANCE_METERS = 0.35;
const ALL_TURNS = new Set(["left", "through", "right"]);

function buildVehicleRoute(osmPath, lanePolygonsPath, networkPath, intersectionSurfacePath) {
  if (!lanePolygonsPath || !networkPath || !intersectionSurfacePath) {
    throw new Error("Lane polygons, osm2streets network, and intersection surface paths are required for vehicle route generation");
  }
  const osm = parseOsm(fs.readFileSync(osmPath, "utf8"));
  const lanePolygons = readLanePolygons(lanePolygonsPath);
  const network = readJsonObject(networkPath, "osm2streets network");
  const intersectionSurfaces = readFeatureCollection(intersectionSurfacePath, "intersection surfaces");
  const diagnostics = [];
  const laneIndex = indexDrivingLanes(lanePolygons.features, diagnostics);
  const intersections = indexIntersections(network, intersectionSurfaces.features);
  const edges = directedRoadEdges(network, osm.ways, diagnostics);
  const candidates = findReturnRoutes(edges);
  const routes = [];
  for (const candidate of candidates) {
    const route = makeRoute(candidate, laneIndex, intersections, diagnostics);
    if (route) routes.push(route);
  }
  const selected = selectRoutes(routes);
  return {
    source: osmPath,
    laneSource: lanePolygonsPath,
    networkSource: networkPath,
    intersectionSource: intersectionSurfacePath,
    bounds: osm.bounds,
    generatedAt: new Date().toISOString(),
    speedMetersPerSecond: 8.0,
    loop: true,
    routes: selected,
    diagnostics,
    // 旧预览仍读取 segments；保持与 routes 为同一个数组引用。
    segments: selected,
  };
}

function readLanePolygons(file) {
  return readFeatureCollection(file, "lane polygons");
}

function readFeatureCollection(file, label) {
  const collection = readJsonObject(file, label);
  if (collection?.type !== "FeatureCollection" || !Array.isArray(collection.features)) {
    throw new Error(`Invalid ${label} GeoJSON '${file}': expected FeatureCollection`);
  }
  return collection;
}

function readJsonObject(file, label) {
  try {
    const value = JSON.parse(fs.readFileSync(file, "utf8"));
    if (!value || typeof value !== "object" || Array.isArray(value)) throw new Error("expected JSON object");
    return value;
  } catch (error) {
    throw new Error(`Invalid ${label} JSON '${file}': ${error.message}`);
  }
}

function indexDrivingLanes(features, diagnostics) {
  const index = new Map();
  features.forEach((feature, featureIndex) => {
    if (feature?.properties?.type !== "Driving") return;
    const centerline = laneCenterline(feature);
    const direction = feature.properties.direction;
    const widthMeters = Number(feature.properties.width);
    const road = Number(feature.properties.road);
    if (!centerline || !["Fwd", "Back"].includes(direction) || !Number.isFinite(widthMeters) || widthMeters <= 0 || !Number.isInteger(road)) {
      diagnostics.push({
        reason: "invalid_lane_polygon",
        featureIndex,
        road: feature?.properties?.road ?? null,
        laneIndex: feature?.properties?.index ?? null,
      });
      return;
    }
    const lane = {
      featureIndex,
      polygonId: feature.id ?? `${feature.properties.road ?? "road"}:${direction}:${feature.properties.index ?? featureIndex}`,
      road,
      laneIndex: feature.properties.index,
      widthMeters,
      allowedTurns: normalizeAllowedTurns(feature.properties.allowed_turns),
      centerline,
    };
    const key = laneKey(road, direction);
    if (!index.has(key)) index.set(key, []);
    index.get(key).push(lane);
  });
  return index;
}

function normalizeAllowedTurns(value) {
  if (!Array.isArray(value)) return new Set();
  return new Set(value.map(normalizeTurn).filter(Boolean));
}

function isCruiseHighway(tags) {
  const highway = tags.highway || "";
  if (!highway || tags.area === "yes") return false;
  return !new Set([
    "footway", "path", "pedestrian", "steps", "cycleway", "service", "track",
    "bridleway", "corridor", "elevator", "platform", "construction",
  ]).has(highway);
}

function directedRoadEdges(network, ways, diagnostics) {
  if (!Array.isArray(network.roads) || !network.gps_bounds) {
    throw new Error("Invalid osm2streets network: expected roads and gps_bounds");
  }
  const waysById = new Map(ways.map((way) => [String(way.id), way]));
  const edges = [];
  for (const entry of network.roads) {
    const road = Array.isArray(entry) ? entry[1] : null;
    if (!road || !Number.isInteger(Number(road.id)) || !Array.isArray(road.lane_specs_ltr)) continue;
    const wayIds = Array.isArray(road.osm_ids) ? road.osm_ids.map(String) : [];
    const sourceWays = wayIds.map((id) => waysById.get(id)).filter(Boolean);
    const sourceWay = sourceWays[0] || null;
    const tags = sourceWay?.tags || { highway: road.highway_type || "" };
    if (!isCruiseHighway(tags)) continue;
    if (sourceWays.length > 1 && sourceWays.some((way) => JSON.stringify(way.tags) !== JSON.stringify(sourceWay.tags))) {
      addDiagnostic(diagnostics, { reason: "ambiguous_internal_road_source", road: road.id, osmWayIds: wayIds });
      continue;
    }
    const coordinates = networkPolylineToGps(road.center_line, network.gps_bounds);
    if (coordinates.length < 2 || routeLength(coordinates) < 12) continue;
    const directions = new Set(road.lane_specs_ltr
      .filter((lane) => lane.lt === "Driving")
      .map((lane) => lane.dir));
    if (directions.has("Fwd")) edges.push(makeEdge(road, sourceWay, wayIds, coordinates, "forward"));
    if (directions.has("Back")) edges.push(makeEdge(road, sourceWay, wayIds, [...coordinates].reverse(), "backward"));
  }
  return edges.sort((a, b) => a.id.localeCompare(b.id));
}

function makeEdge(road, way, wayIds, coordinates, direction) {
  const forward = direction === "forward";
  const tags = way?.tags || {};
  return {
    id: `road-${road.id}:${direction}`,
    roadId: Number(road.id),
    wayId: wayIds[0] || "",
    osmWayIds: wayIds,
    direction,
    name: road.name || tags.name || road.highway_type || "road",
    highway: road.highway_type || tags.highway || "",
    oneWay: directionsForRoad(road).size === 1 ? "yes" : "",
    startNode: forward ? Number(road.src_i) : Number(road.dst_i),
    endNode: forward ? Number(road.dst_i) : Number(road.src_i),
    coordinates,
    allowedTurns: allowedTurns(tags, direction),
    turnLanes: turnLanes(tags, direction),
  };
}

function directionsForRoad(road) {
  return new Set(road.lane_specs_ltr.filter((lane) => lane.lt === "Driving").map((lane) => lane.dir));
}

function networkPolylineToGps(polyline, bounds) {
  const points = Array.isArray(polyline?.pts) ? polyline.pts : [];
  const widthMeters = haversineMeters([bounds.min_lon, bounds.min_lat], [bounds.max_lon, bounds.min_lat]);
  const heightMeters = haversineMeters([bounds.min_lon, bounds.min_lat], [bounds.min_lon, bounds.max_lat]);
  if (!(widthMeters > 0) || !(heightMeters > 0)) return [];
  return points.map((point) => {
    const x = Number(point.x) / 10000;
    const y = Number(point.y) / 10000;
    return [
      bounds.min_lon + x / widthMeters * (bounds.max_lon - bounds.min_lon),
      bounds.min_lat + (bounds.max_lat - bounds.min_lat) * (heightMeters - y) / heightMeters,
    ];
  }).filter((coordinate) => coordinate.every(Number.isFinite));
}

function isOneWay(value) {
  return ["yes", "true", "1"].includes(value);
}

function allowedTurns(tags, direction) {
  const lanes = turnLanes(tags, direction);
  if (!lanes) return ALL_TURNS;
  const turns = new Set(lanes.flatMap((lane) => [...lane]).filter((turn) => ALL_TURNS.has(turn)));
  return turns.size ? turns : ALL_TURNS;
}

function turnLanes(tags, direction) {
  const value = tags[`turn:lanes:${direction}`] ?? tags["turn:lanes"];
  if (value === undefined || value === "") return null;
  return String(value).split("|").map((lane) => {
    const turns = new Set(String(lane).split(";").map(normalizeTurn).filter(Boolean));
    return turns.size ? turns : new Set(ALL_TURNS);
  });
}

function normalizeTurn(value) {
  const turn = String(value || "").trim().replace(/^slight_/, "");
  if (turn === "reverse") return "u_turn";
  return [...ALL_TURNS, "u_turn"].includes(turn) ? turn : null;
}

function findReturnRoutes(edges) {
  const outgoing = new Map();
  const byId = new Map();
  for (const edge of edges) {
    if (!outgoing.has(edge.startNode)) outgoing.set(edge.startNode, []);
    outgoing.get(edge.startNode).push(edge);
    byId.set(edge.id, edge);
  }
  const candidates = [];
  const seen = new Set();
  for (const first of edges) walkToTerminal([first], [], outgoing, byId, candidates, seen);
  return candidates.sort((a, b) => a.signature.localeCompare(b.signature));
}

function walkToTerminal(path, maneuvers, outgoing, byId, candidates, seen) {
  const current = path.at(-1);
  if (path.length >= MIN_ROUTE_EDGES) {
    const route = returnRoute(path, maneuvers, byId);
    if (route && !seen.has(route.signature)) {
      seen.add(route.signature);
      candidates.push(route);
    }
  }
  if (path.length >= MAX_PATH_EDGES) return;
  const nextSteps = [];
  for (const next of outgoing.get(current.endNode) || []) {
    if (path.some((edge) => edge.id === next.id)) continue;
    const maneuver = classifyConnection(current, next);
    if (!maneuver || !current.allowedTurns.has(maneuver)) continue;
    nextSteps.push({ edge: next, maneuver });
  }
  for (const step of nextSteps) {
    walkToTerminal([...path, step.edge], [...maneuvers, step.maneuver], outgoing, byId, candidates, seen);
  }
}

function classifyConnection(incoming, outgoing) {
  if (incoming.roadId === outgoing.roadId) return null;
  const inVector = directionVector(incoming.coordinates.at(-2), incoming.coordinates.at(-1));
  const outVector = directionVector(outgoing.coordinates[0], outgoing.coordinates[1]);
  const dot = inVector.x * outVector.x + inVector.y * outVector.y;
  const cross = inVector.x * outVector.y - inVector.y * outVector.x;
  const angle = Math.atan2(cross, dot) * 180 / Math.PI;
  if (Math.abs(angle) >= 150) return null;
  if (Math.abs(angle) <= 35) return "through";
  return angle > 0 ? "left" : "right";
}

function directionVector(a, b) {
  const scale = 111320;
  const x = (b[0] - a[0]) * scale * Math.cos(degreesToRadians((a[1] + b[1]) / 2));
  const y = (b[1] - a[1]) * scale;
  const length = Math.hypot(x, y) || 1;
  return { x: x / length, y: y / length };
}

function returnRoute(path, forwardManeuvers, byId) {
  const reverse = path.slice().reverse().map((edge) => byId.get(`road-${edge.roadId}:${oppositeDirection(edge.direction)}`));
  if (reverse.some((edge) => !edge)) return null;
  const returnManeuvers = [];
  for (let index = 1; index < reverse.length; index += 1) {
    const maneuver = classifyConnection(reverse[index - 1], reverse[index]);
    if (!maneuver) return null;
    returnManeuvers.push(maneuver);
  }
  const signature = path.map((edge) => edge.roadId).join(">");
  return {
    edges: [...path, ...reverse],
    maneuvers: [...forwardManeuvers, "u_turn", ...returnManeuvers, "u_turn"],
    forwardEdgeCount: path.length,
    signature,
  };
}

function oppositeDirection(direction) {
  return direction === "forward" ? "backward" : "forward";
}

function makeRoute(candidate, laneIndex, intersections, diagnostics) {
  const selectedLanes = [];
  for (let index = 0; index < candidate.edges.length; index += 1) {
    const edge = candidate.edges[index];
    const match = selectLaneForEdge(edge, candidate.maneuvers[index], laneIndex, {
      // 仅去程中的真实路口受 turn:lanes 严格约束；端点调头与展示返程不能被反向标签否决。
      enforceTurnRestrictions: index < candidate.forwardEdgeCount - 1,
    });
    if (!match.ok) {
      addDiagnostic(diagnostics, {
        reason: match.reason,
        routeSignature: candidate.signature,
        edgeId: edge.id,
        road: edge.roadId,
        osmWayId: edge.wayId,
        direction: edge.direction,
        maneuver: candidate.maneuvers[index],
        detail: match.detail,
      });
      return null;
    }
    selectedLanes.push(match.lane);
  }
  const smoothed = smoothLaneRoute(candidate.edges, selectedLanes, intersections);
  if (!smoothed.ok) {
    addDiagnostic(diagnostics, { reason: smoothed.reason, routeSignature: candidate.signature, ...smoothed.detail });
    return null;
  }
  const coordinates = smoothed.coordinates;
  const centerlineCoordinates = smoothRoute(candidate.edges);
  const route = {
    id: `route-${candidate.signature.replace(/[^\w]+/g, "-")}`,
    highway: candidate.edges[0].highway,
    oneWay: candidate.edges.some((edge) => isOneWay(String(edge.oneWay).toLowerCase())) ? "partial" : "",
    edgeIds: candidate.edges.map((edge) => edge.id),
    maneuvers: candidate.maneuvers,
    lengthMeters: routeLength(coordinates),
    coordinates,
    centerlineCoordinates,
    laneSegments: selectedLanes.flatMap((lane, edgeIndex) => lane.fragments.map((fragment) => ({
      edgeId: candidate.edges[edgeIndex].id,
      osmWayId: candidate.edges[edgeIndex].wayId,
      direction: candidate.edges[edgeIndex].direction,
      laneIndex: lane.laneIndex,
      widthMeters: fragment.widthMeters,
      centerOffsetMeters: Number(fragment.centerOffsetMeters.toFixed(3)),
      maneuver: candidate.maneuvers[edgeIndex],
      source: "lane_polygon_centerline",
      polygonId: fragment.polygonId,
      featureIndex: fragment.featureIndex,
      road: fragment.road,
    }))),
    connectors: smoothed.connectors,
  };
  Object.defineProperty(route, "signature", { value: candidate.signature });
  return route;
}

function selectLaneForEdge(edge, maneuver, laneIndex, options = {}) {
  const enforceTurnRestrictions = options.enforceTurnRestrictions !== false;
  const expectedDirection = edge.direction === "forward" ? "Fwd" : "Back";
  const candidates = laneIndex.get(laneKey(edge.roadId, expectedDirection)) || [];
  if (!candidates.length) return { ok: false, reason: "missing_lane_polygon" };
  const lanes = [];
  for (const fragment of candidates) {
    const centerline = orientPolyline(fragment.centerline, edge.coordinates);
    if (!centerline) return { ok: false, reason: "invalid_lane_polygon", detail: "direction_alignment" };
    const midpoint = polylineMidpoint(centerline);
    const offset = lateralOffsetFrom(edge.coordinates, midpoint);
    if (!offset || offset.distance > MAX_LANE_DISTANCE_METERS) {
      return { ok: false, reason: "missing_lane_polygon", detail: "geometry_too_far_from_internal_road" };
    }
    lanes.push({
      laneIndex: fragment.laneIndex,
      centerline,
      centerOffsetMeters: offset.lateral,
      allowedTurns: fragment.allowedTurns,
      fragments: [{ ...fragment, centerline, centerOffsetMeters: offset.lateral }],
    });
  }
  lanes.sort((a, b) => a.centerOffsetMeters - b.centerOffsetMeters || String(a.laneIndex).localeCompare(String(b.laneIndex)));
  for (let index = 1; index < lanes.length; index += 1) {
    if (lanes[index].centerOffsetMeters - lanes[index - 1].centerOffsetMeters < MIN_LATERAL_SEPARATION_METERS) {
      return { ok: false, reason: "ambiguous_lane_order" };
    }
  }
  if (enforceTurnRestrictions && edge.turnLanes && edge.turnLanes.length !== lanes.length) {
    return { ok: false, reason: "ambiguous_lane_order", detail: "turn_lane_count_mismatch" };
  }
  let compatible = lanes.filter((lane, index) => laneSupportsManeuver(lane, edge.turnLanes?.[index], maneuver));
  if (!compatible.length && !enforceTurnRestrictions) compatible = lanes;
  if (!compatible.length) return { ok: false, reason: "no_compatible_turn_lane" };
  const chooseLeft = maneuver === "left" || maneuver === "u_turn";
  return { ok: true, lane: chooseLeft ? compatible[0] : compatible.at(-1) };
}

function laneSupportsManeuver(lane, osmTurns, maneuver) {
  const expected = maneuver === "u_turn" ? "left" : maneuver;
  if (osmTurns && !osmTurns.has(expected) && !(maneuver === "u_turn" && osmTurns.has("u_turn"))) return false;
  if (lane.allowedTurns.size && !lane.allowedTurns.has(expected) && !(maneuver === "u_turn" && lane.allowedTurns.has("u_turn"))) return false;
  return true;
}

function laneKey(roadId, direction) {
  return `${String(roadId)}:${direction}`;
}

function addDiagnostic(diagnostics, entry) {
  const key = JSON.stringify(entry);
  if (!diagnostics.some((current) => JSON.stringify(current) === key)) diagnostics.push(entry);
}

function indexIntersections(network, features) {
  if (!Array.isArray(network.intersections)) throw new Error("Invalid osm2streets network: expected intersections");
  const surfaces = new Map(features
    .filter((feature) => feature?.geometry?.type === "Polygon" && Number.isInteger(Number(feature.properties?.id)))
    .map((feature) => [Number(feature.properties.id), feature.geometry.coordinates[0]]));
  const intersections = new Map();
  for (const entry of network.intersections) {
    const intersection = Array.isArray(entry) ? entry[1] : null;
    if (!intersection || !Number.isInteger(Number(intersection.id))) continue;
    intersections.set(Number(intersection.id), {
      id: Number(intersection.id),
      osmNodeIds: Array.isArray(intersection.osm_ids) ? intersection.osm_ids.map(String) : [],
      surface: surfaces.get(Number(intersection.id)) || null,
    });
  }
  return intersections;
}

function smoothLaneRoute(edges, selectedLanes, intersections) {
  const route = [];
  const connectors = [];
  for (let index = 0; index < edges.length; index += 1) {
    const current = selectedLanes[index].centerline;
    appendCoordinates(route, current);
    const nextIndex = (index + 1) % edges.length;
    const next = selectedLanes[nextIndex].centerline;
    const incomingEdge = edges[index];
    const outgoingEdge = edges[nextIndex];
    if (incomingEdge.endNode !== outgoingEdge.startNode) {
      return { ok: false, reason: "disconnected_internal_roads", detail: { fromRoad: incomingEdge.roadId, toRoad: outgoingEdge.roadId } };
    }
    const intersection = intersections.get(incomingEdge.endNode);
    if (!intersection?.surface) {
      return { ok: false, reason: "missing_intersection_surface", detail: { intersectionId: incomingEdge.endNode } };
    }
    const isUTurn = incomingEdge.roadId === outgoingEdge.roadId;
    const turn = constrainedConnector(current, next, incomingEdge.coordinates.at(-1), intersection.surface, isUTurn);
    if (!turn) {
      return {
        ok: false,
        reason: "connector_outside_intersection",
        detail: { intersectionId: intersection.id, fromRoad: incomingEdge.roadId, toRoad: outgoingEdge.roadId },
      };
    }
    appendCoordinates(route, turn.slice(1));
    connectors.push({
      intersectionId: intersection.id,
      osmNodeIds: intersection.osmNodeIds,
      fromRoad: incomingEdge.roadId,
      toRoad: outgoingEdge.roadId,
      maneuver: isUTurn ? "u_turn" : classifyConnection(incomingEdge, outgoingEdge),
      source: "intersection_surface_constrained",
      coordinates: turn,
    });
  }
  if (route.length) route[route.length - 1] = [...route[0]];
  return { ok: true, coordinates: route, connectors };
}

function constrainedConnector(incoming, outgoing, junction, surface, isUTurn) {
  const scales = isUTurn ? [1, 0.8, 0.6, 0.4, 0.25] : [1, 0.75, 0.5, 0.3, 0.15];
  for (const scale of scales) {
    const connector = isUTurn
      ? uTurnConnector(incoming, outgoing, junction, 20, scale)
      : tangentBezierTurn(incoming, outgoing, 16, scale);
    if (connector.length && connector.every((point) => pointInPolygonOrNear(point, surface, CONNECTOR_SURFACE_TOLERANCE_METERS))) {
      return connector;
    }
  }
  return null;
}

function pointInPolygonOrNear(point, ring, toleranceMeters) {
  if (!Array.isArray(ring) || ring.length < 4) return false;
  let inside = false;
  for (let i = 0, j = ring.length - 1; i < ring.length; j = i, i += 1) {
    const a = ring[i];
    const b = ring[j];
    if ((a[1] > point[1]) !== (b[1] > point[1]) &&
        point[0] < (b[0] - a[0]) * (point[1] - a[1]) / (b[1] - a[1]) + a[0]) inside = !inside;
    if (distanceToSegmentMeters(point, a, b) <= toleranceMeters) return true;
  }
  return inside;
}

function distanceToSegmentMeters(point, start, end) {
  const latitude = (point[1] + start[1] + end[1]) / 3;
  const metersLon = 111320 * Math.cos(degreesToRadians(latitude));
  const dx = (end[0] - start[0]) * metersLon;
  const dy = (end[1] - start[1]) * 111320;
  const px = (point[0] - start[0]) * metersLon;
  const py = (point[1] - start[1]) * 111320;
  const lengthSquared = dx * dx + dy * dy;
  const ratio = lengthSquared ? Math.max(0, Math.min(1, (px * dx + py * dy) / lengthSquared)) : 0;
  return Math.hypot(px - dx * ratio, py - dy * ratio);
}

function smoothRoute(edges) {
  const trimmed = edges.map((edge) => trimPolyline(edge.coordinates, JUNCTION_TRIM_METERS));
  const route = [];
  for (let index = 0; index < edges.length; index += 1) {
    appendCoordinates(route, trimmed[index]);
    const nextIndex = (index + 1) % edges.length;
    const turn = edges[index].roadId === edges[nextIndex].roadId
      ? uTurnConnector(trimmed[index], trimmed[nextIndex], edges[index].coordinates.at(-1))
      : tangentBezierTurn(trimmed[index], trimmed[nextIndex]);
    appendCoordinates(route, turn.slice(1));
  }
  if (route.length) route[route.length - 1] = [...route[0]];
  return route;
}

function tangentBezierTurn(incoming, outgoing, samples = 16, scale = 1) {
  if (incoming.length < 2 || outgoing.length < 2) return [];
  const start = incoming.at(-1);
  const end = outgoing[0];
  const incomingTangent = directionVector(incoming.at(-2), start);
  const outgoingTangent = directionVector(end, outgoing[1]);
  const incomingSpan = haversineMeters(incoming.at(-2), start);
  const outgoingSpan = haversineMeters(end, outgoing[1]);
  const intersection = intersectTangentRays(start, end, incomingTangent, outgoingTangent);
  let controlA;
  let controlB;
  if (intersection && intersection.a >= 0 && intersection.b >= 0) {
    // 两条车道切线的前向交点定义了转弯的几何目标，Bezier 控制点取三分之一距离。
    const maxA = Math.min(8, Math.max(0.75, incomingSpan * 2.4));
    const maxB = Math.min(8, Math.max(0.75, outgoingSpan * 2.4));
    const distanceA = Math.min(intersection.a, maxA) * scale;
    const distanceB = Math.min(intersection.b, maxB) * scale;
    controlA = offsetCoordinate(start, incomingTangent.x * distanceA / 3, incomingTangent.y * distanceA / 3);
    controlB = offsetCoordinate(end, -outgoingTangent.x * distanceB / 3, -outgoingTangent.y * distanceB / 3);
  } else {
    // 平行、反向或交点在车道后方时，使用受限 fallback，避免生成反向回环。
    const chordMeters = haversineMeters(start, end);
    const controlMeters = boundedControlDistance(chordMeters, incomingSpan, outgoingSpan, 0.42, 8) * scale;
    controlA = offsetCoordinate(start, incomingTangent.x * controlMeters, incomingTangent.y * controlMeters);
    controlB = offsetCoordinate(end, -outgoingTangent.x * controlMeters, -outgoingTangent.y * controlMeters);
  }
  return cubicBezier(start, controlA, controlB, end, samples);
}

function intersectTangentRays(start, end, incomingTangent, outgoingTangent) {
  const latitude = (start[1] + end[1]) / 2;
  const metersLon = 111320 * Math.cos(degreesToRadians(latitude));
  const qx = (end[0] - start[0]) * metersLon;
  const qy = (end[1] - start[1]) * 111320;
  const cross = incomingTangent.x * outgoingTangent.y - incomingTangent.y * outgoingTangent.x;
  if (Math.abs(cross) < 1e-6) return null;
  const crossQOutgoing = qx * outgoingTangent.y - qy * outgoingTangent.x;
  const crossQIncoming = qx * incomingTangent.y - qy * incomingTangent.x;
  return {
    a: crossQOutgoing / cross,
    b: crossQIncoming / cross,
  };
}

function uTurnConnector(incoming, outgoing, junction, samples = 20, scale = 1) {
  if (incoming.length < 2 || outgoing.length < 2) return [];
  const start = incoming.at(-1);
  const end = outgoing[0];
  const incomingTangent = directionVector(incoming.at(-2), start);
  const outgoingTangent = directionVector(end, outgoing[1]);
  const chordMeters = haversineMeters(start, end);
  const approachMeters = Math.max(haversineMeters(start, junction), haversineMeters(end, junction));
  const incomingSpan = haversineMeters(incoming.at(-2), start);
  const outgoingSpan = haversineMeters(end, outgoing[1]);
  const availableMeters = Math.max(0.5, Math.min(10, incomingSpan * 0.8, outgoingSpan * 0.8));
  const controlMeters = Math.min(availableMeters, Math.max(Math.min(2, availableMeters), chordMeters * 1.1, approachMeters * 0.6)) * scale;
  const controlA = offsetCoordinate(start, incomingTangent.x * controlMeters, incomingTangent.y * controlMeters);
  const controlB = offsetCoordinate(end, -outgoingTangent.x * controlMeters, -outgoingTangent.y * controlMeters);
  return cubicBezier(start, controlA, controlB, end, samples);
}

function boundedControlDistance(chordMeters, incomingSpan, outgoingSpan, ratio, maximumMeters) {
  const lowerMeters = Math.min(1.5, chordMeters * 0.35);
  const upperMeters = Math.max(0.25, Math.min(maximumMeters, chordMeters * 0.65, incomingSpan * 0.8, outgoingSpan * 0.8));
  return Math.min(upperMeters, Math.max(lowerMeters, chordMeters * ratio));
}

function offsetCoordinate(coord, eastMeters, northMeters) {
  const metersPerLat = 111320;
  const metersPerLon = metersPerLat * Math.cos(degreesToRadians(coord[1]));
  return [coord[0] + eastMeters / metersPerLon, coord[1] + northMeters / metersPerLat];
}

function trimPolyline(coords, distance) {
  if (coords.length < 2 || routeLength(coords) <= distance * 2.5) return [...coords];
  const start = pointAlong(coords, distance);
  const end = pointAlong([...coords].reverse(), distance);
  return [start, ...coords.slice(1, -1), end];
}

function pointAlong(coords, distance) {
  let remaining = distance;
  for (let index = 1; index < coords.length; index += 1) {
    const span = haversineMeters(coords[index - 1], coords[index]);
    if (span >= remaining) return lerpCoordinate(coords[index - 1], coords[index], remaining / span);
    remaining -= span;
  }
  return [...coords.at(-1)];
}

function cubicBezier(start, controlA, controlB, end, samples) {
  const points = [];
  for (let index = 0; index <= samples; index += 1) {
    const t = index / samples;
    const u = 1 - t;
    points.push([
      u ** 3 * start[0] + 3 * u ** 2 * t * controlA[0] + 3 * u * t ** 2 * controlB[0] + t ** 3 * end[0],
      u ** 3 * start[1] + 3 * u ** 2 * t * controlA[1] + 3 * u * t ** 2 * controlB[1] + t ** 3 * end[1],
    ]);
  }
  return points;
}

function selectRoutes(candidates) {
  const selected = [];
  const covered = new Set();
  const remaining = [...candidates];
  while (selected.length < MAX_ROUTES && remaining.length) {
    remaining.sort((a, b) => routeScore(b, covered) - routeScore(a, covered) || a.id.localeCompare(b.id));
    const next = remaining.shift();
    selected.push(next);
    for (const maneuver of next.maneuvers) covered.add(maneuver);
  }
  return selected;
}

function routeScore(route, covered) {
  const novelty = new Set(route.maneuvers.filter((maneuver) => ALL_TURNS.has(maneuver) && !covered.has(maneuver))).size;
  return novelty * 100000 + route.lengthMeters;
}

function routeLength(coords) {
  return polylineLength(coords);
}

function lerpCoordinate(a, b, t) {
  return [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t];
}

function degreesToRadians(value) {
  return value * Math.PI / 180;
}

module.exports = {
  allowedTurns,
  buildVehicleRoute,
  classifyConnection,
  readLanePolygons,
  selectLaneForEdge,
  tangentBezierTurn,
  turnLanes,
  uTurnConnector,
};