modules/map_builder.py

import os
import math
import json
import re
import unicodedata
import numpy as np
from PIL import Image, ImageDraw, ImageFilter, ImageFont

# =========================
# CONSTANTS & CONFIG
# =========================
ASSETS_DIR = os.path.join(os.path.dirname(os.path.dirname(__file__)), "assets")
MAP_STYLE_DIR = os.path.join(ASSETS_DIR, "map_styles")
CITIES_MASTER_FILE = os.path.join(ASSETS_DIR, "cities_master.json")
ANCHORS_DEFAULT_FILE = os.path.join(ASSETS_DIR, "anchors_default.json")

# =========================
# DEFAULT COLORS (used as fallback if style pack missing a key)
# =========================
COLOR_PLANE = (0x1F, 0x27, 0xD8, 255)
COLOR_CAR = (0x1F, 0x27, 0xD8, 255)
COLOR_BOAT = (0x1F, 0x27, 0xD8, 255)
COLOR_TRAIN = (0xC3, 0x0F, 0x16, 255)
MARKER_COLOR_VN = (0x33, 0x99, 0x00, 255)
MARKER_COLOR_FOREIGN = (0xFF, 0x00, 0x00, 255)

# New style-pack system used by the current app runtime.
# If blank maps or replacement icons are dropped into assets/map_styles/style1|style2,
# the renderer will pick them up automatically without more code changes.
STYLE_ALIASES = {
    "default": "style1",
    "tonkin": "style1",
    "classic": "style2",
    "warm": "style2",
}

BASE_MAP_ALIASES = {
    "Vietnam": "Vietnam Only",
    "VN+Laos+Cambodia": "Indochina",
    "VN Laos Cambodia": "Indochina",
    "Vietnam Laos Cambodia": "Indochina",
    "SoutheastAsia": "Southeast Asia",
    "SEA": "Southeast Asia",
}


def normalize_base_map_name(base_map_name):
    name = (base_map_name or "Vietnam Only").strip()
    return BASE_MAP_ALIASES.get(name, name)


def _style_asset_path(style_name, *parts):
    return os.path.join(MAP_STYLE_DIR, style_name, *parts)


STYLE_PACKS = {
    "style1": {
        "name": "Style 1",
        "description": "Default clean route style.",
        "icon_scale": 1.0,
        "line_width_scale": 1.0,
        "dash_patterns": {
            "plane": (12, 8),
            "arrival_departure": (12, 8),
        },
        "mode_icon_scale": {
            "plane": 1.0,
        },
        "mode_offset_scale": {
            "car": 0.85,
            "boat": 1.05,
            "train": 1.3,
        },
        "colors": {
            "plane": (0x00, 0x00, 0xFF, 255),
            "car": (0x00, 0x00, 0xFF, 255),
            "boat": (0x33, 0x99, 0x00, 255),
            "train": (0xC3, 0x0F, 0x16, 255),
            "marker_vn": (0x33, 0x99, 0x00, 255),
            "marker_foreign": (0xFF, 0x00, 0x00, 255),
            "arrival_departure": (0x00, 0x00, 0xFF, 255),
        },
        "maps": {
            "Vietnam": {
                "blank_candidates": [
                    _style_asset_path("style1", "base_map_vietnam_only_blank.png"),
                    _style_asset_path("style1", "base_map_vietnam_only_blank.jpg"),
                    _style_asset_path("style1", "base_map_vietnam_blank.png"),
                    _style_asset_path("style1", "base_map_vietnam_blank.jpg"),
                    _style_asset_path("style1", "base_map_vietnam.png"),
                    _style_asset_path("style1", "base_map_vietnam.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map.jpg"),
            },
            "Vietnam Only": {
                "blank_candidates": [
                    _style_asset_path("style1", "base_map_vietnam_only_blank.png"),
                    _style_asset_path("style1", "base_map_vietnam_only_blank.jpg"),
                    _style_asset_path("style1", "base_map_vietnam_blank.png"),
                    _style_asset_path("style1", "base_map_vietnam_blank.jpg"),
                    _style_asset_path("style1", "base_map_vietnam.png"),
                    _style_asset_path("style1", "base_map_vietnam.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map.jpg"),
            },
            "Indochina": {
                "blank_candidates": [
                    _style_asset_path("style1", "base_map_indochina_blank.png"),
                    _style_asset_path("style1", "base_map_indochina_blank.jpg"),
                    _style_asset_path("style1", "base_map_vn+laos+cambodia_blank.png"),
                    _style_asset_path("style1", "base_map_vn+laos+cambodia_blank.jpg"),
                ],
                "legacy_fallback": None,
            },
            "Southeast Asia": {
                "blank_candidates": [
                    _style_asset_path("style1", "base_map_southeast_asia_blank.png"),
                    _style_asset_path("style1", "base_map_southeast_asia_blank.jpg"),
                    _style_asset_path("style1", "base_map_southeast_asia.png"),
                    _style_asset_path("style1", "base_map_southeast_asia.jpg"),
                    _style_asset_path("style1", "base_map_indochina.png"),
                    _style_asset_path("style1", "base_map_indochina.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map_indochina.jpg"),
            },
        },
        "icons": {
            "plane": [_style_asset_path("style1", "plane.png"), os.path.join(ASSETS_DIR, "plane2.png")],
            "car": [_style_asset_path("style1", "car.png"), os.path.join(ASSETS_DIR, "car2.png")],
            "boat": [_style_asset_path("style1", "boat.png"), os.path.join(ASSETS_DIR, "boat2.png")],
            "train": [_style_asset_path("style1", "train.png"), os.path.join(ASSETS_DIR, "train2.png")],
        },
    },
    "style2": {
        "name": "Style 2",
        "description": "Alternative icon pack with larger transport markers.",
        "icon_scale": 1.35,
        "line_width_scale": 1.2,
        "dash_patterns": {
            "plane": (12, 8),
            "arrival_departure": (12, 8),
        },
        "mode_icon_scale": {
            "plane": 0.82,
            "car": 74 / (40 * 1.35),  # 74 px final output width
        },
        "mode_offset_scale": {
            "car": 1.15,
            "boat": 1.3,
            "train": 1.25,
        },
        "colors": {
            "plane": (0x36, 0x6A, 0x93, 255),
            "car": (0x36, 0x6A, 0x93, 255),
            "boat": (0x33, 0x99, 0x00, 255),
            "train": (0xDC, 0x14, 0x3C, 255),
            "marker_vn": (0x22, 0x8B, 0x22, 255),
            "marker_foreign": (0xFF, 0x45, 0x00, 255),
            "arrival_departure": (0x36, 0x6A, 0x93, 255),
        },
        "maps": {
            "Vietnam": {
                "blank_candidates": [
                    _style_asset_path("style2", "base_map_vietnam_only_blank.png"),
                    _style_asset_path("style2", "base_map_vietnam_only_blank.jpg"),
                    _style_asset_path("style2", "base_map_vietnam_blank.png"),
                    _style_asset_path("style2", "base_map_vietnam_blank.jpg"),
                    _style_asset_path("style2", "base_map_vietnam.png"),
                    _style_asset_path("style2", "base_map_vietnam.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map.jpg"),
            },
            "Vietnam Only": {
                "blank_candidates": [
                    _style_asset_path("style2", "base_map_vietnam_only_blank.png"),
                    _style_asset_path("style2", "base_map_vietnam_only_blank.jpg"),
                    _style_asset_path("style2", "base_map_vietnam_blank.png"),
                    _style_asset_path("style2", "base_map_vietnam_blank.jpg"),
                    _style_asset_path("style2", "base_map_vietnam.png"),
                    _style_asset_path("style2", "base_map_vietnam.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map.jpg"),
            },
            "Indochina": {
                "blank_candidates": [
                    _style_asset_path("style2", "base_map_indochina_blank.png"),
                    _style_asset_path("style2", "base_map_indochina_blank.jpg"),
                    _style_asset_path("style2", "base_map_vn+laos+cambodia_blank.png"),
                    _style_asset_path("style2", "base_map_vn+laos+cambodia_blank.jpg"),
                ],
                "legacy_fallback": None,
            },
            "Southeast Asia": {
                "blank_candidates": [
                    _style_asset_path("style2", "base_map_southeast_asia_blank.png"),
                    _style_asset_path("style2", "base_map_southeast_asia_blank.jpg"),
                    _style_asset_path("style2", "base_map_southeast_asia.png"),
                    _style_asset_path("style2", "base_map_southeast_asia.jpg"),
                    _style_asset_path("style2", "base_map_indochina.png"),
                    _style_asset_path("style2", "base_map_indochina.jpg"),
                ],
                "legacy_fallback": os.path.join(ASSETS_DIR, "base_map_indochina.jpg"),
            },
        },
        "icons": {
            "plane": [_style_asset_path("style2", "plane.png"), os.path.join(ASSETS_DIR, "plane2.png")],
            "car": [_style_asset_path("style2", "car.png"), os.path.join(ASSETS_DIR, "car2.png")],
            "boat": [_style_asset_path("style2", "boat.png"), os.path.join(ASSETS_DIR, "boat2.png")],
            "speedboat": [_style_asset_path("style2", "speedboat.png")],
            "train": [_style_asset_path("style2", "train.png"), os.path.join(ASSETS_DIR, "train2.png")],
        },
    },
}

RACH_GIA_PHU_QUOC_PAIR = frozenset(("Rach Gia", "Phu Quoc"))
STYLE2_SPEEDBOAT_ROUTE_PAIRS = {
    RACH_GIA_PHU_QUOC_PAIR,
    frozenset(("Con Dao", "Phu Quoc")),
}

CENTRAL_VIETNAM_CAR_ICON_LEFT_CITIES = {"Hue", "Da Nang", "Hoi An"}
NINH_BINH_HA_LONG_CAR_ICON_PAIR = frozenset(("Ninh Binh", "Ha Long"))
INLAND_TRAIN_ROUTE_PAIRS = {
    frozenset(("Ha Noi", "Hue")),
    frozenset(("Ha Noi", "Da Nang")),
}
VIETNAM_COASTAL_TRAIN_ROUTE_PAIRS = {
    frozenset(("Da Nang", "Sai Gon")),
    frozenset(("Hue", "Sai Gon")),
}

DEFAULT_LANDMARKS_BY_BASE_MAP = {
    "Vietnam": ["Ha Noi", "Ha Long", "Hue", "Da Nang", "Hoi An", "Sai Gon"],
    "Vietnam Only": ["Ha Noi", "Ha Long", "Hue", "Da Nang", "Hoi An", "Sai Gon"],
    "Indochina": [
        "Ha Noi", "Ha Long", "Hue", "Da Nang", "Hoi An", "Sai Gon",
        "Luang Prabang", "Vientiane", "Pakse",
        "Siem Reap", "Phnom Penh",
    ],
    "VN+Laos+Cambodia": [
        "Ha Noi", "Ha Long", "Hue", "Da Nang", "Hoi An", "Sai Gon",
        "Luang Prabang", "Vientiane", "Pakse",
        "Siem Reap", "Phnom Penh",
    ],
    "Southeast Asia": [
        "Ha Noi", "Ha Long", "Hue", "Da Nang", "Hoi An", "Sai Gon",
        "Luang Prabang", "Vientiane", "Pakse",
        "Siem Reap", "Phnom Penh",
        "Bangkok",
    ],
    "Cambodia": ["Siem Reap", "Phnom Penh", "Battambang", "Sihanoukville"],
    "Laos": ["Luang Prabang", "Vientiane", "Pakse"],
    "Thailand": ["Bangkok", "Chiang Mai", "Phuket"],
    "Myanmar": ["Yangon", "Mandalay", "Bagan", "Inle Lake"],
}

CITY_POSITION_OVERRIDES = {
    ("Vietnam Only", "style2"): {
        # The illustrated Vietnam Style 2 base map draws Phu Quoc lower than
        # the affine lat/lon projection, so pin it to the island artwork.
        # Keyed by base-map style, not icon asset style.
        "Phu Quoc": (0.2796, 0.9010),
    },
}


def _first_existing(paths):
    for path in paths:
        if path and os.path.exists(path):
            return path
    return None


import glob as _glob

def list_base_map_variants(base_map_name, style_name="style1"):
    """Return list of available variant labels for a base map (e.g. ['default', '1', '2'])."""
    resolved_name = STYLE_ALIASES.get(style_name, style_name)
    base_map_name = normalize_base_map_name(base_map_name)
    slug = base_map_name.lower().replace(" ", "_")
    style_dir = os.path.join(MAP_STYLE_DIR, resolved_name)
    variants = []
    # Check default (no suffix)
    for ext in ("png", "jpg"):
        if os.path.exists(os.path.join(style_dir, f"base_map_{slug}_blank.{ext}")):
            variants.append("default")
            break
        if os.path.exists(os.path.join(style_dir, f"base_map_{slug}.{ext}")):
            variants.append("default")
            break
    # Scan numbered variants (_1, _2, _3...)
    for f in sorted(_glob.glob(os.path.join(style_dir, f"base_map_{slug}_blank_*.*"))):
        fname = os.path.basename(f)
        # Extract the variant number/label from e.g. base_map_vietnam_only_blank_2.png
        stem = os.path.splitext(fname)[0]  # base_map_vietnam_only_blank_2
        suffix = stem.replace(f"base_map_{slug}_blank_", "")  # "2"
        if suffix and suffix not in variants:
            variants.append(suffix)
    return variants if variants else ["default"]


def resolve_style_pack(style_name, base_map_name, variant=None, base_map_style=None):
    resolved_name = STYLE_ALIASES.get(style_name, style_name)
    style_cfg = STYLE_PACKS.get(resolved_name, STYLE_PACKS["style1"])
    resolved_map_style = STYLE_ALIASES.get(base_map_style or resolved_name, base_map_style or resolved_name)
    map_style_cfg = STYLE_PACKS.get(resolved_map_style, style_cfg)
    base_map_name = normalize_base_map_name(base_map_name)
    map_cfg = map_style_cfg["maps"].get(base_map_name)
    slug = base_map_name.lower().replace(" ", "_")
    
    # If a numbered variant is specified (e.g. "1", "2"), look for that file first
    variant_candidates = []
    if variant and variant != "default":
        variant_candidates = [
            _style_asset_path(resolved_map_style, f"base_map_{slug}_blank_{variant}.png"),
            _style_asset_path(resolved_map_style, f"base_map_{slug}_blank_{variant}.jpg"),
            _style_asset_path(resolved_map_style, f"base_map_{slug}_{variant}.png"),
            _style_asset_path(resolved_map_style, f"base_map_{slug}_{variant}.jpg"),
        ]
    
    if not map_cfg:
        # Auto-generate candidates for any country name
        map_cfg = {
            "blank_candidates": [
                _style_asset_path(resolved_map_style, f"base_map_{slug}_blank.png"),
                _style_asset_path(resolved_map_style, f"base_map_{slug}_blank.jpg"),
                _style_asset_path(resolved_map_style, f"base_map_{slug}.png"),
                _style_asset_path(resolved_map_style, f"base_map_{slug}.jpg"),
            ],
            "legacy_fallback": None,
        }
    
    # Try variant first, then default candidates
    all_candidates = variant_candidates + map_cfg.get("blank_candidates", [])
    blank_map = _first_existing(all_candidates)
    if not blank_map and not map_cfg.get("legacy_fallback"):
        # No image found for this country — fall back to Vietnam
        map_cfg = map_style_cfg["maps"]["Vietnam"]
        blank_map = _first_existing(map_cfg.get("blank_candidates", []))
    base_map_path = blank_map or map_cfg.get("legacy_fallback")
    icons = {
        mode: _first_existing(candidates)
        for mode, candidates in style_cfg.get("icons", {}).items()
    }
    return {
        "key": resolved_name,
        "base_map_style": resolved_map_style,
        "name": style_cfg["name"],
        "description": style_cfg["description"],
        "colors": style_cfg["colors"],
        "icon_scale": style_cfg.get("icon_scale", 1.0),
        "line_width_scale": style_cfg.get("line_width_scale", 1.0),
        "dash_patterns": style_cfg.get("dash_patterns", {}),
        "mode_icon_scale": style_cfg.get("mode_icon_scale", {}),
        "mode_offset_scale": style_cfg.get("mode_offset_scale", {}),
        "base_map_path": base_map_path,
        "legacy_fallback_path": map_cfg.get("legacy_fallback"),
        "has_preprinted_labels": not bool(blank_map),
        "icons": icons,
    }


def resolve_anchor_preset_name(base_map_name, style_pack=None, base_map_path=None):
    """Pick the best anchor preset for the actual base map file in use."""
    path = (base_map_path or (style_pack or {}).get("base_map_path") or "").lower()
    normalized = normalize_base_map_name(base_map_name)
    if "vietnam_only" in path:
        return "Vietnam Only"
    if "southeast_asia" in path:
        return "Southeast Asia"
    if "vn+laos+cambodia" in path or "vn_laos_cambodia" in path:
        return "Indochina"
    return normalized

MARKER_R = 6
DASH_ON, DASH_OFF = 12, 6
ARROW_SIZE = 18
CURVE_BULGE = 0.25
LABEL_STROKE_W = 2
SUPERSAMPLE_DEFAULT = 3


# Default anchors. The runtime writes/reads these from assets/anchors_default.json.
DEFAULT_ANCHORS_PRESETS = {
    "Southeast Asia": {
        "Ha Noi": (0.641103, 0.170993),
        "Bangkok": (0.297468, 0.5510993191489362),
        "Sai Gon": (0.6925316817359854, 0.702836439716312),
    },
    "Vietnam": {
        "Ha Noi": (0.507103, 0.185993),
        "Hue": (0.74, 0.49),
        "Sai Gon": (0.63934, 0.843918),
    },
    "Vietnam Only": {
        "Ha Noi": (0.4829, 0.1995),
        "Hue": (0.6884, 0.4892),
        "Sai Gon": (0.5762, 0.8460),
    },
    "Cambodia": {
        "Siem Reap": (0.3739, 0.3223),
        "Battambang": (0.2899, 0.3695),
        "Phnom Penh": (0.5122, 0.6241),
        "Sihanoukville": (0.3294, 0.7812),
        "Kampot": (0.4159, 0.7844),
        "Kep": (0.4332, 0.8064),
    },
    "Laos": {
        "Luang Prabang": (0.3142, 0.3178),
        "Pak Ou": (0.3229, 0.3029),
        "Khuang Si": (0.2968, 0.3327),
        "Vang Vieng": (0.3489, 0.4148),
        "Vientiane": (0.3706, 0.5080),
        "Pakse": (0.7264, 0.7915),
    },
    "Thailand": {
        "Bangkok": (0.4265, 0.4414),
        "Chiang Mai": (0.2337, 0.1055),
        "Chiang Rai": (0.3425, 0.0305),
        "Phuket": (0.1570, 0.8336),
        "Krabi": (0.2238, 0.8198),
        "Koh Samui": (0.3721, 0.7224),
        "Pattaya": (0.4760, 0.4964),
        "Ayutthaya": (0.4364, 0.4014),
        "Sukhothai": (0.3400, 0.2241),
        "Pai": (0.1645, 0.0680),
        "Mae Hong Son": (0.1027, 0.0717),
        "Kanchanaburi": (0.3029, 0.4239),
    },
    "Indochina": {
        "Ha Noi": (0.5756, 0.2173),
        "Hue": (0.7104, 0.4920),
        "Da Nang": (0.7593, 0.5157),
        "Hoi An": (0.7682, 0.5270),
        "Sai Gon": (0.6378, 0.8322),
        "Luang Prabang": (0.2926, 0.2863),
        "Vientiane": (0.3311, 0.4016),
        "Pakse": (0.5741, 0.5733),
        "Siem Reap": (0.4244, 0.6796),
        "Phnom Penh": (0.5074, 0.7881),
    },
    "Myanmar": {
        "Yangon": (0.50, 0.75),
        "Mandalay": (0.50, 0.40),
        "Bagan": (0.35, 0.45),
    },
}

ANCHORS_PRESETS = DEFAULT_ANCHORS_PRESETS

# Multi-language translations (FR/EN/IT - no Vietnamese)
TRANSLATIONS = {
    "FR": {"arrival": "Arrivée", "departure": "Départ"},
    "EN": {"arrival": "Arrival", "departure": "Departure"},
    "IT": {"arrival": "Arrivo", "departure": "Partenza"}
}

# =========================
# CITY DATABASE
# =========================
class City:
    def __init__(self, name, lat, lon, country="VN", aliases=None, label_ang=None, label_dist=None):
        self.name = name
        self.lat = float(lat)
        self.lon = float(lon)
        self.country = country
        self.aliases = aliases if aliases else []
        self.label_ang = label_ang
        self.label_dist = label_dist

SEED_CITIES = [
    # ============================================================================
    # LABEL POSITION GUIDE:
    # label_ang: Angle in degrees (0=→right, 90=↓down, -90=↑up, 180=←left, 45=↘, -45=↗, etc.)
    # label_dist: Distance multiplier (1.0=default 8px×SS, 1.5=12px×SS, 2.0=16px×SS)
    # Adjust these values to fine-tune label positions!
    # ============================================================================
    
    # VN - NORTH (Hanoi cluster)
    City("Ha Noi", 21.0278, 105.8342, "VN", ["Hanoi","Ha-Noi","Noi Bai","Noi Bai Airport"], label_ang=0, label_dist=1.0),
    City("Ha Long", 20.9714, 107.0448, "VN", ["Halong","Tuan Chau","Lan Ha","Cat Ba"], label_ang=0, label_dist=1.5),
    City("Ninh Binh", 20.2574, 105.9797, "VN", ["Tam Coc","Trang An"], label_ang=90, label_dist=1.2),
    City("Hai Phong", 20.8449, 106.6881, "VN", ["Haiphong"], label_ang=-90, label_dist=1.0),
    City("Cat Ba", 20.8, 107.05, "VN", [], label_ang=45, label_dist=1.0),
    City("Bac Ninh", 21.1861, 106.0763, "VN", [], label_ang=-90, label_dist=1.0),
    City("Thai Nguyen", 21.5671, 105.8252, "VN", [], label_ang=-45, label_dist=1.0),
    City("Quang Ninh", 21.0064, 107.2925, "VN", [], label_ang=0, label_dist=1.0),
    
    # VN - NORTHWEST (Sapa cluster)
    City("Sapa", 22.3364, 103.8438, "VN", ["Sa Pa", "Lao Cai"], label_ang=-90, label_dist=1.0),
    City("Ha Giang", 22.8233, 104.9836, "VN", [], label_ang=-45, label_dist=1.0),
    City("Bac Ha", 22.5333, 104.3000, "VN", [], label_ang=0, label_dist=1.0),
    City("Yen Bai", 21.7167, 104.8667, "VN", [], label_ang=180, label_dist=1.0),
    City("Cao Bang", 22.6667, 106.2500, "VN", [], label_ang=0, label_dist=1.0),
    City("Lang Son", 21.8536, 106.7610, "VN", [], label_ang=0, label_dist=1.0),
    City("Tuyen Quang", 21.8167, 105.2167, "VN", [], label_ang=-90, label_dist=1.0),
    City("Phu Tho", 21.2689, 105.2045, "VN", [], label_ang=180, label_dist=1.0),
    City("Bac Giang", 21.2819, 106.1973, "VN", [], label_ang=90, label_dist=1.0),
    
    # VN - NORTHWEST MOUNTAINS (Mai Chau cluster)
    City("Mai Chau", 20.6603, 105.0786, "VN", [], label_ang=180, label_dist=1.0),
    City("Pu Luong", 20.4682, 105.1869, "VN", [], label_ang=90, label_dist=1.0),
    City("Hoa Binh", 20.8136, 105.3388, "VN", [], label_ang=-90, label_dist=1.0),
    City("Moc Chau", 20.8333, 104.6833, "VN", [], label_ang=180, label_dist=1.0),
    City("Son La", 21.3167, 103.9000, "VN", [], label_ang=-90, label_dist=1.0),
    City("Dien Bien Phu", 21.3833, 103.0167, "VN", ["Dien Bien"], label_ang=180, label_dist=1.0),
    
    # VN - RED RIVER DELTA
    City("Nam Dinh", 20.4167, 106.1667, "VN", [], label_ang=90, label_dist=1.0),
    City("Thai Binh", 20.4500, 106.3333, "VN", [], label_ang=0, label_dist=1.0),
    City("Ha Nam", 20.5833, 105.9167, "VN", [], label_ang=180, label_dist=1.0),
    
    # VN - NORTH CENTRAL (Vinh - Dong Hoi)
    City("Thanh Hoa", 19.8067, 105.7761, "VN", [], label_ang=180, label_dist=1.0),
    City("Vinh", 18.6792, 105.6919, "VN", [], label_ang=180, label_dist=1.0),
    City("Dong Hoi", 17.4833, 106.6000, "VN", ["Phong Nha"], label_ang=0, label_dist=1.2),
    City("Quang Tri", 16.7943, 107.1856, "VN", [], label_ang=-90, label_dist=1.0),
    
    # VN - CENTRAL (Hue - Da Nang - Hoi An cluster) - IMPORTANT: spread in different directions!
    City("Hue", 16.4637, 107.5909, "VN", [], label_ang=-90, label_dist=1.2),
    City("Da Nang", 16.0678, 108.2208, "VN", ["Danang"], label_ang=0, label_dist=1.0),
    City("Hoi An", 15.8801, 108.338, "VN", ["Hoi-An","Ancient Town"], label_ang=45, label_dist=1.0),
    City("Thua Thien Hue", 16.4637, 107.5909, "VN", [], label_ang=135, label_dist=1.0),
    City("Quang Nam", 15.5394, 108.0191, "VN", [], label_ang=90, label_dist=1.0),
    City("Quang Ngai", 15.1214, 108.8044, "VN", [], label_ang=0, label_dist=1.0),
    
    # VN - SOUTH CENTRAL COAST
    City("Quy Nhon", 13.7830, 109.2194, "VN", [], label_ang=0, label_dist=1.0),
    City("Nha Trang", 12.2388, 109.1967, "VN", [], label_ang=0, label_dist=1.0),
    City("Phan Rang", 11.5667, 108.9833, "VN", [], label_ang=0, label_dist=1.0),
    City("Binh Dinh", 13.7829, 109.2196, "VN", [], label_ang=45, label_dist=1.0),
    City("Phu Yen", 13.0881, 109.0929, "VN", [], label_ang=-45, label_dist=1.0),
    City("Khanh Hoa", 12.2585, 109.0526, "VN", [], label_ang=90, label_dist=1.0),
    City("Ninh Thuan", 11.6739, 108.8629, "VN", [], label_ang=45, label_dist=1.0),
    
    # VN - CENTRAL HIGHLANDS
    City("Dalat", 11.9404, 108.4583, "VN", ["Da Lat"], label_ang=180, label_dist=1.0),
    City("Pleiku", 13.9833, 108.0000, "VN", [], label_ang=180, label_dist=1.0),
    City("Buon Ma Thuot", 12.6667, 108.0500, "VN", ["Buon Me Thuot","BMT"], label_ang=180, label_dist=1.0),
    City("Kon Tum", 14.3497, 108.0005, "VN", [], label_ang=-90, label_dist=1.0),
    
    # VN - SOUTHEAST (Saigon cluster)
    City("Sai Gon", 10.8231, 106.6297, "VN", ["Ho Chi Minh","Ho Chi Minh City","HCMC","Saigon","SGN"], label_ang=-17, label_dist=3.0),
    City("Mui Ne", 10.9333, 108.2833, "VN", ["Phan Thiet"], label_ang=0, label_dist=1.0),
    City("Vung Tau", 10.3460, 107.0843, "VN", [], label_ang=90, label_dist=1.0),
    City("Binh Thuan", 11.0904, 108.0721, "VN", [], label_ang=-90, label_dist=1.0),
    City("Con Dao", 8.6833, 106.6000, "VN", [], label_ang=90, label_dist=1.0),
    
    # VN - MEKONG DELTA
    City("Can Tho", 10.0452, 105.7469, "VN", [], label_ang=45, label_dist=1.8),
    City("Chau Doc", 10.702, 105.117, "VN", [], label_ang=180, label_dist=1.0),
    City("Phu Quoc", 10.2899, 103.9840, "VN", [], label_ang=-178, label_dist=9.9),
    City("Ben Tre", 10.2433, 106.3753, "VN", [], label_ang=0, label_dist=1.0),
    City("Rach Gia", 10.0107, 105.0833, "VN", [], label_ang=168, label_dist=7.9),
    City("Long Xuyen", 10.3867, 105.4350, "VN", [], label_ang=-90, label_dist=1.0),
    City("Sa Dec", 10.2917, 105.7569, "VN", [], label_ang=90, label_dist=1.0),
    City("Vinh Long", 10.2500, 105.9667, "VN", [], label_ang=45, label_dist=1.0),
    City("My Tho", 10.3600, 106.3600, "VN", [], label_ang=0, label_dist=1.0),
    City("Tra Vinh", 9.9347, 106.3456, "VN", [], label_ang=90, label_dist=1.0),
    City("Soc Trang", 9.6033, 105.9800, "VN", [], label_ang=90, label_dist=1.0),
    City("Ca Mau", 9.1769, 105.1500, "VN", [], label_ang=90, label_dist=1.0),
    City("Bac Lieu", 9.2833, 105.7333, "VN", [], label_ang=0, label_dist=1.0),
    
    # LAOS
    City("Luang Prabang", 19.8897, 102.135, "LA", ["Luang-Prabang","LP"], label_ang=90, label_dist=1.0),
    City("Pak Ou", 20.05, 102.21, "LA", ["Pak-Ou", "Pak Ou Cave"], label_ang=-90, label_dist=1.0),
    City("Khuang Si", 19.7486, 101.9931, "LA", ["Kuang Si", "Kuang Si Falls", "Tat Kuang Si"], label_ang=180, label_dist=1.0),
    City("Vientiane", 17.9757, 102.6331, "LA", ["Vieng Chan"], label_ang=0, label_dist=1.0),
    City("Vang Vieng", 18.925, 102.447, "LA", [], label_ang=0, label_dist=1.0),
    
    # CAMBODIA
    City("Siem Reap", 13.3622, 103.8597, "KH", ["Angkor","Tonle Sap"], label_ang=-18, label_dist=2.0),
    City("Phnom Penh", 11.5564, 104.9282, "KH", ["Pnom Penh"], label_ang=-56, label_dist=2.2),
    City("Battambang", 13.0957, 103.2022, "KH", [], label_ang=180, label_dist=1.0),
    City("Kampot", 10.6167, 104.1833, "KH", [], label_ang=90, label_dist=1.0),
    City("Kep", 10.4833, 104.3167, "KH", [], label_ang=0, label_dist=1.0),
    City("Sihanoukville", 10.6333, 103.5000, "KH", ["Kampong Som"], label_ang=180, label_dist=1.0),
    
    # THAILAND
    City("Bangkok", 13.7563, 100.5018, "TH", ["BKK","Suvarnabhumi"], label_ang=0, label_dist=1.0),
    City("Chiang Mai", 18.7883, 98.9853, "TH", ["CM"], label_ang=-90, label_dist=1.0),
    City("Chiang Rai", 19.9105, 99.8406, "TH", [], label_ang=-45, label_dist=1.0),
    City("Phuket", 7.8804, 98.3923, "TH", [], label_ang=180, label_dist=1.0),
    City("Krabi", 8.0863, 98.9063, "TH", [], label_ang=0, label_dist=1.0),
    City("Koh Samui", 9.5357, 100.0633, "TH", ["Samui"], label_ang=0, label_dist=1.0),
    City("Pattaya", 12.9236, 100.8825, "TH", [], label_ang=0, label_dist=1.0),
    City("Ayutthaya", 14.3532, 100.5775, "TH", [], label_ang=-90, label_dist=1.0),
    City("Sukhothai", 17.0061, 99.8230, "TH", [], label_ang=180, label_dist=1.0),
    City("Pai", 19.3581, 98.4405, "TH", [], label_ang=-90, label_dist=1.0),
    City("Mae Hong Son", 19.3014, 97.9656, "TH", [], label_ang=180, label_dist=1.0),
    City("Kanchanaburi", 14.0227, 99.5328, "TH", [], label_ang=180, label_dist=1.0),
]


def _city_to_record(city):
    return {
        "name": city.name,
        "lat": city.lat,
        "lon": city.lon,
        "country": city.country,
        "aliases": list(city.aliases or []),
        "label_ang": city.label_ang,
        "label_dist": city.label_dist,
    }


def _ensure_json_file(path, default_payload):
    if os.path.exists(path):
        return
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w", encoding="utf-8") as handle:
        json.dump(default_payload, handle, ensure_ascii=False, indent=2)


def _write_cities_master(cities):
    payload = [_city_to_record(city) for city in cities]
    os.makedirs(os.path.dirname(CITIES_MASTER_FILE), exist_ok=True)
    with open(CITIES_MASTER_FILE, "w", encoding="utf-8") as handle:
        json.dump(payload, handle, ensure_ascii=False, indent=2)


def _load_anchor_presets():
    default_payload = {
        base_name: {city_name: list(xy) for city_name, xy in anchors.items()}
        for base_name, anchors in DEFAULT_ANCHORS_PRESETS.items()
    }
    _ensure_json_file(ANCHORS_DEFAULT_FILE, default_payload)

    try:
        with open(ANCHORS_DEFAULT_FILE, "r", encoding="utf-8") as handle:
            raw_data = json.load(handle)
    except Exception:
        return DEFAULT_ANCHORS_PRESETS

    loaded = {}
    for base_name, anchor_blob in raw_data.items():
        base_name = normalize_base_map_name(base_name)
        anchors = {}
        if isinstance(anchor_blob, dict) and "presets" in anchor_blob:
            default_list = anchor_blob.get("presets", {}).get("_default", [])
            for item in default_list:
                if isinstance(item, dict) and "name" in item and "xy" in item:
                    anchors[item["name"]] = tuple(item["xy"])
        elif isinstance(anchor_blob, dict):
            for city_name, xy in anchor_blob.items():
                if isinstance(xy, dict) and "xy" in xy:
                    anchors[city_name] = tuple(xy["xy"])
                elif isinstance(xy, (list, tuple)) and len(xy) == 2:
                    anchors[city_name] = tuple(xy)
        if anchors:
            loaded.setdefault(base_name, {}).update(anchors)

    return loaded or DEFAULT_ANCHORS_PRESETS


def _load_seed_cities():
    default_payload = [_city_to_record(city) for city in SEED_CITIES]
    _ensure_json_file(CITIES_MASTER_FILE, default_payload)

    try:
        with open(CITIES_MASTER_FILE, "r", encoding="utf-8") as handle:
            raw_data = json.load(handle)
    except Exception:
        return SEED_CITIES

    loaded = []
    for item in raw_data:
        if not isinstance(item, dict):
            continue
        name = item.get("name")
        lat = item.get("lat")
        lon = item.get("lon")
        if name is None or lat is None or lon is None:
            continue
        loaded.append(
            City(
                name=name,
                lat=lat,
                lon=lon,
                country=item.get("country", "VN"),
                aliases=item.get("aliases", []),
                label_ang=item.get("label_ang"),
                label_dist=item.get("label_dist"),
            )
        )

    return loaded or SEED_CITIES


ANCHORS_PRESETS = _load_anchor_presets()
SEED_CITIES = _load_seed_cities()


# OSM Nominatim API for geocoding
OSM_NOMINATIM_URL = "https://nominatim.openstreetmap.org/search"

def nominatim_geocode(query, country_codes="vn,la,kh,th,mm", limit=1):
    """
    Geocode a place name using OpenStreetMap Nominatim API.
    Returns dict with name, lat, lon, country or None if not found.
    """
    import requests
    try:
        params = {
            "q": query,
            "format": "jsonv2",
            "limit": limit,
            "accept-language": "en",
            "countrycodes": country_codes
        }
        headers = {"User-Agent": "TonkinTourAssistant/1.0"}
        resp = requests.get(OSM_NOMINATIM_URL, params=params, headers=headers, timeout=5)
        resp.raise_for_status()
        data = resp.json()
        if data:
            item = data[0]
            lat = float(item.get("lat", 0))
            lon = float(item.get("lon", 0))
            display_name = item.get("display_name", query)
            # Extract country code from display_name or address
            country = "VN"  # Default
            if "Lào" in display_name or "Laos" in display_name:
                country = "LA"
            elif "Campuchia" in display_name or "Cambodia" in display_name:
                country = "KH"
            elif "Thái Lan" in display_name or "Thailand" in display_name:
                country = "TH"
            elif "Myanmar" in display_name:
                country = "MM"
            
            return {"name": query, "lat": lat, "lon": lon, "country": country}
    except Exception as e:
        print(f"Nominatim geocode error for '{query}': {e}")
    return None


LOCATION_SKIP_PHRASES = {
    "arrival", "arrivee", "arrive", "depart", "departure", "arrivo", "partenza",
    "visit", "visite", "visita", "excursion", "escursione",
    "free time", "temps libre", "tempo libero", "leisure",
    "with guide", "avec guide", "con guida", "without guide", "sans guide",
    "with driver", "avec chauffeur", "sans chauffeur", "private", "prive", "privato",
    "group", "en groupe", "gruppo", "english speaking", "french speaking", "francophone",
    "anglophone", "transfer", "transfert", "trasferimento", "shuttle",
    "breakfast", "lunch", "dinner", "meal", "petit dejeuner", "dejeuner", "diner",
    "colazione", "pranzo", "cena", "pasto", "night", "overnight", "accommodation",
    "spa", "massage", "cooking class", "cours de cuisine", "corso di cucina",
    "market", "shopping", "workshop", "atelier", "temple", "pagoda", "museum", "musee",
    "floating village", "village flottant", "villaggio galleggiante",
}

LOCATION_DROP_PREFIXES = [
    r"^(?:day|jour|ngay|giorno)\s+\d+[:\s-]*",
    r"^(?:vol|flight|plane|volo)\s+(?:pour|vers|to|from|de|da|a)\s+",
    r"^(?:arrivee|arrival|arrivo|depart|departure|partenza)\s+(?:a|to|vers|de|from)?\s*",
]

LOCATION_DROP_SUFFIXES = [
    r"\s*\([^)]*\)\s*$",
    r"\s*\[[^\]]*\]\s*$",
    r"\s+(?:arrival|arrivee|arrivo|departure|depart|partenza).*$",
    r"\s+(?:visit|visite|visita|excursion|escursione|free time|temps libre|tempo libero).*$",
    r"\s+(?:with guide|avec guide|con guida|sans guide|with driver|avec chauffeur|sans chauffeur).*$",
    r"\s+(?:private|prive|privato|group|en groupe|gruppo).*$",
    r"\s+(?:breakfast|lunch|dinner|meal|petit dejeuner|dejeuner|diner|colazione|pranzo|cena).*$",
    r"\s*&\s*(?:arrival|arrivee|depart|departure|arrivo|partenza).*$",
    r"\s*&\s+.*$",
    r"\s*,\s+.*$",
]

COUNTRY_WORDS = {
    "vietnam", "viet nam", "laos", "cambodia", "cambodge", "thailand", "thailande",
    "myanmar", "birmanie", "burma", "indochina", "indochine",
}

GENERIC_LOCATION_WORDS = {
    "reserve", "naturelle", "natural", "park", "national", "river", "beach", "bay",
    "waterfall", "falls", "sanctuary", "village", "floating", "delta", "lake", "mountain",
    "airport", "station", "pier", "port", "harbor", "hotel", "resort", "homestay",
    "flottant", "galleggiante", "plage", "spiaggia", "ile", "isola", "baie",
}

ROUTE_SPLIT_PATTERN = re.compile(r"\s*(?:->|>|/|\||;|\s+-\s+|,\s+|\s*&\s+)\s*")


def _strip_accents(value: str) -> str:
    return "".join(
        char for char in unicodedata.normalize("NFKD", value or "")
        if not unicodedata.combining(char)
    )


def normalize_location_text(value: str) -> str:
    text = _strip_accents(value)
    text = unicodedata.normalize("NFKC", text)
    text = text.lower()
    text = re.sub(r"[’'`]", "", text)
    text = re.sub(r"[&/,;:()\[\]{}]", " ", text)
    text = re.sub(r"[–—−‑‒―<>|/]+", " ", text)
    text = re.sub(r"[^a-z0-9\s-]", " ", text)
    text = re.sub(r"[-]+", " ", text)
    text = re.sub(r"\s+", " ", text).strip()
    return text


def clean_location_fragment(fragment: str) -> str:
    text = unicodedata.normalize("NFKC", fragment or "").strip()
    text = re.sub(r"[–—−‑‒―]", "-", text)
    for pattern in LOCATION_DROP_PREFIXES:
        text = re.sub(pattern, "", text, flags=re.I).strip()
    for pattern in LOCATION_DROP_SUFFIXES:
        text = re.sub(pattern, "", text, flags=re.I).strip()
    text = re.sub(r"\s+", " ", text).strip(" -")
    return text


def looks_like_location_candidate(fragment: str) -> bool:
    cleaned = clean_location_fragment(fragment)
    normalized = normalize_location_text(cleaned)
    if not normalized or len(normalized) < 3 or normalized.isdigit():
        return False
    if normalized in COUNTRY_WORDS:
        return False
    if any(re.search(rf"(?<![a-z0-9]){re.escape(phrase)}(?![a-z0-9])", normalized) for phrase in LOCATION_SKIP_PHRASES):
        return False
    tokens = normalized.split()
    if len(tokens) > 6:
        return False
    if all(token in GENERIC_LOCATION_WORDS or token in COUNTRY_WORDS for token in tokens):
        return False
    return True

class CityDB:
    def __init__(self):
        self.by_name = {}
        self.alias2name = {}
        self.alias_entries = []
        for c in SEED_CITIES:
            self.add(c)
    
    def add(self, c):
        self.by_name[c.name] = c
        keys = [c.name] + c.aliases
        for k in keys:
            normalized = normalize_location_text(k)
            if normalized:
                self.alias2name[normalized] = c.name
        self.alias_entries = sorted(
            self.alias2name.items(),
            key=lambda item: (len(item[0].split()), len(item[0])),
            reverse=True,
        )

    def extract_cities(self, text):
        normalized_text = normalize_location_text(text)
        if not normalized_text:
            return []

        matches = []
        occupied = []
        for alias, canonical in self.alias_entries:
            if len(alias) < 3:
                continue
            pattern = re.compile(rf"(?<![a-z0-9]){re.escape(alias)}(?![a-z0-9])")
            for match in pattern.finditer(normalized_text):
                start, end = match.span()
                if any(not (end <= used_start or start >= used_end) for used_start, used_end in occupied):
                    continue
                occupied.append((start, end))
                matches.append((start, canonical))

        matches.sort(key=lambda item: item[0])

        ordered = []
        seen = set()
        for _, canonical in matches:
            if canonical not in seen:
                ordered.append(canonical)
                seen.add(canonical)
        return ordered

    def find_city(self, name, auto_geocode=False):
        """
        Find city by name. If auto_geocode=True and not found, 
        try to geocode from OSM and add to database.
        """
        name_clean = clean_location_fragment(name)
        name_lower = normalize_location_text(name_clean)
        
        # Direct match
        if name_lower in self.alias2name:
            return self.by_name[self.alias2name[name_lower]]
        
        extracted = self.extract_cities(name_clean)
        if len(extracted) == 1:
            return self.by_name.get(extracted[0])
        
        # Auto-geocode if enabled
        if auto_geocode:
            print(f"🌐 City '{name_clean}' not in DB, trying Nominatim...")
            geo = nominatim_geocode(name_clean)
            if geo:
                new_city = City(
                    name=geo["name"],
                    lat=geo["lat"],
                    lon=geo["lon"],
                    country=geo["country"],
                    aliases=[]
                )
                self.add(new_city)
                print(f"✅ Added '{new_city.name}' ({geo['lat']}, {geo['lon']}) to database")
                return new_city
            else:
                print(f"❌ Could not geocode '{name_clean}'")
        
        return None
    
    def geocode_and_add(self, name):
        """
        Explicitly geocode a city and add to database.
        Returns the new City object or None.
        """
        geo = nominatim_geocode(name)
        if geo:
            new_city = City(
                name=geo["name"],
                lat=geo["lat"],
                lon=geo["lon"],
                country=geo["country"],
                aliases=[]
            )
            self.add(new_city)
            return new_city
        return None

DB = CityDB()


def save_label_overrides_to_file(overrides):
    """
    Save label position overrides into assets/cities_master.json.

    Args:
        overrides: dict {city_name: {"angle": float, "distance": float}}

    Returns:
        tuple: (success: bool, message: str)
    """
    try:
        _write_cities_master(SEED_CITIES)
        with open(CITIES_MASTER_FILE, "r", encoding="utf-8") as handle:
            records = json.load(handle)

        record_map = {
            normalize_location_text(record.get("name", "")): record
            for record in records
            if isinstance(record, dict) and record.get("name")
        }

        changes_made = 0
        for city_name, values in overrides.items():
            angle = int(round(values.get("angle", 0)))
            distance = round(values.get("distance", 1.0), 1)
            lookup_keys = [
                normalize_location_text(city_name),
                normalize_location_text(city_name.replace(" ", "-")),
                normalize_location_text(city_name.replace("-", " ")),
            ]

            target_record = None
            for lookup_key in lookup_keys:
                if lookup_key in record_map:
                    target_record = record_map[lookup_key]
                    break

            if not target_record:
                continue

            target_record["label_ang"] = angle
            target_record["label_dist"] = distance
            changes_made += 1

            matched_city = DB.find_city(city_name)
            if matched_city:
                matched_city.label_ang = angle
                matched_city.label_dist = distance

        if changes_made > 0:
            with open(CITIES_MASTER_FILE, "w", encoding="utf-8") as handle:
                json.dump(records, handle, ensure_ascii=False, indent=2)
            return True, f"Đã lưu {changes_made} thay đổi vào cities_master.json"
        return False, "Không tìm thấy city nào trong cities_master.json để cập nhật"
    except Exception as e:
        return False, f"Lỗi: {str(e)}"


def persist_cities_master():
    try:
        _write_cities_master(SEED_CITIES)
        return True, "Saved cities_master.json"
    except Exception as exc:
        return False, str(exc)


def save_city_to_master(name, lat, lon, country="VN", aliases=None):
    canonical_name = clean_location_fragment(name)
    if not canonical_name:
        return False, "Empty city name", None

    alias_candidates = []
    for alias_name in aliases or []:
        cleaned = clean_location_fragment(alias_name)
        if cleaned:
            alias_candidates.append(cleaned)

    existing = DB.find_city(canonical_name)
    if existing:
        existing.lat = float(lat)
        existing.lon = float(lon)
        existing.country = country or existing.country
        normalized_existing_aliases = {
            normalize_location_text(existing.name),
            *[normalize_location_text(alias) for alias in existing.aliases],
        }
        for alias_name in alias_candidates:
            normalized_alias = normalize_location_text(alias_name)
            if normalized_alias and normalized_alias not in normalized_existing_aliases:
                existing.aliases.append(alias_name)
                normalized_existing_aliases.add(normalized_alias)
        DB.add(existing)
        ok, message = persist_cities_master()
        return ok, message, existing.name

    deduped_aliases = []
    seen_aliases = {normalize_location_text(canonical_name)}
    for alias_name in alias_candidates:
        normalized_alias = normalize_location_text(alias_name)
        if normalized_alias and normalized_alias not in seen_aliases:
            deduped_aliases.append(alias_name)
            seen_aliases.add(normalized_alias)

    new_city = City(
        name=canonical_name,
        lat=lat,
        lon=lon,
        country=country or "VN",
        aliases=deduped_aliases,
    )
    SEED_CITIES.append(new_city)
    DB.add(new_city)
    ok, message = persist_cities_master()
    return ok, message, new_city.name


def add_alias_to_city(alias_name, canonical_name):
    alias_clean = clean_location_fragment(alias_name)
    if not alias_clean:
        return False, "Empty alias", None

    canonical_city = DB.find_city(canonical_name)
    if not canonical_city:
        return False, f"City not found: {canonical_name}", None

    alias_normalized = normalize_location_text(alias_clean)
    canonical_normalized = normalize_location_text(canonical_city.name)
    if alias_normalized == canonical_normalized:
        return False, "Alias matches canonical name", canonical_city.name

    existing_alias_owner = DB.find_city(alias_clean)
    if existing_alias_owner and existing_alias_owner.name != canonical_city.name:
        return False, f"Alias already belongs to {existing_alias_owner.name}", canonical_city.name

    existing_aliases = {
        normalize_location_text(canonical_city.name),
        *[normalize_location_text(alias) for alias in canonical_city.aliases],
    }
    if alias_normalized not in existing_aliases:
        canonical_city.aliases.append(alias_clean)
        DB.add(canonical_city)
        ok, message = persist_cities_master()
        return ok, message, canonical_city.name

    return True, "Alias already exists", canonical_city.name


def canonical_city_name(name):
    if not name:
        return None
    city = DB.find_city(name)
    if city:
        return city.name
    cleaned = clean_location_fragment(name)
    return cleaned or name


def ordered_route_cities(route):
    ordered = []
    for leg in route or []:
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if a_name and (not ordered or ordered[-1] != a_name):
            ordered.append(a_name)
        if b_name and (not ordered or ordered[-1] != b_name):
            ordered.append(b_name)
    return ordered


def default_landmark_cities(base_map_name, hidden_cities=None):
    base_map_name = normalize_base_map_name(base_map_name)
    hidden_set = {
        canonical_city_name(city_name)
        for city_name in (hidden_cities or [])
        if canonical_city_name(city_name)
    }
    landmarks = set()
    for city_name in DEFAULT_LANDMARKS_BY_BASE_MAP.get(base_map_name, []):
        canonical = canonical_city_name(city_name)
        if canonical and canonical not in hidden_set:
            landmarks.add(canonical)
    return landmarks


def compute_visible_cities(route, visibility_mode="all", hidden_cities=None,
                           arrival_city=None, departure_city=None,
                           manual_icons=None, label_overrides=None):
    ordered = ordered_route_cities(route)
    all_cities = set(ordered)
    if not all_cities:
        return set()

    visibility_mode = (visibility_mode or "all").lower()
    hidden_set = {
        canonical_city_name(city_name)
        for city_name in (hidden_cities or [])
        if canonical_city_name(city_name)
    }
    always_visible = {
        canonical_city_name(arrival_city),
        canonical_city_name(departure_city),
    }
    protected = set(always_visible)
    protected.update(
        canonical_city_name(icon.get("city"))
        for icon in (manual_icons or [])
        if icon.get("city")
    )
    protected.update(
        canonical_city_name(city_name)
        for city_name in (label_overrides or {}).keys()
    )
    protected.discard(None)

    if visibility_mode == "custom":
        return {city for city in all_cities if city not in hidden_set} | {city for city in always_visible if city}

    if visibility_mode != "major":
        return all_cities

    visible = set()
    visible.add(ordered[0])
    visible.add(ordered[-1])
    visible.update(protected)

    city_degree = {}
    ordered_counts = {}
    for city_name in ordered:
        ordered_counts[city_name] = ordered_counts.get(city_name, 0) + 1

    for leg in route or []:
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if a_name:
            city_degree[a_name] = city_degree.get(a_name, 0) + 1
        if b_name:
            city_degree[b_name] = city_degree.get(b_name, 0) + 1
        if leg.get("mode") == "plane":
            if a_name:
                visible.add(a_name)
            if b_name:
                visible.add(b_name)

    for idx, city_name in enumerate(ordered[1:-1], start=1):
        prev_leg = route[idx - 1] if idx - 1 < len(route) else None
        next_leg = route[idx] if idx < len(route) else None
        prev_mode = prev_leg.get("mode") if prev_leg else None
        next_mode = next_leg.get("mode") if next_leg else None
        if prev_mode != next_mode:
            visible.add(city_name)
            continue
        if city_degree.get(city_name, 0) > 2:
            visible.add(city_name)
            continue
        if ordered_counts.get(city_name, 0) > 1:
            visible.add(city_name)

    return visible & all_cities


MINOR_STOP_HINTS = {
    "beach", "bay", "cave", "caves", "falls", "fall", "island", "islands",
    "park", "reserve", "village", "floating", "temple", "pagoda", "pier",
    "port", "harbor", "airport", "station", "lake", "mountain", "forest",
    "plage", "baie", "ile", "iles", "flottant", "cascade", "grotte", "isola",
    "spiaggia", "parc", "reserve", "naturelle",
}


def visibility_protected_cities(arrival_city=None, departure_city=None,
                                manual_icons=None, label_overrides=None):
    protected = set()
    for city_name in [arrival_city, departure_city]:
        canonical = canonical_city_name(city_name)
        if canonical:
            protected.add(canonical)
    for icon in manual_icons or []:
        canonical = canonical_city_name(icon.get("city"))
        if canonical:
            protected.add(canonical)
    for city_name in (label_overrides or {}).keys():
        canonical = canonical_city_name(city_name)
        if canonical:
            protected.add(canonical)
    return protected


def city_visibility_score(city_name, route, ordered_cities, protected_cities):
    if city_name in protected_cities:
        return 100

    score = 0
    if ordered_cities:
        if city_name == ordered_cities[0]:
            score += 40
        if city_name == ordered_cities[-1]:
            score += 40

    degree = 0
    repeated = 0
    plane_touch = False
    mode_change = False
    ordered_counts = {}
    for name in ordered_cities:
        ordered_counts[name] = ordered_counts.get(name, 0) + 1
    repeated = ordered_counts.get(city_name, 0)

    for idx, leg in enumerate(route or []):
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if city_name in {a_name, b_name}:
            degree += 1
            if leg.get("mode") == "plane":
                plane_touch = True
        if idx < len(route) - 1:
            next_leg = route[idx + 1]
            pivot = canonical_city_name(leg.get("b"))
            if pivot == city_name and canonical_city_name(next_leg.get("a")) == city_name:
                if leg.get("mode") != next_leg.get("mode"):
                    mode_change = True

    if plane_touch:
        score += 25
    if mode_change:
        score += 20
    if degree > 2:
        score += 15
    if repeated > 1:
        score += 8

    tokens = normalize_location_text(city_name).split()
    if len(tokens) >= 3:
        score -= 3
    if any(token in MINOR_STOP_HINTS for token in tokens):
        score -= 12

    return score


def compact_visible_cities(route, visible_cities, get_xy, base_map_name="Vietnam",
                           arrival_city=None, departure_city=None,
                           manual_icons=None, label_overrides=None):
    ordered = ordered_route_cities(route)
    if not ordered:
        return visible_cities

    protected = visibility_protected_cities(
        arrival_city=arrival_city,
        departure_city=departure_city,
        manual_icons=manual_icons,
        label_overrides=label_overrides,
    )
    visible_order = []
    for city_name in ordered:
        if city_name in visible_cities and (not visible_order or visible_order[-1] != city_name):
            visible_order.append(city_name)
    if len(visible_order) <= 2:
        return set(visible_order)

    cluster_threshold = 95 if base_map_name == "Vietnam" else 80
    clusters = []
    current_cluster = [visible_order[0]]
    previous_point = get_xy(visible_order[0])

    for city_name in visible_order[1:]:
        point = get_xy(city_name)
        if not previous_point or not point:
            clusters.append(current_cluster)
            current_cluster = [city_name]
            previous_point = point
            continue

        gap = math.hypot(point[0] - previous_point[0], point[1] - previous_point[1])
        if gap <= cluster_threshold:
            current_cluster.append(city_name)
        else:
            clusters.append(current_cluster)
            current_cluster = [city_name]
        previous_point = point

    if current_cluster:
        clusters.append(current_cluster)

    compacted = set()
    for cluster in clusters:
        if len(cluster) <= 2:
            compacted.update(cluster)
            continue

        keep = {cluster[0], cluster[-1]}
        keep.update(city for city in cluster if city in protected)

        base_budget = 0 if len(cluster) <= 3 else 1 if len(cluster) <= 5 else 2
        candidate_scores = []
        for city_name in cluster[1:-1]:
            score = city_visibility_score(city_name, route, ordered, protected)
            candidate_scores.append((score, city_name))
            if score >= 25:
                keep.add(city_name)

        remaining_budget = max(0, base_budget - len([city for city in keep if city in cluster[1:-1]]))
        for _, city_name in sorted(candidate_scores, key=lambda item: item[0], reverse=True):
            if remaining_budget <= 0:
                break
            if city_name in keep:
                continue
            keep.add(city_name)
            remaining_budget -= 1

        compacted.update(keep)

    return compacted


def extract_ordered_locations(text, include_unknown=True):
    """
    Extract ordered location candidates from a route fragment.

    Returns canonical DB city names when matched, otherwise keeps a cleaned
    unknown candidate only if it still looks like a location.
    """
    if not text:
        return []

    fragments = ROUTE_SPLIT_PATTERN.split(unicodedata.normalize("NFKC", text))
    ordered = []
    seen = set()

    for fragment in fragments:
        cleaned = clean_location_fragment(fragment)
        if not cleaned:
            continue

        matched = DB.extract_cities(cleaned)
        if matched:
            for city_name in matched:
                key = normalize_location_text(city_name)
                if key not in seen:
                    ordered.append(city_name)
                    seen.add(key)
            continue

        if include_unknown and looks_like_location_candidate(cleaned):
            key = normalize_location_text(cleaned)
            if key not in seen:
                ordered.append(cleaned)
                seen.add(key)

    return ordered


# =========================
# GEOMETRY & AFFINE
# =========================
def solve_affine(latlons, xys):
    A, B = [], []
    for (lon, lat), (X, Y) in zip(latlons, xys):
        A.append([lon, lat, 1, 0, 0, 0]); B.append(X)
        A.append([0, 0, 0, lon, lat, 1]); B.append(Y)
    A = np.array(A, dtype=float); B = np.array(B, dtype=float)
    try:
        p, *_ = np.linalg.lstsq(A, B, rcond=None)
        return p.reshape(2, 3)
    except:
        return np.eye(2, 3) # Fallback

def apply_affine(M, lon, lat):
    v = np.array([lon, lat, 1.0])
    x, y = M @ v
    return float(x), float(y)

def quad_point(p0, p1, p2, t):
    x = (1-t)**2*p0[0] + 2*(1-t)*t*p1[0] + t**2 * p2[0]
    y = (1-t)**2*p0[1] + 2*(1-t)*t*p1[1] + t**2 * p2[1]
    return (x, y)

def control_point(p0, p2, bulge=0.25):
    mx, my = (p0[0]+p2[0])/2, (p0[1]+p2[1])/2
    dx, dy = p2[0]-p0[0], p2[1]-p0[1]
    L = math.hypot(dx,dy) + 1e-6
    nx, ny = -dy/L, dx/L
    return (mx + nx * L * bulge, my + ny * L * bulge)

def sample_curve(p0, p1, p2, n=200):
    return [quad_point(p0,p1,p2,i/(n-1)) for i in range(n)]

def radial_point(center, angle_deg, distance):
    """Calculate a point at a given angle and distance from center"""
    rad = math.radians(angle_deg)
    x = center[0] + math.cos(rad) * distance
    y = center[1] + math.sin(rad) * distance
    return (x, y)

def draw_line(draw, pts, color, width):
    """Draw a solid line through points"""
    try:
        draw.line(pts, fill=color, width=width, joint="curve")
    except TypeError:
        draw.line(pts, fill=color, width=width)

def draw_dashed(draw, pts, color, width, dash_on=DASH_ON, dash_off=DASH_OFF):
    """Draw a dashed line through points"""
    if not pts or len(pts) < 2:
        return
    
    pattern = [dash_on, dash_off]
    idx = 0
    remain = pattern[idx]
    on_seg = True
    
    x0, y0 = pts[0]
    for k in range(1, len(pts)):
        x1, y1 = pts[k]
        seg = math.hypot(x1 - x0, y1 - y0)
        
        while seg > 1e-6:
            step = min(remain, seg)
            r = step / seg
            xm, ym = x0 + (x1 - x0) * r, y0 + (y1 - y0) * r
            
            if on_seg:
                draw.line([(x0, y0), (xm, ym)], fill=color, width=width)
            
            seg -= step
            x0, y0 = xm, ym
            remain -= step
            
            if remain <= 1e-6:
                idx = (idx + 1) % 2
                remain = pattern[idx]
                on_seg = not on_seg
        
        x0, y0 = x1, y1

def draw_arrow(draw, p0, pc, p2, size=ARROW_SIZE, color=COLOR_PLANE, t=0.6):
    """Draw an arrowhead on a Bezier curve at position t"""
    # Sample points before and after t to get direction
    p_at = quad_point(p0, pc, p2, t)
    p_forward = quad_point(p0, pc, p2, min(1.0, t + 0.01))
    p_backward = quad_point(p0, pc, p2, max(0.0, t - 0.01))
    
    # Calculate angle from backward to forward point
    angle = math.atan2(p_forward[1] - p_backward[1], p_forward[0] - p_backward[0])
    
    x, y = p_at
    s = size
    
    # Triangle vertices in local coordinates (pointing right)
    triangle = [(-0.9*s, -0.6*s), (0, 0), (-0.9*s, 0.6*s)]
    
    # Rotate and translate
    ca, sa = math.cos(angle), math.sin(angle)
    rotated = []
    for px, py in triangle:
        rx = px * ca - py * sa + x
        ry = px * sa + py * ca + y
        rotated.append((rx, ry))
    
    draw.polygon(rotated, fill=color)
# =========================
# ICON HELPERS
# =========================
# Module-level cache to avoid reloading icons from disk
_ICON_CACHE = {}


def get_icons(style_pack):
    """Load icons for the selected style pack (with caching)."""
    icon_paths = style_pack.get("icons", {})
    cache_key = tuple(sorted((name, path or "") for name, path in icon_paths.items()))
    if cache_key in _ICON_CACHE:
        return _ICON_CACHE[cache_key]

    icons = {}
    for name, path in icon_paths.items():
        if path and os.path.exists(path):
            icons[name] = Image.open(path).convert("RGBA")

    _ICON_CACHE[cache_key] = icons
    return icons

def paste_icon_on_curve(overlay, icon, p0, pc, p2, t=0.5, size_px=32):
    """
    Pastes an icon on the Bezier curve at t (0..1), rotated tangentially.
    Improved rotation logic from app.py-v16
    """
    # Clamp t to safe range
    t = max(0.02, min(0.98, float(t)))
    
    # Calculate point at t
    mt = 1 - t
    x = mt**2 * p0[0] + 2 * mt * t * pc[0] + t**2 * p2[0]
    y = mt**2 * p0[1] + 2 * mt * t * pc[1] + t**2 * p2[1]
    
    # Calculate tangent vector for rotation
    # Use points slightly ahead and behind for better accuracy
    t_forward = min(0.999, t + 0.01)
    t_back = max(0.001, t - 0.01)
    
    pf_x = (1-t_forward)**2 * p0[0] + 2*(1-t_forward)*t_forward * pc[0] + t_forward**2 * p2[0]
    pf_y = (1-t_forward)**2 * p0[1] + 2*(1-t_forward)*t_forward * pc[1] + t_forward**2 * p2[1]
    
    pb_x = (1-t_back)**2 * p0[0] + 2*(1-t_back)*t_back * pc[0] + t_back**2 * p2[0]
    pb_y = (1-t_back)**2 * p0[1] + 2*(1-t_back)*t_back * pc[1] + t_back**2 * p2[1]
    
    # Tangent vector
    tx = pf_x - pb_x
    ty = pf_y - pb_y
    
    # Calculate rotation angle
    angle_rad = math.atan2(ty, tx)
    angle_deg = math.degrees(angle_rad)
    
    # Resize icon
    size_px = int(max(8, size_px))
    icon_resized = icon.resize((size_px, size_px), Image.Resampling.LANCZOS)
    
    # Rotate icon
    # PIL rotation is counter-clockwise, and screen Y increases downward
    # Negate angle to account for screen coordinates
    icon_rotated = icon_resized.rotate(-angle_deg, expand=True, resample=Image.BICUBIC)
    
    # Paste centered on the curve point
    w, h = icon_rotated.size
    px = int(x - w / 2)
    py = int(y - h / 2)
    
    overlay.paste(icon_rotated, (px, py), icon_rotated)

def paste_icon_beside_curve(overlay, icon, p0, pc, p2, t=0.5, size_px=32, offset_px=25, preserve_aspect=False):
    """
    Pastes an icon BESIDE the Bezier curve at t, without rotation.
    Icon is offset perpendicular to the curve direction (to the left of travel direction).
    This avoids overlapping with city labels that are typically near the curve.
    """
    # Clamp t to safe range
    t = max(0.02, min(0.98, float(t)))
    
    # Calculate point at t
    mt = 1 - t
    x = mt**2 * p0[0] + 2 * mt * t * pc[0] + t**2 * p2[0]
    y = mt**2 * p0[1] + 2 * mt * t * pc[1] + t**2 * p2[1]
    
    # Calculate tangent vector
    t_forward = min(0.999, t + 0.01)
    t_back = max(0.001, t - 0.01)
    
    pf_x = (1-t_forward)**2 * p0[0] + 2*(1-t_forward)*t_forward * pc[0] + t_forward**2 * p2[0]
    pf_y = (1-t_forward)**2 * p0[1] + 2*(1-t_forward)*t_forward * pc[1] + t_forward**2 * p2[1]
    
    pb_x = (1-t_back)**2 * p0[0] + 2*(1-t_back)*t_back * pc[0] + t_back**2 * p2[0]
    pb_y = (1-t_back)**2 * p0[1] + 2*(1-t_back)*t_back * pc[1] + t_back**2 * p2[1]
    
    # Tangent vector
    tx = pf_x - pb_x
    ty = pf_y - pb_y
    
    # Normalize tangent
    length = math.sqrt(tx**2 + ty**2)
    if length > 0:
        tx /= length
        ty /= length
    
    # Perpendicular vector (rotate 90 degrees CCW) - points to "left" of travel
    # For screen coords (Y down), this puts icon to the left of the curve
    perp_x = -ty
    perp_y = tx
    
    # Offset position beside the curve
    offset_x = x + perp_x * offset_px
    offset_y = y + perp_y * offset_px
    
    # Resize icon (no rotation)
    size_px = int(max(8, size_px))
    if preserve_aspect and icon.width:
        width_px = size_px
        height_px = max(1, int(round(width_px * icon.height / icon.width)))
        icon_resized = icon.resize((width_px, height_px), Image.Resampling.LANCZOS)
    else:
        icon_resized = icon.resize((size_px, size_px), Image.Resampling.LANCZOS)
    
    # Paste centered on offset position
    w, h = icon_resized.size
    px = int(offset_x - w / 2)
    py = int(offset_y - h / 2)
    
    overlay.paste(icon_resized, (px, py), icon_resized)

def paste_icon_centered(overlay, icon, center_x, center_y, size_px=32, preserve_aspect=False):
    size_px = int(max(8, size_px))
    if preserve_aspect and icon.width:
        width_px = size_px
        height_px = max(1, int(round(width_px * icon.height / icon.width)))
        icon_resized = icon.resize((width_px, height_px), Image.Resampling.LANCZOS)
    else:
        icon_resized = icon.resize((size_px, size_px), Image.Resampling.LANCZOS)

    w, h = icon_resized.size
    px = int(center_x - w / 2)
    py = int(center_y - h / 2)
    overlay.paste(icon_resized, (px, py), icon_resized)

# =========================
# MAIN BUILD FUNCTION
# =========================
def get_city_positions(city_names, base_map_name="Vietnam", style="style1", base_map_style=None):
    """
    Get pixel coordinates (x, y) for cities on the DISPLAYED map.
    Returns dict: {city_name: (x, y)} in BASE image coordinates (NOT scaled by SS).
    
    Note: The rendered map uses SS=2, but when displayed in browser via 
    streamlit_image_coordinates, it shows at base size. So we return base coords.
    """
    from PIL import Image
    
    # Get map dimensions (base image, before SS scaling)
    style_pack = resolve_style_pack(style, base_map_name, base_map_style=base_map_style)
    base_path = style_pack.get("base_map_path")
    anchor_key = resolve_anchor_preset_name(base_map_name, style_pack=style_pack, base_map_path=base_path)
    anchors_cfg = ANCHORS_PRESETS.get(anchor_key, ANCHORS_PRESETS.get(base_map_name, ANCHORS_PRESETS.get("Vietnam", {})))
    if not os.path.exists(base_path):
        W, H = 1000, 2000
    else:
        base_img = Image.open(base_path)
        W, H = base_img.size
    
    # Build affine matrix (same logic as build_map)
    latlons = []
    xys = []
    for name, (ax, ay) in anchors_cfg.items():
        c = DB.find_city(name)
        if c:
            latlons.append((c.lon, c.lat))
            xys.append((ax*W, ay*H))
    
    if len(latlons) >= 3:
        M = solve_affine(latlons, xys)
    else:
        M = None

    position_overrides = CITY_POSITION_OVERRIDES.get((anchor_key, style_pack.get("base_map_style")), {})
    
    # Compute positions in BASE image coordinates
    positions = {}
    for city_name in city_names:
        c = DB.find_city(city_name)
        if c:
            canonical_name = canonical_city_name(city_name) or city_name
            if canonical_name in position_overrides:
                ox, oy = position_overrides[canonical_name]
                x, y = ox * W, oy * H
            elif M is not None:
                x, y = apply_affine(M, c.lon, c.lat)
            else:
                x, y = 0.5 * W, 0.5 * H
            positions[city_name] = (int(x), int(y))
    
    return positions


def build_map(route, base_map_name="Vietnam", output_path="map_output.png",
              arrival_city=None, departure_city=None, language="EN",
              manual_icons=None, label_overrides=None, custom_anchors=None,
              style="style1", arrival_offset=None, departure_offset=None,
              visibility_mode="all", hidden_cities=None, variant=None,
              variation_seed=None, label_variation_seed=None, base_map_style=None):
    """
    route: list of dicts {a: "CityA", b: "CityB", mode: "car"/"plane", bulge: 0.25, icon_pct: 70}
    arrival_city: Optional city name for arrival marker
    departure_city: Optional city name for departure marker
    language: "FR", "EN", or "VN" for labels
    manual_icons: list of {city, type, angle, distance}
    label_overrides: dict {city_name: {text, angle, distance}}
    custom_anchors: dict {city_name: (x, y)} to override ANCHORS_PRESETS
    style: "style1" or "style2" - determines colors, icons, routes, and icon scale
    base_map_style: Optional "style1" or "style2" override for the background image
    visibility_mode: "all", "major", or "custom"
    hidden_cities: explicit hidden city names used when visibility_mode="custom"
    variation_seed: Optional int seed for visual variation (shuffles curves, angles)
    label_variation_seed: Optional int seed for label-only layout variation
    """
    import random as _random
    _rng = _random.Random(variation_seed) if variation_seed is not None else None
    style_pack = resolve_style_pack(style, base_map_name, variant=variant, base_map_style=base_map_style)
    colors = style_pack["colors"]
    icon_scale = style_pack.get("icon_scale", 1.0)
    line_width_scale = style_pack.get("line_width_scale", 1.0)
    dash_patterns = style_pack.get("dash_patterns", {})
    mode_icon_scale = style_pack.get("mode_icon_scale", {})
    mode_offset_scale = style_pack.get("mode_offset_scale", {})
    
    # Extract colors from style
    color_plane = colors.get("plane", COLOR_PLANE)
    color_car = colors.get("car", COLOR_CAR)
    color_boat = colors.get("boat", COLOR_BOAT)
    color_train = colors.get("train", COLOR_TRAIN)
    marker_color_vn = colors.get("marker_vn", MARKER_COLOR_VN)
    marker_color_foreign = colors.get("marker_foreign", MARKER_COLOR_FOREIGN)
    color_arrival_departure = colors.get("arrival_departure", color_plane)

    def scaled_icon_px(base_size, mode_name):
        return int(base_size * icon_scale * mode_icon_scale.get(mode_name, 1.0))

    def scaled_offset_px(base_offset, mode_name):
        return int(base_offset * icon_scale * mode_offset_scale.get(mode_name, 1.0))

    def scaled_line_width(base_width, mode_name):
        return max(1, int(base_width * line_width_scale))

    def dash_for(kind_name):
        dash_on, dash_off = dash_patterns.get(kind_name, (DASH_ON, DASH_OFF))
        return max(1, int(dash_on * SS)), max(1, int(dash_off * SS))
    
    # Default parameters
    if manual_icons is None:
        manual_icons = []
    if label_overrides is None:
        label_overrides = {}
    if hidden_cities is None:
        hidden_cities = []

    route_endpoint_cities = {
        canonical_city_name(route[0].get("a")) if route else None,
        canonical_city_name(route[-1].get("b")) if route else None,
        canonical_city_name(arrival_city),
        canonical_city_name(departure_city),
    }
    route_endpoint_cities.discard(None)

    # Resolve anchor preset against the actual base map file selected for this style.
    anchor_key = resolve_anchor_preset_name(base_map_name, style_pack=style_pack, base_map_path=style_pack.get("base_map_path"))
    anchors_cfg = ANCHORS_PRESETS.get(anchor_key, ANCHORS_PRESETS.get(base_map_name, ANCHORS_PRESETS.get("Vietnam", {})))
    
    # Apply custom anchors if provided
    if custom_anchors:
        anchors_cfg = dict(anchors_cfg)  # Make a copy
        anchors_cfg.update(custom_anchors)
    base_path = style_pack.get("base_map_path")
    if not base_path or not os.path.exists(base_path):
        base_img = Image.new("RGB", (1000, 2000), (240, 240, 220))
    else:
        base_img = Image.open(base_path).convert("RGBA")

    W, H = base_img.size
    
    # Load Icons
    icons = get_icons(style_pack)

    def is_style2_speedboat_leg(leg):
        if style_pack.get("key") != "style2" or leg.get("mode", "car") != "boat":
            return False
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if not a_name or not b_name:
            return False
        return frozenset((a_name, b_name)) in STYLE2_SPEEDBOAT_ROUTE_PAIRS

    def is_rach_gia_phu_quoc_speedboat_leg(leg):
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        return bool(a_name and b_name and frozenset((a_name, b_name)) == RACH_GIA_PHU_QUOC_PAIR)

    def prefers_screen_left_car_icon(leg):
        if leg.get("mode", "car") != "car":
            return False
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if not a_name or not b_name:
            return False
        return {a_name, b_name}.issubset(CENTRAL_VIETNAM_CAR_ICON_LEFT_CITIES)

    def adjusted_car_offset_px(leg, p0, pc, p2, t, offset_px):
        if not prefers_screen_left_car_icon(leg):
            return offset_px

        t = max(0.02, min(0.98, float(t)))
        t_forward = min(0.999, t + 0.01)
        t_back = max(0.001, t - 0.01)

        pf_x = (1 - t_forward) ** 2 * p0[0] + 2 * (1 - t_forward) * t_forward * pc[0] + t_forward ** 2 * p2[0]
        pf_y = (1 - t_forward) ** 2 * p0[1] + 2 * (1 - t_forward) * t_forward * pc[1] + t_forward ** 2 * p2[1]
        pb_x = (1 - t_back) ** 2 * p0[0] + 2 * (1 - t_back) * t_back * pc[0] + t_back ** 2 * p2[0]
        pb_y = (1 - t_back) ** 2 * p0[1] + 2 * (1 - t_back) * t_back * pc[1] + t_back ** 2 * p2[1]

        tx = pf_x - pb_x
        ty = pf_y - pb_y
        length = math.sqrt(tx ** 2 + ty ** 2)
        if length <= 0:
            return -offset_px
        tx /= length
        ty /= length
        perp_x = -ty

        mt = 1 - t
        curve_x = mt ** 2 * p0[0] + 2 * mt * t * pc[0] + t ** 2 * p2[0]
        positive_x = curve_x + perp_x * offset_px
        negative_x = curve_x - perp_x * offset_px
        return offset_px if positive_x <= negative_x else -offset_px

    def adjusted_speedboat_offset_px(leg, p0, pc, p2, t, offset_px):
        if not is_rach_gia_phu_quoc_speedboat_leg(leg):
            return offset_px

        t = max(0.02, min(0.98, float(t)))
        t_forward = min(0.999, t + 0.01)
        t_back = max(0.001, t - 0.01)

        pf_x = (1 - t_forward) ** 2 * p0[0] + 2 * (1 - t_forward) * t_forward * pc[0] + t_forward ** 2 * p2[0]
        pf_y = (1 - t_forward) ** 2 * p0[1] + 2 * (1 - t_forward) * t_forward * pc[1] + t_forward ** 2 * p2[1]
        pb_x = (1 - t_back) ** 2 * p0[0] + 2 * (1 - t_back) * t_back * pc[0] + t_back ** 2 * p2[0]
        pb_y = (1 - t_back) ** 2 * p0[1] + 2 * (1 - t_back) * t_back * pc[1] + t_back ** 2 * p2[1]

        tx = pf_x - pb_x
        ty = pf_y - pb_y
        length = math.sqrt(tx ** 2 + ty ** 2)
        if length <= 0:
            return offset_px
        tx /= length
        ty /= length
        perp_y = tx

        mt = 1 - t
        curve_y = mt ** 2 * p0[1] + 2 * mt * t * pc[1] + t ** 2 * p2[1]
        positive_y = curve_y + perp_y * offset_px
        negative_y = curve_y - perp_y * offset_px
        return offset_px if positive_y >= negative_y else -offset_px

    # Calculate Affine Matrix
    latlons = []
    xys = []
    for name, (ax, ay) in anchors_cfg.items():
        c = DB.find_city(name)
        if c:
            latlons.append((c.lon, c.lat))
            xys.append((ax*W, ay*H))
            
    if len(latlons) >= 3:
        M = solve_affine(latlons, xys)
    else:
        M = None
        
    def get_xy(name):
        c = DB.find_city(name)
        if not c: return None
        canonical_name = canonical_city_name(name) or name
        position_overrides = CITY_POSITION_OVERRIDES.get((anchor_key, style_pack.get("base_map_style")), {})
        if canonical_name in position_overrides:
            ox, oy = position_overrides[canonical_name]
            return (ox * W, oy * H)
        if M is not None:
            return apply_affine(M, c.lon, c.lat)
        else:
            return (0.5 * W, 0.5 * H)

    # Drawing Surface (Supersampled)
    SS = SUPERSAMPLE_DEFAULT
    overlay = Image.new("RGBA", (W*SS, H*SS), (0,0,0,0))
    draw = ImageDraw.Draw(overlay)

    def fixed_car_icon_center(leg, icon_size_px):
        if leg.get("mode", "car") != "car":
            return None
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if not a_name or not b_name:
            return None
        if frozenset((a_name, b_name)) == NINH_BINH_HA_LONG_CAR_ICON_PAIR:
            ninh_binh_xy = get_xy("Ninh Binh")
            if not ninh_binh_xy:
                return None
            ninh_x = ninh_binh_xy[0] * SS
            ninh_y = ninh_binh_xy[1] * SS
            return (
                ninh_x + icon_size_px * 0.18,
                ninh_y + icon_size_px * 0.65,
            )
        return None

    def vietnam_train_bulge_candidates(leg, base_bulge):
        if leg.get("mode", "car") != "train":
            return None
        a_name = canonical_city_name(leg.get("a"))
        b_name = canonical_city_name(leg.get("b"))
        if not a_name or not b_name:
            return None

        pair = frozenset((a_name, b_name))
        if pair in INLAND_TRAIN_ROUTE_PAIRS:
            # Hanoi-Central train should sit just inside Vietnam's coast:
            # enough inland bow to avoid the sea, but not far toward Laos.
            magnitude = max(abs(base_bulge), 0.28)
            sign = 1 if a_name == "Ha Noi" else -1
            fixed_bulge = sign * magnitude
            return [fixed_bulge, fixed_bulge * 0.82, fixed_bulge * 1.08, fixed_bulge * 0.65]

        if pair in VIETNAM_COASTAL_TRAIN_ROUTE_PAIRS:
            # Central-South train should stay on Vietnam's side of the route,
            # near the East Sea, not bow west into Cambodia.
            magnitude = max(abs(base_bulge), 0.56)
            sign = -1 if a_name in {"Da Nang", "Hue"} else 1
            fixed_bulge = sign * magnitude
            return [fixed_bulge, fixed_bulge * 0.82, fixed_bulge * 1.08, fixed_bulge * 0.65]

        return None
    
    # Font
    try:
        font_path = os.path.join(ASSETS_DIR, "GillSans.ttc")
        font = ImageFont.truetype(font_path, 19 * SS, index=0)
        font_semibold = ImageFont.truetype(font_path, 19 * SS, index=4)
    except:
        font = ImageFont.load_default()
        font_semibold = font

    def font_for_city_label(city_name):
        return font_semibold if city_name == "Ha Noi" else font

    def rects_overlap(box1, box2):
        return not (
            box1["right"] < box2["left"] or
            box1["left"] > box2["right"] or
            box1["bottom"] < box2["top"] or
            box1["top"] > box2["bottom"]
        )

    def center_box(center_x, center_y, width_px, height_px=None, padding_px=None):
        height_px = width_px if height_px is None else height_px
        padding_px = 15 * SS if padding_px is None else padding_px
        return {
            "left": center_x - (width_px / 2) - padding_px,
            "top": center_y - (height_px / 2) - padding_px,
            "right": center_x + (width_px / 2) + padding_px,
            "bottom": center_y + (height_px / 2) + padding_px,
        }

    def box_outside_render_canvas(box):
        return (
            box["left"] < 0 or
            box["top"] < 0 or
            box["right"] > (W * SS) or
            box["bottom"] > (H * SS)
        )

    def box_overlap_area_raw(box1, box2):
        left = max(box1["left"], box2["left"])
        right = min(box1["right"], box2["right"])
        top = max(box1["top"], box2["top"])
        bottom = min(box1["bottom"], box2["bottom"])
        return max(0, right - left) * max(0, bottom - top)

    def curve_pose(p0, pc, p2, t):
        t = max(0.02, min(0.98, float(t)))
        x, y = quad_point(p0, pc, p2, t)
        t_forward = min(0.999, t + 0.01)
        t_back = max(0.001, t - 0.01)
        pf_x, pf_y = quad_point(p0, pc, p2, t_forward)
        pb_x, pb_y = quad_point(p0, pc, p2, t_back)
        tx = pf_x - pb_x
        ty = pf_y - pb_y
        length = math.sqrt(tx ** 2 + ty ** 2)
        if length <= 0:
            return x, y, 1.0, 0.0, 0.0, 1.0
        tx /= length
        ty /= length
        return x, y, tx, ty, -ty, tx

    def icon_center_on_curve(p0, pc, p2, t, offset_px):
        curve_x, curve_y, _, _, perp_x, perp_y = curve_pose(p0, pc, p2, t)
        return curve_x + perp_x * offset_px, curve_y + perp_y * offset_px

    def icon_size_for_leg(mode, use_speedboat_icon):
        if use_speedboat_icon:
            return 50 * SS
        return scaled_icon_px(48 * SS if mode == "plane" else 40 * SS, mode)

    def rough_text_size(text, font_obj):
        try:
            bbox = draw.textbbox((0, 0), text, font=font_obj, stroke_width=0)
            return max(1, bbox[2] - bbox[0]), max(1, bbox[3] - bbox[1])
        except Exception:
            return max(1, len(text) * 10 * SS), max(1, 19 * SS)

    def rough_label_box(city_x, city_y, text, angle, distance, font_obj):
        width, height = rough_text_size(text, font_obj)
        rad = math.radians(angle)
        dx = math.cos(rad)
        dy = math.sin(rad)
        gap = max(2 * SS, 2)
        anchor_x = city_x + dx * (distance + gap)
        anchor_y = city_y + dy * (distance + gap)
        if dx > 0.35:
            left = anchor_x
        elif dx < -0.35:
            left = anchor_x - width
        else:
            left = anchor_x - (width / 2)
        if dy > 0.45:
            top = anchor_y
        elif dy < -0.45:
            top = anchor_y - height
        else:
            top = anchor_y - (height / 2)
        padding = 4 * SS
        return {
            "left": left - padding,
            "top": top - padding,
            "right": left + width + padding,
            "bottom": top + height + padding,
        }

    def grid_box_overlap_count(box, occupied_cells, cell_size=25):
        left = int(box["left"] / cell_size)
        right = int(box["right"] / cell_size)
        top = int(box["top"] / cell_size)
        bottom = int(box["bottom"] / cell_size)
        overlap = 0
        for gx in range(left, right + 1):
            for gy in range(top, bottom + 1):
                if (gx, gy) in occupied_cells:
                    overlap += 1
        return overlap

    def route_icon_t_candidates(seed_t, mode, use_speedboat_icon, explicit_icon_pct):
        seed_t = max(0.08, min(0.92, float(seed_t)))
        if explicit_icon_pct:
            return [seed_t]
        if mode == "plane":
            raw = [seed_t, 0.50, 0.38, 0.62, 0.28, 0.72]
        elif use_speedboat_icon:
            raw = [seed_t, 0.50, 0.42, 0.58]
        elif mode == "boat":
            raw = [seed_t, 0.86, 0.74, 0.62, 0.50]
        else:
            raw = [seed_t, 0.50, 0.38, 0.62, 0.28, 0.72]
        candidates = []
        for value in raw:
            clamped = round(max(0.08, min(0.92, float(value))), 3)
            if clamped not in candidates:
                candidates.append(clamped)
        return candidates

    def route_icon_offset_candidates(leg, mode, use_speedboat_icon, p0, pc, p2, t, base_offset):
        if mode == "plane":
            return [0]
        preferred = base_offset
        hard_side = False
        if mode == "car":
            preferred = adjusted_car_offset_px(leg, p0, pc, p2, t, base_offset)
            hard_side = prefers_screen_left_car_icon(leg)
        elif use_speedboat_icon:
            preferred = adjusted_speedboat_offset_px(leg, p0, pc, p2, t, base_offset)
            hard_side = is_rach_gia_phu_quoc_speedboat_leg(leg)

        multipliers = [1.0, 0.68]
        offsets = []
        for multiplier in multipliers:
            offsets.append(preferred * multiplier)
        if not hard_side:
            for multiplier in multipliers:
                offsets.append(-preferred * multiplier)
        deduped = []
        for offset in offsets:
            rounded = round(offset, 3)
            if rounded not in deduped:
                deduped.append(rounded)
        return deduped

    def choose_route_icon_layout(leg, mode, use_speedboat_icon, p0, pc, p2, seed_t, icon_size, previous_route_cells, city_boxes, expected_label_boxes):
        fixed_center = fixed_car_icon_center(leg, icon_size) if mode == "car" else None
        if fixed_center:
            bbox = center_box(fixed_center[0], fixed_center[1], icon_size)
            return {"t": seed_t, "center": fixed_center, "bbox": bbox, "offset": 0, "fixed": True}

        base_offset = scaled_offset_px(20 * SS, "boat" if use_speedboat_icon else mode)
        explicit_icon_pct = "icon_pct" in leg
        best_layout = None
        best_score = float("inf")

        for t in route_icon_t_candidates(seed_t, mode, use_speedboat_icon, explicit_icon_pct):
            offsets = route_icon_offset_candidates(leg, mode, use_speedboat_icon, p0, pc, p2, t, base_offset)
            for offset in offsets:
                if mode == "plane":
                    center_x, center_y = quad_point(p0, pc, p2, t)
                else:
                    center_x, center_y = icon_center_on_curve(p0, pc, p2, t, offset)
                bbox = center_box(center_x, center_y, icon_size)

                score = abs(t - seed_t) * 8.0
                if explicit_icon_pct:
                    score -= 1.5
                if abs(offset) < abs(base_offset) and mode != "plane":
                    score += 0.35
                if box_outside_render_canvas(bbox):
                    score += 120

                for existing in icon_positions:
                    if rects_overlap(bbox, existing["bbox"]):
                        score += 60 + min(box_overlap_area_raw(bbox, existing["bbox"]) / max(icon_size * icon_size, 1), 5) * 12
                for marker_box in city_boxes:
                    if rects_overlap(bbox, marker_box):
                        score += 42 + min(box_overlap_area_raw(bbox, marker_box) / max(icon_size * icon_size, 1), 5) * 10
                for label_box in expected_label_boxes:
                    if rects_overlap(bbox, label_box):
                        score += 12 + min(box_overlap_area_raw(bbox, label_box) / max(icon_size * icon_size, 1), 4) * 4

                route_overlap = grid_box_overlap_count(bbox, previous_route_cells, cell_size=25)
                if route_overlap:
                    score += min(route_overlap, 12) * 2.5

                for endpoint_name in (leg.get("a"), leg.get("b")):
                    endpoint_xy = get_xy(endpoint_name)
                    if endpoint_xy:
                        endpoint_x, endpoint_y = endpoint_xy[0] * SS, endpoint_xy[1] * SS
                        distance = math.hypot(center_x - endpoint_x, center_y - endpoint_y)
                        if distance < (icon_size * 0.62):
                            score += ((icon_size * 0.62) - distance) / max(SS, 1)

                if mode == "plane":
                    score -= 0.5
                elif use_speedboat_icon and is_rach_gia_phu_quoc_speedboat_leg(leg):
                    _, curve_y, _, _, _, _ = curve_pose(p0, pc, p2, t)
                    if center_y < curve_y:
                        score += 200
                elif mode == "car" and prefers_screen_left_car_icon(leg):
                    preferred = adjusted_car_offset_px(leg, p0, pc, p2, t, base_offset)
                    if (offset > 0) != (preferred > 0):
                        score += 100

                if score < best_score:
                    best_score = score
                    best_layout = {"t": t, "center": (center_x, center_y), "bbox": bbox, "offset": offset, "fixed": False}

        return best_layout

    # =============================================
    # MERGE CONSECUTIVE SEGMENTS FOR ICON PLACEMENT
    # =============================================
    # User insight: "Đi ô tô thì các chặng liền mạch nhau thì chỉ cần dùng 1 ô tô"
    # Consecutive same-mode segments should show only ONE icon for the entire chain
    
    def merge_consecutive_segments(route_legs):
        """Merge consecutive same-mode segments into chains for icon placement.
        Returns list of chains, each with: mode, start_city, end_city, middle_leg_index
        """
        if not route_legs:
            return []
        
        chains = []
        current_chain = None
        
        for i, leg in enumerate(route_legs):
            mode = "speedboat" if is_style2_speedboat_leg(leg) else leg.get("mode", "car")
            
            # Check if this leg continues the current chain
            # Never merge plane or special speedboat legs - each gets its own icon.
            if current_chain and current_chain["mode"] == mode and mode not in {"plane", "speedboat"} and current_chain["end"] == leg["a"]:
                # Extend current chain
                current_chain["end"] = leg["b"]
                current_chain["leg_indices"].append(i)
            else:
                # Save previous chain and start new one
                if current_chain:
                    chains.append(current_chain)
                current_chain = {
                    "mode": mode,
                    "start": leg["a"],
                    "end": leg["b"],
                    "leg_indices": [i]
                }
        
        # Don't forget the last chain
        if current_chain:
            chains.append(current_chain)
        
        return chains
    
    # Get merged chains for icon placement
    icon_chains = merge_consecutive_segments(route)
    
    # Pre-calculate which leg index gets the icon (middle of each chain)
    legs_with_icons = set()
    chain_icon_info = {}  # leg_index -> icon_t position
    
    for chain in icon_chains:
        indices = chain["leg_indices"]
        chain_mode = chain.get("mode", "car")
        
        # If ANY leg in this chain has icon_pct = -1, user wants to hide the icon
        if any(route[idx].get("icon_pct", 50) < 0 for idx in indices):
            continue
        
        if len(indices) == 1:
            # Single leg: icon at normal position
            legs_with_icons.add(indices[0])
            chain_icon_info[indices[0]] = None  # Use leg's default icon_pct
        else:
            # Multiple legs: icon at middle leg. Boat icons should stay closer
            # to the destination side of the representative leg.
            middle_idx = indices[len(indices) // 2]
            legs_with_icons.add(middle_idx)
            chain_icon_info[middle_idx] = 0.86 if chain_mode in {"boat", "speedboat"} else 0.5

    # =============================================
    # AUTO-CULL ICONS THAT ARE TOO CLOSE TOGETHER
    # =============================================
    # After chain merging, icons on short car segments can still cluster.
    # Remove icons whose approximate positions are within a minimum distance.
    # Users can re-enable via Chỉnh icon → Reset (removes the auto-hide).
    _MIN_ICON_DIST = 0.15 * min(W, H)  # 15% of smaller map dimension
    _kept_icon_positions = []  # list of (x, y) for kept icons
    _auto_hidden = set()

    for leg_idx in sorted(legs_with_icons):
        leg = route[leg_idx]
        pt_a = get_xy(leg["a"])
        pt_b = get_xy(leg["b"])
        if not pt_a or not pt_b:
            continue
        # Approximate icon position = midpoint of the leg
        mid_x = (pt_a[0] + pt_b[0]) / 2
        mid_y = (pt_a[1] + pt_b[1]) / 2
        too_close = False
        for kx, ky in _kept_icon_positions:
            if math.hypot(mid_x - kx, mid_y - ky) < _MIN_ICON_DIST:
                too_close = True
                break
        if too_close and "icon_pct" not in leg and leg.get("mode") != "plane" and not is_style2_speedboat_leg(leg):
            _auto_hidden.add(leg_idx)
        else:
            _kept_icon_positions.append((mid_x, mid_y))

    legs_with_icons -= _auto_hidden

    visible_cities = compute_visible_cities(
        route,
        visibility_mode=visibility_mode,
        hidden_cities=hidden_cities,
        arrival_city=arrival_city,
        departure_city=departure_city,
        manual_icons=manual_icons,
        label_overrides=label_overrides,
    )
    if (visibility_mode or "all").lower() == "major":
        visible_cities = compact_visible_cities(
            route,
            visible_cities,
            get_xy,
            base_map_name=base_map_name,
            arrival_city=arrival_city,
            departure_city=departure_city,
            manual_icons=manual_icons,
            label_overrides=label_overrides,
        )
    visible_cities = set(visible_cities) | default_landmark_cities(base_map_name, hidden_cities=hidden_cities)

    # =============================================
    # MERGE LEGS AROUND HIDDEN CITIES
    # =============================================
    # Only merge legs for explicitly user-hidden cities (custom hidden / Ẩn nhãn).
    # Major Stops mode hides labels/markers but keeps original route legs intact.
    hidden_set = set()
    for h in (hidden_cities or []):
        c = canonical_city_name(h)
        if c:
            hidden_set.add(c)
    
    if hidden_set:
        merged_route = []
        for leg in route:
            # If previous leg's destination is hidden, merge with this leg
            if merged_route and canonical_city_name(merged_route[-1]["b"]) in hidden_set:
                merged_route[-1] = {**merged_route[-1], "b": leg["b"]}
            else:
                merged_route.append(dict(leg))
        route = merged_route

    city_marker_boxes = []
    expected_label_boxes = []
    for city_name in sorted(city for city in visible_cities if city):
        pt = get_xy(city_name)
        city_obj = DB.find_city(city_name)
        if not pt:
            continue
        city_x, city_y = pt[0] * SS, pt[1] * SS
        marker_r = (6 if city_obj and city_obj.country == "VN" else 4) * SS
        marker_box = center_box(city_x, city_y, marker_r * 2, padding_px=8 * SS)
        marker_box["name"] = city_name
        city_marker_boxes.append(marker_box)

        override = label_overrides.get(city_name, {})
        display_text = override.get("text", city_name)
        label_font = font_for_city_label(city_name)
        if override and ("offset_x" in override or "offset_y" in override):
            width, height = rough_text_size(display_text, label_font)
            left = city_x + (override.get("offset_x", 0) * SS)
            top = city_y + (override.get("offset_y", 0) * SS) - (height / 2)
            expected_label_boxes.append({
                "left": left - 4 * SS,
                "top": top - 4 * SS,
                "right": left + width + 4 * SS,
                "bottom": top + height + 4 * SS,
            })
            continue

        if override and ("angle" in override or "distance" in override):
            angle = override.get("angle", 0)
            distance = 8 * SS * override.get("distance", 1.0)
        elif city_obj and city_obj.label_ang is not None:
            angle = city_obj.label_ang
            distance = 8 * SS * (city_obj.label_dist if city_obj.label_dist else 1.0)
        else:
            angle = 0
            distance = 8 * SS
        expected_label_boxes.append(rough_label_box(city_x, city_y, display_text, angle, distance, label_font))

    # Draw Legs
    all_route_cities = set()
    drawn_route_cells = set()  # Track already drawn routes for collision avoidance
    icon_positions = []  # Track icon positions for label collision
    
    for leg_idx, leg in enumerate(route):
        a_name, b_name = leg["a"], leg["b"]
        pt_a = get_xy(a_name)
        pt_b = get_xy(b_name)
        
        if not pt_a or not pt_b:
            continue
            
        x0, y0 = pt_a[0]*SS, pt_a[1]*SS
        x2, y2 = pt_b[0]*SS, pt_b[1]*SS
        
        all_route_cities.add(canonical_city_name(a_name))
        all_route_cities.add(canonical_city_name(b_name))
        
        mode = leg.get("mode", "car")
        use_speedboat_icon = is_style2_speedboat_leg(leg)
        
        # SMART ROUTE COLLISION AVOIDANCE
        # Try different bulge values and pick the one with least overlap with existing routes
        base_bulge = leg.get("bulge", CURVE_BULGE)
        
        # Candidate bulge values to try
        fixed_train_candidates = vietnam_train_bulge_candidates(leg, base_bulge) if mode == "train" else None
        if fixed_train_candidates:
            bulge_candidates = fixed_train_candidates
        elif mode == "plane":
            bulge_candidates = [base_bulge, -base_bulge, base_bulge * 1.5, -base_bulge * 1.5, 
                               base_bulge * 0.5, -base_bulge * 0.5, base_bulge * 2, -base_bulge * 2]
        else:
            bulge_candidates = [base_bulge, -base_bulge * 0.5, base_bulge * 0.5, -base_bulge]
        
        best_bulge = base_bulge
        best_overlap = float('inf')
        
        for candidate_bulge in bulge_candidates:
            pc_test = control_point((x0, y0), (x2, y2), candidate_bulge)
            pts_test = sample_curve((x0, y0), pc_test, (x2, y2), n=30)
            
            # Count overlap with already drawn routes
            overlap_count = 0
            for px, py in pts_test:
                grid_key = (int(px / 25), int(py / 25))
                if grid_key in drawn_route_cells:
                    overlap_count += 1
            
            if overlap_count < best_overlap:
                best_overlap = overlap_count
                best_bulge = candidate_bulge
                
            # Perfect - no overlap
            if overlap_count == 0:
                break
        
        bulge = best_bulge
        
        # Use chain icon position if this is the representative leg
        if leg_idx in chain_icon_info and chain_icon_info[leg_idx] is not None:
            icon_t = chain_icon_info[leg_idx]
        else:
            default_icon_pct = 50 if (mode == "plane" or use_speedboat_icon) else 94 if mode == "boat" else 50
            icon_pct = leg.get("icon_pct", default_icon_pct)
            icon_t = icon_pct / 100.0
        # Variation seed: randomize icon position on route
        if _rng is not None and "icon_pct" not in leg:
            icon_t = _rng.uniform(0.25, 0.75)
        
        # Curve with chosen bulge
        pc = control_point((x0, y0), (x2, y2), bulge)
        pts = sample_curve((x0,y0), pc, (x2,y2), n=150)
        previous_route_cells = set(drawn_route_cells)
        
        # Add this route's points to drawn set for future collision checks
        for px, py in pts[::5]:  # Sample every 5th point
            drawn_route_cells.add((int(px / 25), int(py / 25)))
        
        width = scaled_line_width(2 * SS, mode)
        
        # Check if this leg should show an icon (only representative legs of each chain)
        should_show_icon = leg_idx in legs_with_icons and leg.get("icon_pct", 50) >= 0
        selected_icon_layout = None
        if should_show_icon:
            icon_size = icon_size_for_leg(mode, use_speedboat_icon)
            selected_icon_layout = choose_route_icon_layout(
                leg,
                mode,
                use_speedboat_icon,
                (x0, y0),
                pc,
                (x2, y2),
                icon_t,
                icon_size,
                previous_route_cells,
                city_marker_boxes,
                expected_label_boxes,
            )
            if selected_icon_layout:
                icon_t = selected_icon_layout["t"]
                icon_x, icon_y = selected_icon_layout["center"]
                icon_positions.append({
                    'x': icon_x,
                    'y': icon_y,
                    'size': icon_size,
                    'bbox': selected_icon_layout["bbox"],
                })
        
        if mode == "plane":
            plane_dash_on, plane_dash_off = dash_for("plane")
            draw_dashed(draw, pts, color_plane, width, dash_on=plane_dash_on, dash_off=plane_dash_off)
            if should_show_icon and "plane" in icons:
               paste_icon_on_curve(overlay, icons["plane"], (x0,y0), pc, (x2,y2), t=icon_t, size_px=scaled_icon_px(48 * SS, "plane"))
        elif mode == "train":
            draw_line(draw, pts, color_train, width)
            if should_show_icon and "train" in icons:
                train_offset_px = selected_icon_layout["offset"] if selected_icon_layout else scaled_offset_px(20 * SS, "train")
                paste_icon_beside_curve(overlay, icons["train"], (x0,y0), pc, (x2,y2), t=icon_t, size_px=icon_size_for_leg(mode, use_speedboat_icon), offset_px=train_offset_px)
        elif mode == "boat":
            draw_line(draw, pts, color_boat, width)
            boat_icon_name = "speedboat" if use_speedboat_icon and "speedboat" in icons else "boat"
            if should_show_icon and boat_icon_name in icons:
                boat_icon_size = icon_size_for_leg(mode, use_speedboat_icon)
                boat_offset_px = selected_icon_layout["offset"] if selected_icon_layout else scaled_offset_px(20 * SS, "boat")
                paste_icon_beside_curve(
                    overlay,
                    icons[boat_icon_name],
                    (x0, y0),
                    pc,
                    (x2, y2),
                    t=icon_t,
                    size_px=boat_icon_size,
                    offset_px=boat_offset_px,
                    preserve_aspect=boat_icon_name == "speedboat",
                )
        else: # Car
            draw_line(draw, pts, color_car, width)
            if should_show_icon and "car" in icons:
                car_icon_size = icon_size_for_leg(mode, use_speedboat_icon)
                if selected_icon_layout and selected_icon_layout.get("fixed"):
                    fixed_icon_center = selected_icon_layout["center"]
                    paste_icon_centered(overlay, icons["car"], fixed_icon_center[0], fixed_icon_center[1], size_px=car_icon_size)
                else:
                    car_offset_px = selected_icon_layout["offset"] if selected_icon_layout else adjusted_car_offset_px(
                        leg,
                        (x0, y0),
                        pc,
                        (x2, y2),
                        icon_t,
                        scaled_offset_px(20 * SS, "car"),
                    )
                    paste_icon_beside_curve(overlay, icons["car"], (x0,y0), pc, (x2,y2), t=icon_t, size_px=car_icon_size, offset_px=car_offset_px)
            
    # base_map.jpg already contains some printed city labels. Avoid drawing those twice.
    preprinted_city_labels = set()
    if base_map_name == "Vietnam" and style_pack.get("has_preprinted_labels"):
        preprinted_city_labels = {
            "Dong Van", "Meo Vac", "Lao Cai", "Sapa", "Mu Cang Chai", "Nghia Lo",
            "Duong Lam", "Mai Chau", "Bac Ha", "Ba Be", "Ha Noi", "Ninh Binh",
            "Hue", "Da Nang", "Hoi An", "Buon Ma Thuot", "Sai Gon", "Rach Gia",
            "Ben Tre", "Can Tho", "Mui Ne", "Phu Quoc", "Lan Ha",
        }

    # Smart Label Positioning with Collision Detection
    # First, calculate all potential label positions
    label_data = []
    
    for city_name in sorted(city for city in visible_cities if city):
        pt = get_xy(city_name)
        if pt:
            x, y = pt[0]*SS, pt[1]*SS
            
            # PRIORITY ORDER for label position:
            # 1. UI overrides (label_overrides from session state)
            # 2. SAVED positions from map_positions.json
            # 3. Predefined in SEED_CITIES (city_obj.label_ang/label_dist)
            # 4. Dynamic collision avoidance
            
            override = label_overrides.get(city_name, {})
            
            # Positions come from:
            # 1. UI overrides (label_overrides passed from session)
            # 2. SEED_CITIES in this file (city_obj.label_ang/label_dist)
            
            city_obj = DB.find_city(city_name)
            # Keep entry/exit labels explicit even on legacy pre-labelled maps.
            suppress_text = city_name in preprinted_city_labels and not override and city_name not in route_endpoint_cities
            
            # Check for simple X/Y offset override (new system)
            if override and ('offset_x' in override or 'offset_y' in override):
                # Direct pixel offset - simple!
                offset_x = override.get('offset_x', 0) * SS
                offset_y = override.get('offset_y', 0) * SS
                display_name = override.get('text', city_name)
                
                label_data.append({
                    'name': city_name,
                    'display_name': display_name,
                    'x': x,
                    'y': y,
                    'direct_offset': (offset_x, offset_y),  # New: direct offset
                    'suppress_text': False,
                    'placed': False,
                    'label_x': None,
                    'label_y': None,
                    'bbox': None
                })
                continue
            
            # Angle/distance override (from click or other sources)
            if override and ('angle' in override or 'distance' in override):
                # Use same base_dist as SEED_CITIES for consistency
                base_dist = 8 * SS
                ang = override.get('angle', 0)
                dist_mult = override.get('distance', 1.0)
                angles = [ang]
                distances = [base_dist * dist_mult]
                use_predefined = True
                display_name = override.get('text', city_name)
            elif city_obj and city_obj.label_ang is not None:
                # Use predefined position from SEED_CITIES
                base_dist = 8 * SS
                dist = base_dist * (city_obj.label_dist if city_obj.label_dist else 1.0)
                angles = [city_obj.label_ang]
                distances = [dist]
                use_predefined = True
                display_name = city_name
            else:
                # Dynamic placement - try 8 cardinal directions
                angles = [0, -45, -90, 45, 90, -135, 180, 135]
                distances = [8 * SS, 12 * SS, 18 * SS]
                use_predefined = False
                display_name = city_name
            
            label_data.append({
                'name': city_name,
                'display_name': display_name,  # For custom text
                'x': x,
                'y': y,
                'suppress_text': suppress_text,
                'angles': angles,
                'distances': distances,
                'use_predefined': use_predefined,
                'placed': False,
                'label_x': None,
                'label_y': None,
                'bbox': None
            })
    
    def measure_label_text(text, font_obj, draw_obj):
        """Measure label size without text stroke."""
        try:
            bbox = draw_obj.textbbox((0, 0), text, font=font_obj, stroke_width=0)
            w = bbox[2] - bbox[0]
            h = bbox[3] - bbox[1]
        except Exception:
            try:
                bbox = font_obj.getbbox(text)
                w = bbox[2] - bbox[0]
                h = bbox[3] - bbox[1]
            except Exception:
                w = len(text) * 10 * SS
                h = 19 * SS
        return max(w, 1), max(h, 1)

    def resolve_label_box(city_x, city_y, angle, distance, text, font_obj, draw_obj):
        """
        Convert polar label placement into a top-left draw position and bbox.
        This keeps labels on the correct side of the city instead of always
        expanding to the right.
        """
        w, h = measure_label_text(text, font_obj, draw_obj)
        rad = math.radians(angle)
        dx = math.cos(rad)
        dy = math.sin(rad)
        gap = max(2 * SS, 2)

        anchor_x = city_x + dx * (distance + gap)
        anchor_y = city_y + dy * (distance + gap)

        if dx > 0.35:
            left = anchor_x
        elif dx < -0.35:
            left = anchor_x - w
        else:
            left = anchor_x - (w / 2)

        if dy > 0.45:
            top = anchor_y
        elif dy < -0.45:
            top = anchor_y - h
        else:
            top = anchor_y - (h / 2)

        padding = 4 * SS
        bbox = {
            'left': left - padding,
            'top': top - padding,
            'right': left + w + padding,
            'bottom': top + h + padding,
        }
        return left, top, bbox

    def resolve_direct_offset_box(city_x, city_y, offset_x, offset_y, text, font_obj, draw_obj):
        """
        Legacy direct offset mode stores X/Y relative to city center and used
        left-middle anchoring. Preserve that behavior but draw using top-left
        coordinates so bbox math stays consistent.
        """
        w, h = measure_label_text(text, font_obj, draw_obj)
        left = city_x + offset_x
        top = city_y + offset_y - (h / 2)
        padding = 4 * SS
        bbox = {
            'left': left - padding,
            'top': top - padding,
            'right': left + w + padding,
            'bottom': top + h + padding,
        }
        return left, top, bbox
    
    # Check if two bboxes overlap
    def boxes_overlap(box1, box2):
        return not (box1['right'] < box2['left'] or 
                   box1['left'] > box2['right'] or
                   box1['bottom'] < box2['top'] or
                   box1['top'] > box2['bottom'])

    def box_outside_canvas(box):
        return (
            box['left'] < 0 or
            box['top'] < 0 or
            box['right'] > (W * SS) or
            box['bottom'] > (H * SS)
        )

    def grid_overlap_score(box, occupied_cells, cell_size=25):
        left = int(box['left'] / cell_size)
        right = int(box['right'] / cell_size)
        top = int(box['top'] / cell_size)
        bottom = int(box['bottom'] / cell_size)
        overlap = 0
        for gx in range(left, right + 1):
            for gy in range(top, bottom + 1):
                if (gx, gy) in occupied_cells:
                    overlap += 1
        return overlap

    preprinted_label_texts = {
        "Buon Ma Thuot": "Buon Me Thuat",
        "Phu Quoc": "Ile de Phu Quoc",
    }

    base_label_boxes = []
    for preprinted_name in preprinted_city_labels:
        pt = get_xy(preprinted_name)
        if not pt:
            continue
        city_obj = DB.find_city(preprinted_name)
        angle = city_obj.label_ang if city_obj and city_obj.label_ang is not None else 0
        dist_mult = city_obj.label_dist if city_obj and city_obj.label_dist else 1.0
        base_distance = 8 * SS * dist_mult
        _, _, bbox = resolve_label_box(
            pt[0] * SS,
            pt[1] * SS,
            angle,
            base_distance,
            preprinted_label_texts.get(preprinted_name, preprinted_name),
            font,
            draw,
        )
        base_label_boxes.append({"name": preprinted_name, "bbox": bbox})

    LABEL_OVERLAP_TOLERANCE = 0.18

    def box_area(box):
        return max(0, box["right"] - box["left"]) * max(0, box["bottom"] - box["top"])

    def box_overlap_area(box1, box2):
        left = max(box1["left"], box2["left"])
        right = min(box1["right"], box2["right"])
        top = max(box1["top"], box2["top"])
        bottom = min(box1["bottom"], box2["bottom"])
        return max(0, right - left) * max(0, bottom - top)

    def box_overlap_ratio(box1, box2):
        overlap = box_overlap_area(box1, box2)
        if overlap <= 0:
            return 0.0
        return overlap / max(1, min(box_area(box1), box_area(box2)))

    def tolerated_overlap_penalty(box, other_box, base_weight, tolerance=LABEL_OVERLAP_TOLERANCE):
        ratio = box_overlap_ratio(box, other_box)
        if ratio <= tolerance:
            return 0
        excess = (ratio - tolerance) / max(1 - tolerance, 1e-6)
        return base_weight + (base_weight * 4 * excess)

    def grid_cell_count(box, cell_size=25):
        left = int(box["left"] / cell_size)
        right = int(box["right"] / cell_size)
        top = int(box["top"] / cell_size)
        bottom = int(box["bottom"] / cell_size)
        return max(1, (right - left + 1) * (bottom - top + 1))

    def collision_score(box, placed_labels, current_label_name=None):
        score = 0
        for other in placed_labels:
            if other['placed'] and other['bbox'] and boxes_overlap(box, other['bbox']):
                score += tolerated_overlap_penalty(box, other["bbox"], 12)
        for other in base_label_boxes:
            if boxes_overlap(box, other['bbox']):
                score += tolerated_overlap_penalty(box, other["bbox"], 10)
        for icon_pos in icon_positions:
            if boxes_overlap(box, icon_pos['bbox']):
                score += tolerated_overlap_penalty(box, icon_pos["bbox"], 16)
        for marker_box in city_marker_boxes:
            if marker_box.get("name") == current_label_name:
                continue
            if boxes_overlap(box, marker_box):
                score += tolerated_overlap_penalty(box, marker_box, 10, tolerance=0.05)
        route_overlap = grid_overlap_score(box, drawn_route_cells, cell_size=25)
        route_ratio = route_overlap / grid_cell_count(box, cell_size=25)
        if route_ratio > LABEL_OVERLAP_TOLERANCE:
            score += min(route_overlap, 16) * 3 * (
                (route_ratio - LABEL_OVERLAP_TOLERANCE) / max(1 - LABEL_OVERLAP_TOLERANCE, 1e-6)
            )
        if box_outside_canvas(box):
            score += 10
        return score

    def angle_delta_deg(a, b):
        delta = (a - b) % 360
        if delta > 180:
            delta -= 360
        return abs(delta)

    def label_variant_unit(city_name, angle=0, distance=0, channel="score"):
        if label_variation_seed is None:
            return 0.0
        token = f"{label_variation_seed}|{city_name}|{channel}|{round(float(angle), 2)}|{round(float(distance), 2)}"
        value = 0
        for char in token:
            value = ((value * 131) + ord(char)) % 1000003
        return value / 1000003.0

    for label in label_data:
        nearby = 0
        for other in label_data:
            if other is label:
                continue
            if math.hypot(label['x'] - other['x'], label['y'] - other['y']) < (90 * SS):
                nearby += 1
        label['crowding'] = nearby

    # Place fixed/manual labels first, then crowded zones, then longer labels.
    label_data.sort(
        key=lambda item: (
            0 if item.get('direct_offset') else 1,
            -item.get('crowding', 0),
            -len(item.get('display_name', item['name'])),
        )
    )
    
    # Place labels with collision avoidance
    for i, label in enumerate(label_data):
        placed = False

        if label.get('suppress_text'):
            label['placed'] = True
            continue
        
        # Direct X/Y offset - simple! offset IS the position relative to city dot
        label_font = font_for_city_label(label['name'])
        if label.get('direct_offset'):
            offset_x, offset_y = label['direct_offset']
            lx, ly, bbox = resolve_direct_offset_box(
                label['x'],
                label['y'],
                offset_x,
                offset_y,
                label.get('display_name', label['name']),
                label_font,
                draw,
            )
            label['label_x'] = lx
            label['label_y'] = ly
            label['bbox'] = bbox
            label['placed'] = True
            continue

        candidate_positions = []
        display_text = label.get('display_name', label['name'])
        text_width, _ = measure_label_text(display_text, label_font, draw)
        text_scale = max(1.0, text_width / max(70 * SS, 1))
        crowding_scale = 1.0 + (label.get('crowding', 0) * 0.22)

        if label.get('use_predefined') and label.get('angles') and label.get('distances'):
            # Prefer the preset position, but allow fallback candidates when
            # it overlaps another label by more than the tolerated threshold.
            base_angle = label['angles'][0]
            base_distance = label['distances'][0]
            dynamic_distances = []
            for distance in [int(base_distance * 0.75), base_distance, int(base_distance * 1.25)]:
                if distance not in dynamic_distances:
                    dynamic_distances.append(distance)
            for extra_distance in [10, 18, 28, 42, 58]:
                scaled = int(base_distance + extra_distance * SS * text_scale * crowding_scale)
                if scaled not in dynamic_distances:
                    dynamic_distances.append(scaled)
            dynamic_angles = []
            fallback_angles = [
                base_angle,
                base_angle - 30,
                base_angle + 30,
                base_angle - 60,
                base_angle + 60,
                base_angle - 90,
                base_angle + 90,
                base_angle + 180,
                0, -45, -90, 45, 90, -135, 180, 135,
            ]
            for angle in fallback_angles:
                normalized = ((angle + 180) % 360) - 180
                if normalized not in dynamic_angles:
                    dynamic_angles.append(normalized)
            for distance in dynamic_distances:
                for angle in dynamic_angles:
                    candidate_positions.append((angle, distance))
        else:
            dynamic_distances = list(label.get('distances', []))
            # Keep search area TIGHT — overlap is better than jumping far
            for extra_distance in [6, 18, 26, 34, 46]:
                scaled = int(extra_distance * SS * text_scale * crowding_scale)
                if scaled not in dynamic_distances:
                    dynamic_distances.append(scaled)
            dynamic_angles = []
            for angle in (label.get('angles', []) + [-30, 30, -60, 60, -120, 120, 150, -150, 180]):
                if angle not in dynamic_angles:
                    dynamic_angles.append(angle)
            for distance in dynamic_distances:
                for angle in dynamic_angles:
                    candidate_positions.append((angle, distance))

        variant_preferred = None
        if label_variation_seed is not None and candidate_positions:
            variant_index = int(label_variant_unit(
                label['name'],
                label.get('crowding', 0),
                len(candidate_positions),
                "candidate",
            ) * len(candidate_positions))
            variant_preferred = candidate_positions[min(variant_index, len(candidate_positions) - 1)]

        best_candidate = None
        best_score = float('inf')
        best_close_candidate = None
        best_close_score = float('inf')
        close_distance_limit = max(32 * SS, (32 + min(label.get('crowding', 0), 3) * 10) * SS)

        for angle, distance in candidate_positions:
            lx, ly, bbox = resolve_label_box(
                label['x'],
                label['y'],
                angle,
                distance,
                display_text,
                label_font,
                draw,
            )
            score = collision_score(bbox, label_data[:i], label['name'])
            distance_penalty = distance / max(28 * SS * max(crowding_scale, 1), 1)
            score += distance_penalty
            if label.get('use_predefined') and label.get('angles'):
                score += angle_delta_deg(angle, label['angles'][0]) / 180.0
            if label.get('use_predefined') and label.get('distances'):
                score += abs(distance - label['distances'][0]) / max(28 * SS, 1) * 0.35
            if label.get('crowding', 0) <= 1 and distance > (40 * SS):
                score += 2.5
            if variant_preferred:
                preferred_angle, preferred_distance = variant_preferred
                crowding_weight = 0.75 + min(label.get('crowding', 0), 4) * 0.35
                score += angle_delta_deg(angle, preferred_angle) / 180.0 * crowding_weight
                score += abs(distance - preferred_distance) / max(70 * SS, 1) * 0.25
                score += label_variant_unit(label['name'], angle, distance, "jitter") * 0.18

            if score < best_score:
                best_score = score
                best_candidate = (lx, ly, bbox, distance)

            if distance <= close_distance_limit and score < best_close_score:
                best_close_score = score
                best_close_candidate = (lx, ly, bbox, distance)

            if score == 0:
                label['label_x'] = lx
                label['label_y'] = ly
                label['bbox'] = bbox
                label['placed'] = True
                placed = True
                break

        if not placed and best_candidate:
            chosen = best_candidate
            if best_close_candidate:
                far_distance = best_candidate[3]
                if far_distance > close_distance_limit and best_close_score <= (best_score + 4.5):
                    chosen = best_close_candidate
            label['label_x'], label['label_y'], label['bbox'], _ = chosen
            label['placed'] = True
    
    def draw_star_marker(draw_obj, cx, cy, outer_r, inner_r):
        points = []
        for idx in range(10):
            angle = math.radians(-90 + idx * 36)
            radius = outer_r if idx % 2 == 0 else inner_r
            points.append((cx + math.cos(angle) * radius, cy + math.sin(angle) * radius))
        closed = points + [points[0]]
        draw_obj.line(closed, fill=(255, 255, 255, 230), width=max(1, int(5 * SS)), joint="curve")
        draw_obj.line(closed, fill=(255, 0, 0, 255), width=max(1, int(3 * SS)), joint="curve")

    star_icon = None
    star_icon_path = os.path.join(MAP_STYLE_DIR, "shared", "star_icon.png")
    if os.path.exists(star_icon_path):
        try:
            star_icon = Image.open(star_icon_path).convert("RGBA")
        except Exception:
            star_icon = None

    def paste_star_marker(cx, cy, size_px):
        if not star_icon:
            draw_star_marker(draw, cx, cy, outer_r=15 * SS, inner_r=6 * SS)
            return
        icon_resized = star_icon.resize((size_px, size_px), Image.Resampling.LANCZOS)
        px = int(cx - size_px / 2)
        py = int(cy - size_px / 2)
        overlay.paste(icon_resized, (px, py), icon_resized)

    def paste_city_decoration(label, mode_name, size_px, dx=45, dy=-42):
        icon = icons.get(mode_name)
        if not icon:
            return
        icon_resized = icon.resize((size_px, size_px), Image.Resampling.LANCZOS)
        center_x = label["x"] + dx * SS
        center_y = label["y"] + dy * SS
        px = int(center_x - size_px / 2)
        py = int(center_y - size_px / 2)
        overlay.paste(icon_resized, (px, py), icon_resized)

    star_marker_cities = {"Ha Noi"}
    city_decorations = {
        "Ha Long": {"mode": "boat", "size": scaled_icon_px(58 * SS, "boat"), "dx": 45, "dy": -42},
        "Lan Ha": {"mode": "boat", "size": scaled_icon_px(58 * SS, "boat"), "dx": 45, "dy": -42},
    }

    # Now draw all markers and labels
    for label in label_data:
        x, y = label['x'], label['y']
        
        # Draw marker
        city_obj = DB.find_city(label['name'])
        marker_fill = marker_color_vn if city_obj and city_obj.country == "VN" else marker_color_foreign
        if label["name"] in star_marker_cities:
            paste_star_marker(x, y, size_px=30 * SS)
        else:
            r = (6 if city_obj and city_obj.country == "VN" else 4) * SS
            draw.ellipse((x-r, y-r, x+r, y+r), fill=marker_fill, outline="white", width=2)
        
        # Draw label at calculated position
        if not label.get('suppress_text') and label['label_x'] and label['label_y']:
            # Use display_name which already includes any custom text overrides
            display_text = label.get('display_name', label['name'])
            text_fill = (0xCC, 0x00, 0x00, 255) if label["name"] == "Ha Noi" else "black"
            bbox = label.get('bbox')

            if bbox:
                connect_x = min(max(x, bbox['left']), bbox['right'])
                connect_y = min(max(y, bbox['top']), bbox['bottom'])
                dx = connect_x - x
                dy = connect_y - y
                if math.hypot(dx, dy) > (18 * SS):
                    draw.line(
                        [(x, y), (connect_x, connect_y)],
                        fill=(90, 90, 90, 180),
                        width=max(1, int(1.2 * SS))
                    )
            
            draw.text(
                (label['label_x'], label['label_y']), 
                display_text,
                font=font_for_city_label(label['name']),
                fill=text_fill
            )

        decoration = city_decorations.get(label["name"])
        if decoration and not label.get("suppress_text"):
            paste_city_decoration(
                label,
                decoration["mode"],
                decoration["size"],
                dx=decoration.get("dx", 45),
                dy=decoration.get("dy", -42),
            )
    
    # Draw Manual Icons (free-floating, not on routes)
    for manual_icon in manual_icons:
        city_name = manual_icon.get('city')
        icon_type = manual_icon.get('type', 'car')
        angle_deg = manual_icon.get('angle', 0)
        distance_px = manual_icon.get('distance', 30)
        
        pt = get_xy(city_name)
        if pt and icon_type in icons:
            # Calculate position based on angle and distance from city
            rad = math.radians(angle_deg)
            x = (pt[0] + math.cos(rad) * distance_px) * SS
            y = (pt[1] + math.sin(rad) * distance_px) * SS
            
            # Paste icon at calculated position
            icon_img = icons[icon_type]
            size_px = scaled_icon_px(40 * SS, icon_type)
            icon_resized = icon_img.resize((size_px, size_px), Image.Resampling.LANCZOS)
            px = int(x - size_px / 2)
            py = int(y - size_px / 2)
            overlay.paste(icon_resized, (px, py), icon_resized)
    
    # Draw Arrival and Departure Markers with SMART ANGLE SELECTION
    # Build occupied regions from routes and cities for collision detection
    occupied_points = set()
    
    # Add route points to occupied set - with expanded radius to avoid overlap
    for leg in route:
        pt_a = get_xy(leg["a"])
        pt_b = get_xy(leg["b"])
        if pt_a and pt_b:
            x0, y0 = pt_a[0] * SS, pt_a[1] * SS
            x2, y2 = pt_b[0] * SS, pt_b[1] * SS
            pc = control_point((x0, y0), (x2, y2), leg.get("bulge", CURVE_BULGE))
            pts = sample_curve((x0, y0), pc, (x2, y2), n=80)
            for px, py in pts:
                # Add to grid with expanded radius (5 cells around each point)
                gx, gy = int(px / 20), int(py / 20)
                for dx in range(-3, 4):
                    for dy in range(-3, 4):
                        occupied_points.add((gx + dx, gy + dy))
    
    # Add city marker positions to occupied set
    for city_name in sorted(city for city in visible_cities if city):
        pt = get_xy(city_name)
        if pt:
            x, y = pt[0] * SS, pt[1] * SS
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    occupied_points.add((int(x / 20) + dx, int(y / 20) + dy))

    # Add placed label boxes so arrival/departure markers do not cross text
    for label in label_data:
        bbox = label.get("bbox")
        if not bbox:
            continue
        left = int(bbox["left"] / 20)
        right = int(bbox["right"] / 20)
        top = int(bbox["top"] / 20)
        bottom = int(bbox["bottom"] / 20)
        for gx in range(left, right + 1):
            for gy in range(top, bottom + 1):
                occupied_points.add((gx, gy))

    for icon_pos in icon_positions:
        bbox = icon_pos.get("bbox")
        if not bbox:
            continue
        left = int(bbox["left"] / 20)
        right = int(bbox["right"] / 20)
        top = int(bbox["top"] / 20)
        bottom = int(bbox["bottom"] / 20)
        for gx in range(left, right + 1):
            for gy in range(top, bottom + 1):
                occupied_points.add((gx, gy))
    
    marker_icon_size = scaled_icon_px(48 * SS, "plane") if "plane" in icons else 0
    marker_icon_t_from_city = 0.68

    def marker_curve_geometry(p_city, p_edge, marker_type):
        if marker_type == "arrival":
            p_start, p_end = p_edge, p_city
            icon_t = 1.0 - marker_icon_t_from_city
        else:
            p_start, p_end = p_city, p_edge
            icon_t = marker_icon_t_from_city
        pc = control_point(p_start, p_end, CURVE_BULGE)
        return p_start, pc, p_end, icon_t

    def curve_icon_bbox(p_start, pc, p_end, icon_t, size_px, padding_px):
        x, y = quad_point(p_start, pc, p_end, icon_t)
        half = size_px / 2
        return {
            "left": x - half - padding_px,
            "top": y - half - padding_px,
            "right": x + half + padding_px,
            "bottom": y + half + padding_px,
        }

    def mark_box_occupied(box, occupied, cell_size=20):
        left = int(box["left"] / cell_size)
        right = int(box["right"] / cell_size)
        top = int(box["top"] / cell_size)
        bottom = int(box["bottom"] / cell_size)
        for gx in range(left, right + 1):
            for gy in range(top, bottom + 1):
                occupied.add((gx, gy))

    def score_curve_path(p_city, angle, radius, occupied, marker_type):
        """Calculate how many occupied grid cells this angle would cross."""
        p_edge = radial_point(p_city, angle, radius)
        p_start, pc, p_end, icon_t = marker_curve_geometry(p_city, p_edge, marker_type)
        pts = sample_curve(p_start, pc, p_end, n=30)
        
        overlap_count = 0
        for px, py in pts:
            grid_key = (int(px / 20), int(py / 20))
            if grid_key in occupied:
                overlap_count += 1
        return overlap_count, p_edge, p_start, pc, p_end, icon_t

    def point_outside_canvas(point):
        return point[0] < 0 or point[1] < 0 or point[0] > (W * SS) or point[1] > (H * SS)

    def score_marker_candidate(p_city, angle, radius, label_text, occupied, preference_rank, marker_type):
        curve_overlap, p_edge, p_start, pc, p_end, icon_t = score_curve_path(
            p_city,
            angle,
            radius,
            occupied,
            marker_type,
        )
        lx, ly, bbox = resolve_label_box(
            p_edge[0],
            p_edge[1],
            angle,
            6 * SS,
            label_text,
            font,
            draw,
        )
        label_overlap = grid_overlap_score(bbox, occupied, cell_size=20)
        score = curve_overlap
        score += label_overlap * 2.6
        score += preference_rank * 0.75
        score += max(radius - (0.18 * min(W, H) * SS), 0) / max(24 * SS, 1)
        icon_bbox = None
        if marker_icon_size:
            icon_bbox = curve_icon_bbox(p_start, pc, p_end, icon_t, marker_icon_size, 12 * SS)
            icon_overlap = grid_overlap_score(icon_bbox, occupied, cell_size=20)
            score += icon_overlap * 6.0
            if boxes_overlap(icon_bbox, bbox):
                score += 16
            for other in base_label_boxes:
                if boxes_overlap(icon_bbox, other["bbox"]):
                    score += 20
            for placed_label in label_data:
                placed_bbox = placed_label.get("bbox")
                if placed_bbox and boxes_overlap(icon_bbox, placed_bbox):
                    score += 22
            for icon_pos in icon_positions:
                if boxes_overlap(icon_bbox, icon_pos["bbox"]):
                    score += 34
            if box_outside_canvas(icon_bbox):
                score += 18
        if point_outside_canvas(p_edge):
            score += 25
        if box_outside_canvas(bbox):
            score += 18
        margin = min(
            p_edge[0],
            p_edge[1],
            (W * SS) - p_edge[0],
            (H * SS) - p_edge[1],
        )
        if margin < (28 * SS):
            score += ((28 * SS) - margin) / max(6 * SS, 1)
        return score, p_edge, lx, ly, bbox, p_start, pc, p_end, icon_t, icon_bbox

    def find_best_marker_layout(p_city, base_radius, preferred_angles, label_text, marker_type):
        candidate_angles = []
        seen_angles = set()
        for angle in preferred_angles + [-180, -157, -135, -112, -90, -67, -45, -22, 0, 22, 45, 67, 90, 112, 135, 157, 180]:
            normalized = ((angle + 180) % 360) - 180
            if normalized not in seen_angles:
                candidate_angles.append(normalized)
                seen_angles.add(normalized)

        best = None
        radius_steps = [1.0, 1.15, 1.3, 1.48]
        for radius_mult in radius_steps:
            radius = base_radius * radius_mult
            for rank, angle in enumerate(candidate_angles):
                score, p_edge, lx, ly, bbox, p_start, pc, p_end, icon_t, icon_bbox = score_marker_candidate(
                    p_city,
                    angle,
                    radius,
                    label_text,
                    occupied_points,
                    rank,
                    marker_type,
                )
                if best is None or score < best["score"]:
                    best = {
                        "score": score,
                        "angle": angle,
                        "radius": radius,
                        "p_edge": p_edge,
                        "label_x": lx,
                        "label_y": ly,
                        "label_bbox": bbox,
                        "p_start": p_start,
                        "pc": pc,
                        "p_end": p_end,
                        "icon_t": icon_t,
                        "icon_bbox": icon_bbox,
                    }
                if score <= 0.5:
                    return best
        return best
    
    for marker_type, city_name in [("arrival", arrival_city), ("departure", departure_city)]:
        if not city_name or city_name == "None":
            continue
        
        pt = get_xy(city_name)
        if not pt:
            continue
        
        # City center point (scaled)
        cx, cy = pt[0] * SS, pt[1] * SS
        p_city = (cx, cy)
        
        # Calculate radial distance (18% of smaller map dimension)
        mWH = min(W, H)
        radius = 0.18 * mWH * SS
        
        # Check for custom offset from user click
        custom_offset = arrival_offset if marker_type == "arrival" else departure_offset
        label_text = TRANSLATIONS.get(language, TRANSLATIONS["EN"]).get(marker_type, marker_type.title())
        
        if custom_offset:
            # User clicked a custom position - use it directly
            p_edge = (custom_offset["x"] * SS, custom_offset["y"] * SS)
            p_start, pc, p_end, icon_t = marker_curve_geometry(p_city, p_edge, marker_type)
            icon_bbox = curve_icon_bbox(p_start, pc, p_end, icon_t, marker_icon_size, 12 * SS) if marker_icon_size else None
            label_x, label_y, label_bbox = resolve_label_box(
                p_edge[0],
                p_edge[1],
                -90 if marker_type == "arrival" else 45,
                6 * SS,
                label_text,
                font,
                draw,
            )
        else:
            if marker_type == "arrival":
                # Arrival: prefer upper-left quadrant
                preferred = [-135, -112, -157, -90, -45, -22, 180, 135, 157, 112, 90, 45, 0]
            else:
                # Departure: prefer lower-right or lower-left before upper quadrants
                preferred = [45, 67, 22, 90, 112, 0, 135, -45, 157, -67, 180, -90, -135]
            if _rng is not None:
                _rng.shuffle(preferred)

            best_layout = find_best_marker_layout(p_city, radius, preferred, label_text, marker_type)
            p_edge = best_layout["p_edge"]
            label_x = best_layout["label_x"]
            label_y = best_layout["label_y"]
            label_bbox = best_layout["label_bbox"]
            p_start = best_layout["p_start"]
            pc = best_layout["pc"]
            p_end = best_layout["p_end"]
            icon_t = best_layout["icon_t"]
            icon_bbox = best_layout["icon_bbox"]
        
        pts = sample_curve(p_start, pc, p_end, n=220)

        ad_dash_on, ad_dash_off = dash_for("arrival_departure")
        draw_dashed(draw, pts, color_arrival_departure,
                    scaled_line_width(2 * SS, "plane"),
                    dash_on=ad_dash_on, dash_off=ad_dash_off)

        if "plane" in icons:
            paste_icon_on_curve(overlay, icons["plane"], p_start, pc, p_end,
                                t=icon_t, size_px=marker_icon_size)

        draw.text(
            (label_x, label_y),
            label_text,
            font=font,
            fill=color_arrival_departure
        )

        # Register this marker's position so the next one avoids it
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                occupied_points.add((int(p_edge[0] / 20) + dx, int(p_edge[1] / 20) + dy))
        mark_box_occupied(label_bbox, occupied_points)
        if icon_bbox:
            mark_box_occupied(icon_bbox, occupied_points)
    
    # Downsample and Composite
    overlay = overlay.resize((W, H), Image.Resampling.LANCZOS)
    final = Image.alpha_composite(base_img, overlay)

    final.convert("RGB").save(output_path)
    return output_path