rustial_engine/symbols/

mod.rs

//! Symbol/cartography foundations: asset dependencies and placement.
//!
//! This module provides a small engine-owned symbol system inspired by the
//! higher-level responsibilities in MapLibre's `symbol/placement.ts` and image
//! / glyph management. It is intentionally foundational rather than complete:
//! the engine can now derive text/icon dependencies, perform basic collision
//! detection, de-duplicate nearby repeated labels, and preserve per-symbol fade
//! state across frames.
//!
//! ## Sub-modules
//!
//! | Module | Purpose |
//! |--------|---------|
//! | [`cross_tile_index`] | Cross-tile symbol deduplication index (MapLibre `CrossTileSymbolIndex` equivalent). |

pub mod cross_tile_index;
#[cfg(feature = "text-shaping")]
pub mod text_shaper;

use crate::camera_projection::CameraProjection;
use rustial_math::{GeoCoord, TileId, WorldBounds};
use std::collections::{BTreeSet, HashMap, HashSet};

/// A requested glyph in a font stack.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct GlyphKey {
    /// Font stack name used for the glyph.
    pub font_stack: String,
    /// Unicode scalar requested from the font stack.
    pub codepoint: char,
}

/// Symbol anchor position relative to the anchor point.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolAnchor {
    /// Centered on the anchor.
    Center,
    /// Above the anchor.
    Top,
    /// Below the anchor.
    Bottom,
    /// Left of the anchor.
    Left,
    /// Right of the anchor.
    Right,
    /// Above-left of the anchor.
    TopLeft,
    /// Above-right of the anchor.
    TopRight,
    /// Below-left of the anchor.
    BottomLeft,
    /// Below-right of the anchor.
    BottomRight,
}

impl SymbolAnchor {
    fn offset_signs(self) -> [f64; 2] {
        match self {
            SymbolAnchor::Center => [0.0, 0.0],
            SymbolAnchor::Top => [0.0, 1.0],
            SymbolAnchor::Bottom => [0.0, -1.0],
            SymbolAnchor::Left => [-1.0, 0.0],
            SymbolAnchor::Right => [1.0, 0.0],
            SymbolAnchor::TopLeft => [-1.0, 1.0],
            SymbolAnchor::TopRight => [1.0, 1.0],
            SymbolAnchor::BottomLeft => [-1.0, -1.0],
            SymbolAnchor::BottomRight => [1.0, -1.0],
        }
    }
}

/// Text writing mode for symbol labels.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolWritingMode {
    /// Left-to-right horizontal text flow.
    Horizontal,
    /// Top-to-bottom vertical text flow.
    Vertical,
}

impl Default for SymbolWritingMode {
    fn default() -> Self {
        Self::Horizontal
    }
}

/// Horizontal text justification for symbol labels.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolTextJustify {
    /// Match justification to the effective anchor direction.
    Auto,
    /// Align text toward the left side of the label box.
    Left,
    /// Center text within the label box.
    Center,
    /// Align text toward the right side of the label box.
    Right,
}

impl Default for SymbolTextJustify {
    fn default() -> Self {
        Self::Auto
    }
}

/// Text transformation applied before shaping and measurement.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolTextTransform {
    /// Keep source text unchanged.
    None,
    /// Convert text to uppercase.
    Uppercase,
    /// Convert text to lowercase.
    Lowercase,
}

impl Default for SymbolTextTransform {
    fn default() -> Self {
        Self::None
    }
}

/// Icon sizing mode relative to the label text box.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolIconTextFit {
    /// Keep the icon at its nominal size.
    None,
    /// Stretch the icon to match text width.
    Width,
    /// Stretch the icon to match text height.
    Height,
    /// Stretch the icon to match both text width and height.
    Both,
}

impl Default for SymbolIconTextFit {
    fn default() -> Self {
        Self::None
    }
}

/// Placement mode for symbol features.
///
/// Mapbox and MapLibre distinguish between point-placed symbols and symbols
/// that are anchored along line geometry. The engine still uses a simplified
/// line-placement model, but keeping the mode explicit in the shared symbol
/// types lets style parsing, candidate generation, and future parity work all
/// agree on the intended placement behavior.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolPlacement {
    /// Place symbols at point geometry anchors.
    Point,
    /// Place symbols along line geometry.
    Line,
}

impl Default for SymbolPlacement {
    fn default() -> Self {
        Self::Point
    }
}

/// Rasterized glyph bitmap.
#[derive(Debug, Clone, PartialEq)]
pub struct GlyphRaster {
    /// Bitmap width in pixels.
    pub width: u16,
    /// Bitmap height in pixels.
    pub height: u16,
    /// Horizontal advance in pixels.
    pub advance_x: f32,
    /// Left-side bearing in pixels.
    pub bearing_x: i16,
    /// Top bearing in pixels.
    pub bearing_y: i16,
    /// Alpha bitmap, row-major.
    pub alpha: Vec<u8>,
}

impl GlyphRaster {
    /// Create a new glyph raster.
    pub fn new(
        width: u16,
        height: u16,
        advance_x: f32,
        bearing_x: i16,
        bearing_y: i16,
        alpha: Vec<u8>,
    ) -> Self {
        Self {
            width,
            height,
            advance_x,
            bearing_x,
            bearing_y,
            alpha,
        }
    }
}

/// Glyph atlas entry metadata.
#[derive(Debug, Clone, PartialEq)]
pub struct GlyphAtlasEntry {
    /// Requested glyph key.
    pub key: GlyphKey,
    /// Atlas origin in pixels.
    pub origin: [u16; 2],
    /// Raster width/height in pixels.
    pub size: [u16; 2],
    /// Horizontal advance in pixels.
    pub advance_x: f32,
    /// Left-side bearing in pixels.
    pub bearing_x: i16,
    /// Top bearing in pixels.
    pub bearing_y: i16,
}

/// Glyph raster source used to populate a glyph atlas.
pub trait GlyphProvider: Send + Sync {
    /// Load or rasterize a glyph bitmap for the requested font/codepoint.
    fn load_glyph(&self, font_stack: &str, codepoint: char) -> Option<GlyphRaster>;

    /// Pixel size of 1 em as rasterized by this provider.
    ///
    /// The symbol batch builder divides `symbol.size_px` by this value to
    /// compute the scale factor that maps glyph atlas pixels to world units.
    /// Default is 24.0 (matching the MapLibre `ONE_EM` convention).
    fn render_em_pixels(&self) -> f32 {
        24.0
    }
}

/// A tiny built-in procedural glyph source for engine-side symbol plumbing.
#[derive(Debug, Clone, Default)]
pub struct ProceduralGlyphProvider;

impl ProceduralGlyphProvider {
    /// Create a procedural glyph provider.
    pub fn new() -> Self {
        Self
    }
}

impl GlyphProvider for ProceduralGlyphProvider {
    fn load_glyph(&self, _font_stack: &str, codepoint: char) -> Option<GlyphRaster> {
        let width = 8u16;
        let height = 12u16;
        let mut alpha = vec![0u8; width as usize * height as usize];
        let seed = codepoint as u32;
        for y in 0..height as usize {
            for x in 0..width as usize {
                let border = x == 0 || y == 0 || x + 1 == width as usize || y + 1 == height as usize;
                let bits = ((seed >> ((x + y) % 8)) & 1) != 0;
                let horizontal = y == 3 || y == 6 || y == 9;
                let vertical = x == 2 || x == 5;
                alpha[y * width as usize + x] = if border || (bits && (horizontal || vertical)) {
                    255
                } else {
                    0
                };
            }
        }
        Some(GlyphRaster::new(width, height, width as f32 + 1.0, 0, height as i16, alpha))
    }

    fn render_em_pixels(&self) -> f32 {
        12.0
    }
}

/// Number of pixels of SDF padding added around each glyph in the atlas.
///
/// The signed distance field extends this many pixels beyond the glyph
/// outline, enabling smooth anti-aliasing and configurable halo width.
/// Matches the MapLibre `GLYPH_PBF_BORDER` value of 3.
const SDF_BUFFER: u16 = 3;

/// Requested glyph set for symbol text rendering.
#[derive(Debug, Clone)]
pub struct GlyphAtlas {
    requested: BTreeSet<GlyphKey>,
    entries: HashMap<GlyphKey, GlyphAtlasEntry>,
    alpha: Vec<u8>,
    dimensions: [u16; 2],
    render_em_px: f32,
}

impl Default for GlyphAtlas {
    fn default() -> Self {
        Self {
            requested: BTreeSet::new(),
            entries: HashMap::new(),
            alpha: Vec::new(),
            dimensions: [0, 0],
            render_em_px: 24.0,
        }
    }
}

impl GlyphAtlas {
    /// Create an empty glyph atlas request set.
    pub fn new() -> Self {
        Self::default()
    }

    /// Request all glyphs needed to render a text string.
    pub fn request_text(&mut self, font_stack: &str, text: &str) {
        for codepoint in text.chars() {
            self.requested.insert(GlyphKey {
                font_stack: font_stack.to_owned(),
                codepoint,
            });
        }
    }

    /// Iterate requested glyphs.
    pub fn requested(&self) -> impl Iterator<Item = &GlyphKey> {
        self.requested.iter()
    }

    /// Number of unique requested glyphs.
    pub fn len(&self) -> usize {
        self.requested.len()
    }

    /// Whether there are no requested glyphs.
    pub fn is_empty(&self) -> bool {
        self.requested.is_empty()
    }

    /// Loaded atlas entries.
    pub fn entries(&self) -> impl Iterator<Item = &GlyphAtlasEntry> {
        self.entries.values()
    }

    /// Look up a glyph entry by font stack and codepoint.
    pub fn get(&self, font_stack: &str, codepoint: char) -> Option<&GlyphAtlasEntry> {
        self.entries.get(&GlyphKey {
            font_stack: font_stack.to_owned(),
            codepoint,
        })
    }

    /// Packed alpha bitmap for the atlas.
    pub fn alpha(&self) -> &[u8] {
        &self.alpha
    }

    /// Atlas dimensions in pixels.
    pub fn dimensions(&self) -> [u16; 2] {
        self.dimensions
    }

    /// Pixel size of 1 em as reported by the provider used for the last
    /// [`load_requested`](Self::load_requested) call.
    pub fn render_em_px(&self) -> f32 {
        self.render_em_px
    }

    /// Load all requested glyphs into a packed atlas using a glyph provider.
    ///
    /// Each glyph is rasterized by the provider, then converted to a signed
    /// distance field (SDF) with [`SDF_BUFFER`] pixels of padding.  The
    /// resulting atlas can be used directly with an SDF text shader.
    pub fn load_requested(&mut self, provider: &dyn GlyphProvider) {
        self.entries.clear();
        self.alpha.clear();
        self.dimensions = [0, 0];
        self.render_em_px = provider.render_em_pixels();

        let mut rasters: Vec<(GlyphKey, GlyphRaster)> = Vec::new();
        for key in &self.requested {
            if let Some(raster) = provider.load_glyph(&key.font_stack, key.codepoint) {
                rasters.push((key.clone(), raster));
            }
        }
        if rasters.is_empty() {
            return;
        }

        // Apply SDF distance transform with padding to each glyph.
        let buf = SDF_BUFFER;
        let rasters: Vec<(GlyphKey, GlyphRaster)> = rasters
            .into_iter()
            .map(|(key, raster)| {
                if raster.width == 0 || raster.height == 0 {
                    return (key, raster); // Whitespace: keep as-is.
                }
                let sdf_alpha = binary_to_sdf(
                    &raster.alpha,
                    raster.width as usize,
                    raster.height as usize,
                    buf as usize,
                );
                (
                    key,
                    GlyphRaster::new(
                        raster.width + buf * 2,
                        raster.height + buf * 2,
                        raster.advance_x,
                        raster.bearing_x - buf as i16,
                        raster.bearing_y + buf as i16,
                        sdf_alpha,
                    ),
                )
            })
            .collect();

        let padding = 1u16;
        let atlas_width = rasters
            .iter()
            .map(|(_, raster)| raster.width + padding)
            .sum::<u16>()
            .max(1);
        let atlas_height = rasters
            .iter()
            .map(|(_, raster)| raster.height)
            .max()
            .unwrap_or(0)
            + padding * 2;

        self.dimensions = [atlas_width, atlas_height.max(1)];
        self.alpha = vec![0; atlas_width as usize * self.dimensions[1] as usize];

        let mut cursor_x = padding;
        for (key, raster) in rasters {
            let atlas_key = key.clone();
            let origin = [cursor_x, padding];
            blit_alpha(
                &mut self.alpha,
                self.dimensions[0] as usize,
                origin,
                raster.width as usize,
                raster.height as usize,
                &raster.alpha,
            );
            self.entries.insert(
                atlas_key,
                GlyphAtlasEntry {
                    key,
                    origin,
                    size: [raster.width, raster.height],
                    advance_x: raster.advance_x,
                    bearing_x: raster.bearing_x,
                    bearing_y: raster.bearing_y,
                },
            );
            cursor_x += raster.width + padding;
        }
    }
}

/// A sprite or standalone image dependency.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SpriteImage {
    /// Stable image id.
    pub id: String,
    /// Pixel origin in a sprite sheet.
    pub origin: [u32; 2],
    /// Image pixel size.
    pub pixel_size: [u32; 2],
}

impl SpriteImage {
    /// Create a new image descriptor.
    pub fn new(id: impl Into<String>, pixel_size: [u32; 2]) -> Self {
        Self {
            id: id.into(),
            origin: [0, 0],
            pixel_size,
        }
    }

    /// Set the sprite-sheet origin for this image.
    pub fn with_origin(mut self, origin: [u32; 2]) -> Self {
        self.origin = origin;
        self
    }
}

/// Registered sprite-sheet metadata.
#[derive(Debug, Clone, Default)]
pub struct SpriteSheet {
    images: HashMap<String, SpriteImage>,
}

impl SpriteSheet {
    /// Create an empty sprite sheet registry.
    pub fn new() -> Self {
        Self::default()
    }

    /// Register or replace a sprite image.
    pub fn register(&mut self, image: SpriteImage) {
        self.images.insert(image.id.clone(), image);
    }

    /// Look up a sprite image.
    pub fn get(&self, id: &str) -> Option<&SpriteImage> {
        self.images.get(id)
    }

    /// Iterate registered sprite images.
    pub fn iter(&self) -> impl Iterator<Item = &SpriteImage> {
        self.images.values()
    }

    /// Parse a MapLibre-style sprite index JSON document.
    #[cfg(feature = "style-json")]
    pub fn from_index_json(json: &str) -> Result<Self, SpriteSheetParseError> {
        use serde::Deserialize;

        #[derive(Deserialize)]
        struct SpriteIndexEntry {
            x: u32,
            y: u32,
            width: u32,
            height: u32,
        }

        let index: HashMap<String, SpriteIndexEntry> = serde_json::from_str(json)
            .map_err(SpriteSheetParseError::Json)?;
        let mut sheet = SpriteSheet::new();
        for (id, entry) in index {
            sheet.register(
                SpriteImage::new(id, [entry.width, entry.height]).with_origin([entry.x, entry.y]),
            );
        }
        Ok(sheet)
    }
}

/// Errors while parsing a sprite-sheet index.
#[cfg(feature = "style-json")]
#[derive(Debug)]
pub enum SpriteSheetParseError {
    /// JSON parse failure.
    Json(serde_json::Error),
}

#[cfg(feature = "style-json")]
impl std::fmt::Display for SpriteSheetParseError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            SpriteSheetParseError::Json(err) => write!(f, "sprite sheet parse error: {err}"),
        }
    }
}

#[cfg(feature = "style-json")]
impl std::error::Error for SpriteSheetParseError {}

/// Tracks symbol image dependencies.
#[derive(Debug, Clone, Default)]
pub struct ImageManager {
    sprites: SpriteSheet,
    images: HashMap<String, SpriteImage>,
    referenced: BTreeSet<String>,
}

impl ImageManager {
    /// Create an empty image manager.
    pub fn new() -> Self {
        Self::default()
    }

    /// Register a sprite-sheet image.
    pub fn register_sprite(&mut self, image: SpriteImage) {
        self.sprites.register(image);
    }

    /// Register a standalone image.
    pub fn register_image(&mut self, image: SpriteImage) {
        self.images.insert(image.id.clone(), image);
    }

    /// Load a sprite-sheet index JSON document.
    #[cfg(feature = "style-json")]
    pub fn load_sprite_sheet_index_json(&mut self, json: &str) -> Result<(), SpriteSheetParseError> {
        self.sprites = SpriteSheet::from_index_json(json)?;
        Ok(())
    }

    /// Mark an image id as required by the current symbol set.
    pub fn request(&mut self, id: &str) {
        self.referenced.insert(id.to_owned());
    }

    /// Check whether an image is known either as a sprite or standalone image.
    pub fn contains(&self, id: &str) -> bool {
        self.images.contains_key(id) || self.sprites.get(id).is_some()
    }

    /// Iterate referenced image ids.
    pub fn referenced(&self) -> impl Iterator<Item = &str> {
        self.referenced.iter().map(String::as_str)
    }

    fn clear_requests(&mut self) {
        self.referenced.clear();
    }
}

/// Asset dependencies for a single placed symbol.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct SymbolAssetDependencies {
    /// Glyphs needed for text rendering.
    pub glyphs: BTreeSet<GlyphKey>,
    /// Referenced image ids needed for icon rendering.
    pub images: BTreeSet<String>,
}

/// Runtime registry of glyph and image dependencies derived from placed symbols.
#[derive(Debug, Clone, Default)]
pub struct SymbolAssetRegistry {
    glyphs: GlyphAtlas,
    images: ImageManager,
}

impl SymbolAssetRegistry {
    /// Create an empty symbol asset registry.
    pub fn new() -> Self {
        Self::default()
    }

    /// Immutable access to requested glyphs.
    pub fn glyphs(&self) -> &GlyphAtlas {
        &self.glyphs
    }

    /// Immutable access to tracked images.
    pub fn images(&self) -> &ImageManager {
        &self.images
    }

    /// Mutable access to tracked images for registration.
    pub fn images_mut(&mut self) -> &mut ImageManager {
        &mut self.images
    }

    /// Rebuild dependency state from placed symbols.
    pub fn rebuild_from_symbols(&mut self, symbols: &[PlacedSymbol]) {
        self.glyphs = GlyphAtlas::default();
        self.images.clear_requests();
        for symbol in symbols.iter().filter(|symbol| symbol.visible) {
            if let Some(text) = &symbol.text {
                self.glyphs.request_text(&symbol.font_stack, text);
            }
            if let Some(icon) = &symbol.icon_image {
                self.images.request(icon);
            }
        }
    }
}

/// Candidate symbol generated from a symbol layer before placement.
#[derive(Debug, Clone)]
pub struct SymbolCandidate {
    /// Stable per-feature candidate id used for fade persistence.
    pub id: String,
    /// Originating style/runtime layer id, when known.
    pub layer_id: Option<String>,
    /// Originating style source id, when known.
    pub source_id: Option<String>,
    /// Originating style source-layer id, when known.
    pub source_layer: Option<String>,
    /// Tile that supplied the symbol feature, when known.
    pub source_tile: Option<TileId>,
    /// Stable feature id for feature-state and queries.
    pub feature_id: String,
    /// Source-local feature index.
    pub feature_index: usize,
    /// Stable group id for candidate variants of the same conceptual symbol.
    ///
    /// Most symbols only generate one candidate, so this matches the unique
    /// per-feature candidate id. When optional text/icon fallback variants are
    /// emitted, they all share this group id so placement can choose the first
    /// variant that fits without treating the fallbacks as unrelated symbols.
    pub placement_group_id: String,
    /// Whether this symbol is point-placed or line-placed.
    pub placement: SymbolPlacement,
    /// Geographic anchor point for the symbol.
    pub anchor: GeoCoord,
    /// Optional label text.
    pub text: Option<String>,
    /// Optional icon image id.
    pub icon_image: Option<String>,
    /// Font stack to use for text glyph requests.
    pub font_stack: String,
    /// Stable cross-tile / cross-frame placement identity.
    pub cross_tile_id: String,
    /// Clockwise screen-space rotation in radians for line-following labels.
    ///
    /// Point-placed symbols keep this at `0`. Line-placed symbols use the
    /// local path direction at the chosen anchor so placeholder rendering can
    /// start following the line before full glyph shaping along paths exists.
    pub rotation_rad: f32,
    /// Nominal symbol size in pixels.
    pub size_px: f32,
    /// Additional collision padding in pixels.
    pub padding_px: f32,
    /// Whether overlap should be allowed.
    pub allow_overlap: bool,
    /// Whether this symbol should avoid blocking later symbols.
    pub ignore_placement: bool,
    /// Optional placement ordering key.
    ///
    /// Lower keys are placed first. `None` means the candidate keeps source
    /// order relative to other unsorted symbols.
    pub sort_key: Option<f32>,
    /// Optional radial offset measured in symbol-size units.
    pub radial_offset: Option<f32>,
    /// Explicit per-anchor offsets for variable anchor placement.
    pub variable_anchor_offsets: Option<Vec<(SymbolAnchor, [f32; 2])>>,
    /// Maximum point-label width before wrapping.
    pub text_max_width: Option<f32>,
    /// Preferred wrapped text line height.
    pub text_line_height: Option<f32>,
    /// Extra spacing between adjacent glyphs.
    pub text_letter_spacing: Option<f32>,
    /// Icon sizing mode relative to the text box.
    pub icon_text_fit: SymbolIconTextFit,
    /// Padding applied when fitting the icon around text.
    pub icon_text_fit_padding: [f32; 4],
    /// Preferred anchor candidates in priority order.
    pub anchors: Vec<SymbolAnchor>,
    /// Writing mode used to estimate collision and layout dimensions.
    pub writing_mode: SymbolWritingMode,
    /// Pixel-space text/icon offset.
    pub offset_px: [f32; 2],
    /// Primary fill colour used for placeholder rendering.
    pub fill_color: [f32; 4],
    /// Halo colour used for placeholder rendering.
    pub halo_color: [f32; 4],
}

impl SymbolCandidate {
    /// Build asset dependencies for this candidate.
    pub fn dependencies(&self) -> SymbolAssetDependencies {
        let mut deps = SymbolAssetDependencies::default();
        if let Some(text) = &self.text {
            for codepoint in text.chars() {
                deps.glyphs.insert(GlyphKey {
                    font_stack: self.font_stack.clone(),
                    codepoint,
                });
            }
        }
        if let Some(icon) = &self.icon_image {
            deps.images.insert(icon.clone());
        }
        deps
    }

    fn dedupe_key(&self, meters_per_pixel: f64) -> String {
        if !self.cross_tile_id.is_empty() {
            return self.cross_tile_id.clone();
        }
        cross_tile_id_for_symbol(self.text.as_deref(), self.icon_image.as_deref(), &self.anchor, meters_per_pixel)
    }
}

/// A simple collision box in world-space meters.
#[derive(Debug, Clone, PartialEq)]
pub struct SymbolCollisionBox {
    /// Minimum X/Y corner.
    pub min: [f64; 2],
    /// Maximum X/Y corner.
    pub max: [f64; 2],
}

impl SymbolCollisionBox {
    /// Whether two collision boxes overlap.
    pub fn intersects(&self, other: &Self) -> bool {
        !(self.max[0] <= other.min[0]
            || self.min[0] >= other.max[0]
            || self.max[1] <= other.min[1]
            || self.min[1] >= other.max[1])
    }
}

/// A pre-laid-out glyph quad for GPU rendering.
///
/// Positions are in pixels relative to the symbol anchor.  The batch builder
/// uses these directly instead of re-computing layout from the raw text string.
#[derive(Debug, Clone, PartialEq)]
pub struct GlyphQuad {
    /// Unicode codepoint (for atlas lookup).
    pub codepoint: char,
    /// Horizontal offset from the symbol anchor in pixels.
    pub x: f32,
    /// Vertical offset from the symbol anchor in pixels.
    pub y: f32,
}

/// A placed symbol after collision resolution.
#[derive(Debug, Clone)]
pub struct PlacedSymbol {
    /// Stable symbol id.
    pub id: String,
    /// Originating style/runtime layer id, when known.
    pub layer_id: Option<String>,
    /// Originating style source id, when known.
    pub source_id: Option<String>,
    /// Originating style source-layer id, when known.
    pub source_layer: Option<String>,
    /// Tile that supplied the symbol feature, when known.
    pub source_tile: Option<TileId>,
    /// Stable feature id for feature-state and queries.
    pub feature_id: String,
    /// Source-local feature index.
    pub feature_index: usize,
    /// Whether this symbol is point-placed or line-placed.
    pub placement: SymbolPlacement,
    /// Geographic anchor point.
    pub anchor: GeoCoord,
    /// World-space anchor point.
    pub world_anchor: [f64; 3],
    /// Optional text content.
    pub text: Option<String>,
    /// Optional icon image id.
    pub icon_image: Option<String>,
    /// Font stack for text rendering.
    pub font_stack: String,
    /// Stable cross-tile identity.
    pub cross_tile_id: String,
    /// Clockwise screen-space rotation in radians for rendering.
    pub rotation_rad: f32,
    /// Collision box used during placement.
    pub collision_box: SymbolCollisionBox,
    /// Selected anchor used for this placement.
    pub anchor_mode: SymbolAnchor,
    /// Writing mode used for this placement.
    pub writing_mode: SymbolWritingMode,
    /// Pixel-space offset applied during placement.
    pub offset_px: [f32; 2],
    /// Optional radial offset measured in symbol-size units.
    pub radial_offset: Option<f32>,
    /// Maximum point-label width before wrapping.
    pub text_max_width: Option<f32>,
    /// Preferred wrapped text line height.
    pub text_line_height: Option<f32>,
    /// Extra spacing between adjacent glyphs.
    pub text_letter_spacing: Option<f32>,
    /// Icon sizing mode relative to the text box.
    pub icon_text_fit: SymbolIconTextFit,
    /// Padding applied when fitting the icon around text.
    pub icon_text_fit_padding: [f32; 4],
    /// Nominal symbol size in pixels.
    pub size_px: f32,
    /// Placeholder fill colour used by current renderers.
    pub fill_color: [f32; 4],
    /// Placeholder halo colour used by current renderers.
    pub halo_color: [f32; 4],
    /// Fade opacity in `[0, 1]`.
    pub opacity: f32,
    /// Whether the symbol survived collision placement this frame.
    pub visible: bool,
    /// Pre-computed glyph positions relative to the symbol anchor (pixels).
    ///
    /// Populated by [`layout_symbol_glyphs`].  When non-empty the renderer
    /// uses these quads directly; when empty it falls back to naive
    /// character-by-character layout.
    pub glyph_quads: Vec<GlyphQuad>,
}

impl PlacedSymbol {
    /// Asset dependencies required by this placed symbol.
    pub fn dependencies(&self) -> SymbolAssetDependencies {
        SymbolCandidate {
            id: self.id.clone(),
            layer_id: self.layer_id.clone(),
            source_id: self.source_id.clone(),
            source_layer: self.source_layer.clone(),
            source_tile: self.source_tile,
            feature_id: self.feature_id.clone(),
            feature_index: self.feature_index,
            placement_group_id: self.id.clone(),
            placement: self.placement,
            anchor: self.anchor,
            text: self.text.clone(),
            icon_image: self.icon_image.clone(),
            font_stack: self.font_stack.clone(),
            cross_tile_id: self.cross_tile_id.clone(),
            rotation_rad: self.rotation_rad,
            size_px: 0.0,
            padding_px: 0.0,
            allow_overlap: true,
            ignore_placement: false,
            sort_key: None,
            radial_offset: self.radial_offset,
            variable_anchor_offsets: None,
            text_max_width: self.text_max_width,
            text_line_height: self.text_line_height,
            text_letter_spacing: self.text_letter_spacing,
            icon_text_fit: self.icon_text_fit,
            icon_text_fit_padding: self.icon_text_fit_padding,
            anchors: vec![self.anchor_mode],
            writing_mode: self.writing_mode,
            offset_px: self.offset_px,
            fill_color: self.fill_color,
            halo_color: self.halo_color,
        }
        .dependencies()
    }
}

/// Placement tuning parameters.
#[derive(Debug, Clone)]
pub struct SymbolPlacementConfig {
    /// Fade-in rate in opacity units per second.
    pub fade_in_per_second: f32,
    /// Fade-out rate in opacity units per second.
    pub fade_out_per_second: f32,
    /// Extra world-space margin multiplier used for viewport culling.
    pub viewport_padding_factor: f64,
}

impl Default for SymbolPlacementConfig {
    fn default() -> Self {
        Self {
            fade_in_per_second: 6.0,
            fade_out_per_second: 8.0,
            viewport_padding_factor: 2.0,
        }
    }
}

/// Stateful placement engine with collision handling and fade persistence.
#[derive(Debug, Clone, Default)]
pub struct SymbolPlacementEngine {
    /// Placement tuning parameters.
    pub config: SymbolPlacementConfig,
    previous_opacity: HashMap<String, f32>,
    previous_anchor: HashMap<String, SymbolAnchor>,
    /// Cross-tile symbol index for deduplicating labels across tile boundaries.
    pub cross_tile_index: cross_tile_index::CrossTileSymbolIndex,
}

impl SymbolPlacementEngine {
    /// Create a placement engine with default configuration.
    pub fn new() -> Self {
        Self::default()
    }

    /// Remove all cross-tile index entries for a specific tile.
    ///
    /// Call this when a tile is evicted from the tile cache so that the
    /// index releases the associated cross-tile IDs.
    pub fn remove_tile(&mut self, tile_id: &TileId) {
        self.cross_tile_index.remove_tile(tile_id);
    }

    /// Place candidates for the current frame.
    pub fn place_candidates(
        &mut self,
        candidates: &[SymbolCandidate],
        projection: CameraProjection,
        meters_per_pixel: f64,
        dt_seconds: f64,
        viewport_bounds: Option<&WorldBounds>,
    ) -> Vec<PlacedSymbol> {
        let dt = dt_seconds.max(0.0) as f32;
        let grouped_candidates = Self::group_symbol_candidates(candidates, meters_per_pixel);
        let mut result = Vec::new();
        let mut accepted_boxes = Vec::new();
        let mut seen_ids = HashSet::new();
        let mut dedupe = HashSet::new();

        for (placement_id, variants) in grouped_candidates {
            let Some(primary_candidate) = variants.first() else {
                continue;
            };
            seen_ids.insert(placement_id.clone());
            if !dedupe.insert(placement_id.clone()) {
                continue;
            }

            let anchors = ordered_candidate_anchors(
                primary_candidate,
                self.previous_anchor.get(&placement_id).copied(),
            );
            let mut chosen = None;
            for candidate in &variants {
                if candidate.text.is_none() && candidate.icon_image.is_none() {
                    continue;
                }
                for anchor in anchors.iter().copied() {
                    let collision_boxes =
                        candidate_collision_boxes(candidate, projection, anchor, meters_per_pixel);
                    if collision_boxes.is_empty()
                        || !collision_boxes.iter().any(|bbox| {
                            viewport_contains_box(
                                viewport_bounds,
                                bbox,
                                self.config.viewport_padding_factor,
                            )
                        })
                    {
                        continue;
                    }
                    let collides = !candidate.allow_overlap
                        && accepted_boxes
                            .iter()
                            .any(|other| collision_boxes.iter().any(|bbox| bbox.intersects(other)));
                    if !collides {
                        chosen = Some((candidate, anchor, collision_boxes));
                        break;
                    }
                }
                if chosen.is_some() {
                    break;
                }
            }

            let prev = self.previous_opacity.get(&placement_id).copied().unwrap_or(0.0);
            let opacity = if chosen.is_none() {
                (prev - self.config.fade_out_per_second * dt).max(0.0)
            } else {
                (prev + self.config.fade_in_per_second * dt).clamp(0.0, 1.0)
            };

            self.previous_opacity.insert(placement_id.clone(), opacity);
            if opacity <= 0.0 {
                continue;
            }

            let (selected_candidate, anchor_mode, collision_box, visible) = if let Some((selected_candidate, anchor_mode, collision_boxes)) = chosen {
                if !selected_candidate.ignore_placement {
                    accepted_boxes.extend(collision_boxes.iter().cloned());
                }
                self.previous_anchor.insert(placement_id.clone(), anchor_mode);
                (
                    selected_candidate,
                    anchor_mode,
                    merge_collision_boxes(&collision_boxes),
                    true,
                )
            } else {
                let fallback_anchor = self
                    .previous_anchor
                    .get(&placement_id)
                    .copied()
                    .unwrap_or_else(|| {
                        primary_candidate
                            .anchors
                            .first()
                            .copied()
                            .unwrap_or(SymbolAnchor::Center)
                    });
                let collision_boxes = candidate_collision_boxes(
                    primary_candidate,
                    projection,
                    fallback_anchor,
                    meters_per_pixel,
                );
                (
                    primary_candidate,
                    fallback_anchor,
                    merge_collision_boxes(&collision_boxes),
                    false,
                )
            };

            let world = projection.project(&selected_candidate.anchor);
            result.push(PlacedSymbol {
                id: selected_candidate.id.clone(),
                layer_id: selected_candidate.layer_id.clone(),
                source_id: selected_candidate.source_id.clone(),
                source_layer: selected_candidate.source_layer.clone(),
                source_tile: selected_candidate.source_tile,
                feature_id: selected_candidate.feature_id.clone(),
                feature_index: selected_candidate.feature_index,
                placement: selected_candidate.placement,
                anchor: selected_candidate.anchor,
                world_anchor: [world.position.x, world.position.y, world.position.z],
                text: selected_candidate.text.clone(),
                icon_image: selected_candidate.icon_image.clone(),
                font_stack: selected_candidate.font_stack.clone(),
                cross_tile_id: placement_id.clone(),
                rotation_rad: selected_candidate.rotation_rad,
                collision_box,
                anchor_mode,
                writing_mode: selected_candidate.writing_mode,
                offset_px: resolve_symbol_offset(
                    anchor_mode,
                    selected_candidate.offset_px,
                    selected_candidate.radial_offset,
                    selected_candidate.variable_anchor_offsets.as_deref(),
                    selected_candidate.size_px,
                ),
                radial_offset: None,
                text_max_width: selected_candidate.text_max_width,
                text_line_height: selected_candidate.text_line_height,
                text_letter_spacing: selected_candidate.text_letter_spacing,
                icon_text_fit: selected_candidate.icon_text_fit,
                icon_text_fit_padding: selected_candidate.icon_text_fit_padding,
                size_px: selected_candidate.size_px,
                fill_color: selected_candidate.fill_color,
                halo_color: selected_candidate.halo_color,
                opacity,
                visible,
                glyph_quads: Vec::new(),
            });
        }

        self.previous_opacity
            .retain(|id, opacity| seen_ids.contains(id) && *opacity > 0.0);
        self.previous_anchor.retain(|id, _| seen_ids.contains(id));
        result
    }

/// Group candidate variants by conceptual symbol before placement.
///
/// Optional text/icon semantics can emit several fallback candidates for one
/// underlying symbol. Grouping them here lets placement try the preferred
/// variant first and then fall back to a text-only or icon-only variant if the
/// full pair does not fit, while still keeping fade state keyed by the shared
/// cross-tile placement identity.
fn group_symbol_candidates<'a>(
    candidates: &'a [SymbolCandidate],
    meters_per_pixel: f64,
) -> Vec<(String, Vec<&'a SymbolCandidate>)> {
    let mut grouped: Vec<(String, Vec<&'a SymbolCandidate>)> = Vec::new();
    let mut group_indexes: HashMap<String, usize> = HashMap::new();

    for candidate in candidates {
        let placement_id = candidate.dedupe_key(meters_per_pixel);
        let group_key = format!("{}|{}", placement_id, candidate.placement_group_id);
        if let Some(index) = group_indexes.get(&group_key).copied() {
            grouped[index].1.push(candidate);
        } else {
            group_indexes.insert(group_key, grouped.len());
            grouped.push((placement_id, vec![candidate]));
        }
    }

        // Mapbox and MapLibre use `symbol-sort-key` to make placement order
        // explicit. Sorting at the grouped-symbol level keeps optional fallback
        // variants together while still honoring the requested inter-symbol
        // priority. When no sort keys are present, retain the original source
        // order to preserve the engine's existing behavior.
        if grouped
            .iter()
            .any(|(_, variants)| variants.first().and_then(|candidate| candidate.sort_key).is_some())
        {
            grouped.sort_by(|(_, a_variants), (_, b_variants)| {
                let a_key = a_variants.first().and_then(|candidate| candidate.sort_key).unwrap_or(0.0);
                let b_key = b_variants.first().and_then(|candidate| candidate.sort_key).unwrap_or(0.0);
                a_key
                    .partial_cmp(&b_key)
                    .unwrap_or(std::cmp::Ordering::Equal)
            });
        }

    grouped
}
}

/// Build a placeholder vector mesh from placed symbols.
pub fn symbol_mesh_from_placed_symbols(
    symbols: &[PlacedSymbol],
    projection: CameraProjection,
    meters_per_pixel: f64,
) -> crate::layers::VectorMeshData {
    let mut mesh = crate::layers::VectorMeshData::default();
    for symbol in symbols.iter().filter(|symbol| symbol.visible && symbol.opacity > 0.0) {
        let [half_w, half_h] = symbol_half_extents(
            symbol.size_px,
            symbol.text.as_deref(),
            symbol.icon_image.as_deref(),
            symbol.writing_mode,
            symbol.placement,
            symbol.text_max_width,
            symbol.text_line_height,
            symbol.text_letter_spacing,
            symbol.icon_text_fit,
            symbol.icon_text_fit_padding,
            symbol.offset_px,
            1.0,
        );
        append_symbol_quad(&mut mesh, symbol, projection, half_w * meters_per_pixel * 1.35, half_h * meters_per_pixel * 1.35, symbol.halo_color, symbol.opacity, meters_per_pixel);
        append_symbol_quad(&mut mesh, symbol, projection, half_w * meters_per_pixel, half_h * meters_per_pixel, symbol.fill_color, symbol.opacity, meters_per_pixel);
    }
    mesh
}

// ---------------------------------------------------------------------------
// Symbol glyph layout
// ---------------------------------------------------------------------------

/// Convert a [`SymbolAnchor`] to horizontal/vertical alignment factors.
///
/// Returns `(h_align, v_align)` where `0.0 = left/top`, `0.5 = center`,
/// `1.0 = right/bottom`.
fn anchor_align(anchor: SymbolAnchor) -> (f32, f32) {
    let h = match anchor {
        SymbolAnchor::Left | SymbolAnchor::TopLeft | SymbolAnchor::BottomLeft => 0.0,
        SymbolAnchor::Right | SymbolAnchor::TopRight | SymbolAnchor::BottomRight => 1.0,
        _ => 0.5,
    };
    let v = match anchor {
        SymbolAnchor::Top | SymbolAnchor::TopLeft | SymbolAnchor::TopRight => 0.0,
        SymbolAnchor::Bottom | SymbolAnchor::BottomLeft | SymbolAnchor::BottomRight => 1.0,
        _ => 0.5,
    };
    (h, v)
}

/// Compute per-glyph positions from the glyph atlas and store them in each
/// `PlacedSymbol::glyph_quads`.
///
/// This is the basic (non-shaping) layout path: glyphs are positioned
/// left-to-right using atlas advance/bearing metrics.  Point labels are
/// wrapped at `text_max_width` (in em-units) and the resulting block is
/// aligned according to `anchor_mode`.
///
/// When the `text-shaping` feature is enabled, call
/// [`layout_symbol_glyphs_shaped`] instead for proper kerning, ligatures,
/// BiDi reorder, and line breaking.
pub fn layout_symbol_glyphs(symbols: &mut [PlacedSymbol], atlas: &GlyphAtlas) {
    let em = atlas.render_em_px();
    for symbol in symbols.iter_mut() {
        symbol.glyph_quads.clear();
        if !symbol.visible || symbol.opacity <= 0.0 {
            continue;
        }
        let text = match &symbol.text {
            Some(t) if !t.is_empty() => t.clone(),
            _ => continue,
        };

        let scale = symbol.size_px / em.max(1.0);
        let letter_spacing = symbol.text_letter_spacing.unwrap_or(0.0) * symbol.size_px;
        let line_height = symbol.text_line_height.unwrap_or(1.2) * symbol.size_px;

        // Break text into lines based on text_max_width (for point labels).
        let max_line_width_px = if symbol.placement == SymbolPlacement::Point {
            symbol.text_max_width.map(|w| w * symbol.size_px)
        } else {
            None
        };

        let lines = break_text_simple(&text, atlas, &symbol.font_stack, scale, letter_spacing, max_line_width_px);
        if lines.is_empty() {
            continue;
        }

        // Compute per-line widths and total height.
        let line_widths: Vec<f32> = lines.iter().map(|glyphs| {
            glyphs.last().map(|(_, x, adv)| x + adv).unwrap_or(0.0)
        }).collect();
        let max_width = line_widths.iter().cloned().fold(0.0f32, f32::max);
        let total_height = lines.len() as f32 * line_height;

        // Anchor alignment.
        let (h_align, v_align) = anchor_align(symbol.anchor_mode);

        let mut quads = Vec::new();
        for (line_idx, (glyphs, line_w)) in lines.iter().zip(line_widths.iter()).enumerate() {
            // Justify: center each line relative to the widest line.
            let line_shift_x = (max_width - line_w) * 0.5;
            // Anchor-based horizontal offset.
            let anchor_x = -max_width * h_align;
            // Anchor-based vertical offset.
            let anchor_y = -total_height * v_align + line_idx as f32 * line_height;

            for &(codepoint, glyph_x, _advance) in glyphs {
                quads.push(GlyphQuad {
                    codepoint,
                    x: anchor_x + line_shift_x + glyph_x,
                    y: anchor_y,
                });
            }
        }

        symbol.glyph_quads = quads;
    }
}

/// Break text into lines and compute per-glyph x positions using atlas
/// metrics.  Returns lines of `(codepoint, x_pixel, advance_pixel)` tuples.
fn break_text_simple(
    text: &str,
    atlas: &GlyphAtlas,
    font_stack: &str,
    scale: f32,
    letter_spacing: f32,
    max_width: Option<f32>,
) -> Vec<Vec<(char, f32, f32)>> {
    let chars: Vec<char> = text.chars().collect();
    if chars.is_empty() {
        return Vec::new();
    }

    // First pass: compute advance for each character.
    let mut advances: Vec<f32> = Vec::with_capacity(chars.len());
    for &ch in &chars {
        let adv = atlas.get(font_stack, ch)
            .map(|e| e.advance_x * scale)
            .unwrap_or(0.0);
        advances.push(adv);
    }

    // Break into words at spaces.
    let mut lines: Vec<Vec<(char, f32, f32)>> = Vec::new();
    let mut current_line: Vec<(char, f32, f32)> = Vec::new();
    let mut cursor_x: f32 = 0.0;

    for (i, &ch) in chars.iter().enumerate() {
        let adv = advances[i];

        // Forced newline.
        if ch == '\n' {
            lines.push(std::mem::take(&mut current_line));
            cursor_x = 0.0;
            continue;
        }

        // Check if we should wrap before this word.
        if let Some(max_w) = max_width {
            if ch == ' ' && cursor_x > 0.0 {
                // Check if the next word would exceed max_width.
                let next_word_end = next_word_width(&chars, &advances, i + 1, letter_spacing);
                if cursor_x + adv + letter_spacing + next_word_end > max_w && !current_line.is_empty() {
                    lines.push(std::mem::take(&mut current_line));
                    cursor_x = 0.0;
                    continue; // Drop the space at line start.
                }
            }
        }

        if !current_line.is_empty() {
            cursor_x += letter_spacing;
        }
        current_line.push((ch, cursor_x, adv));
        cursor_x += adv;
    }
    if !current_line.is_empty() {
        lines.push(current_line);
    }

    lines
}

/// Measure the width of the next word (until the next space or end of text).
fn next_word_width(chars: &[char], advances: &[f32], start: usize, letter_spacing: f32) -> f32 {
    let mut w: f32 = 0.0;
    let mut first = true;
    for i in start..chars.len() {
        if chars[i] == ' ' || chars[i] == '\n' {
            break;
        }
        if !first {
            w += letter_spacing;
        }
        w += advances[i];
        first = false;
    }
    w
}

/// Lay out symbol glyphs using the text shaping engine.
///
/// Uses [`shape_text`](text_shaper::shape_text) for correct kerning,
/// ligatures, BiDi reordering, and line wrapping.  The shaped glyph
/// coordinates (in layout units) are scaled to pixel coordinates using
/// `symbol.size_px / ONE_EM`.
#[cfg(feature = "text-shaping")]
pub fn layout_symbol_glyphs_shaped(
    symbols: &mut [PlacedSymbol],
    registry: &mut text_shaper::FontRegistry,
) {
    use text_shaper::{ShapeTextOptions, TextAnchor, TextJustify, shape_text, ONE_EM};

    for symbol in symbols.iter_mut() {
        symbol.glyph_quads.clear();
        if !symbol.visible || symbol.opacity <= 0.0 {
            continue;
        }
        let text = match &symbol.text {
            Some(t) if !t.is_empty() => t.as_str(),
            _ => continue,
        };

        let anchor = match symbol.anchor_mode {
            SymbolAnchor::Center => TextAnchor::Center,
            SymbolAnchor::Top => TextAnchor::Top,
            SymbolAnchor::Bottom => TextAnchor::Bottom,
            SymbolAnchor::Left => TextAnchor::Left,
            SymbolAnchor::Right => TextAnchor::Right,
            SymbolAnchor::TopLeft => TextAnchor::TopLeft,
            SymbolAnchor::TopRight => TextAnchor::TopRight,
            SymbolAnchor::BottomLeft => TextAnchor::BottomLeft,
            SymbolAnchor::BottomRight => TextAnchor::BottomRight,
        };

        let options = ShapeTextOptions {
            font_stack: symbol.font_stack.clone(),
            max_width: if symbol.placement == SymbolPlacement::Point {
                symbol.text_max_width.or(Some(10.0))
            } else {
                None
            },
            line_height: symbol.text_line_height.unwrap_or(1.2),
            letter_spacing: symbol.text_letter_spacing.unwrap_or(0.0),
            justify: TextJustify::Center,
            anchor,
            writing_mode: symbol.writing_mode,
            text_transform: SymbolTextTransform::None,
        };

        let shaped = match shape_text(text, registry, &options) {
            Some(s) => s,
            None => continue,
        };

        let px_per_layout = symbol.size_px / ONE_EM;
        let mut quads = Vec::with_capacity(shaped.glyph_count());
        for line in &shaped.lines {
            for glyph in &line.glyphs {
                quads.push(GlyphQuad {
                    codepoint: glyph.codepoint,
                    x: glyph.x * px_per_layout,
                    y: glyph.y * px_per_layout,
                });
            }
        }

        symbol.glyph_quads = quads;
    }
}

fn candidate_collision_boxes(
    candidate: &SymbolCandidate,
    projection: CameraProjection,
    anchor_mode: SymbolAnchor,
    meters_per_pixel: f64,
) -> Vec<SymbolCollisionBox> {
    let world = projection.project(&candidate.anchor);
    let effective_offset = resolve_symbol_offset(
        anchor_mode,
        candidate.offset_px,
        candidate.radial_offset,
        candidate.variable_anchor_offsets.as_deref(),
        candidate.size_px,
    );
    let [half_w_px, half_h_px] = symbol_half_extents(
        candidate.size_px,
        candidate.text.as_deref(),
        candidate.icon_image.as_deref(),
        candidate.writing_mode,
        candidate.placement,
        candidate.text_max_width,
        candidate.text_line_height,
        candidate.text_letter_spacing,
        candidate.icon_text_fit,
        candidate.icon_text_fit_padding,
        effective_offset,
        candidate.padding_px.max(0.0) as f64,
    );
    let half_w = half_w_px * meters_per_pixel;
    let half_h = half_h_px * meters_per_pixel;
    let signs = anchor_mode.offset_signs();
    let center_x = world.position.x + effective_offset[0] as f64 * meters_per_pixel + signs[0] * half_w * 2.0;
    let center_y = world.position.y + effective_offset[1] as f64 * meters_per_pixel + signs[1] * half_h * 2.0;

    segmented_collision_boxes(candidate, center_x, center_y, half_w, half_h)
}

/// Build collision boxes for a symbol candidate.
///
/// Point labels still collide as a single box. Line labels use several smaller
/// boxes along the local label axis so collision testing better matches the
/// rendered label footprint. This is still simpler than Mapbox or MapLibre's
/// full line collision geometry, but it reduces false positives from one large
/// enclosing box without changing the rest of the placement contract.
fn segmented_collision_boxes(
    candidate: &SymbolCandidate,
    center_x: f64,
    center_y: f64,
    half_w: f64,
    half_h: f64,
) -> Vec<SymbolCollisionBox> {
    if candidate.placement != SymbolPlacement::Line {
        return vec![rotated_collision_box(
            center_x,
            center_y,
            half_w,
            half_h,
            candidate.rotation_rad,
        )];
    }

    let full_width = half_w * 2.0;
    let full_height = half_h * 2.0;
    let segment_count = ((full_width / full_height.max(1.0)).ceil() as usize).clamp(1, 4);
    let segment_half_w = half_w / segment_count as f64;
    let sin_theta = candidate.rotation_rad.sin() as f64;
    let cos_theta = candidate.rotation_rad.cos() as f64;
    let mut boxes = Vec::with_capacity(segment_count);

    for index in 0..segment_count {
        let local_center_x = -half_w + segment_half_w + (index as f64 * segment_half_w * 2.0);
        let rotated_center_x = local_center_x * cos_theta;
        let rotated_center_y = local_center_x * sin_theta;
        boxes.push(rotated_collision_box(
            center_x + rotated_center_x,
            center_y + rotated_center_y,
            segment_half_w,
            half_h,
            candidate.rotation_rad,
        ));
    }

    boxes
}

/// Build an axis-aligned collision box that encloses a rotated symbol quad.
///
/// Mapbox and MapLibre eventually work with richer line-label collision
/// geometry than a single box. The engine still uses a single collision box,
/// but by enclosing the rotated quad instead of the unrotated one we keep the
/// collision approximation aligned with the current rendered orientation.
fn rotated_collision_box(
    center_x: f64,
    center_y: f64,
    half_w: f64,
    half_h: f64,
    rotation_rad: f32,
) -> SymbolCollisionBox {
    let sin_theta = rotation_rad.sin() as f64;
    let cos_theta = rotation_rad.cos() as f64;
    let mut min_x = f64::INFINITY;
    let mut min_y = f64::INFINITY;
    let mut max_x = f64::NEG_INFINITY;
    let mut max_y = f64::NEG_INFINITY;

    for [local_x, local_y] in [
        [-half_w, -half_h],
        [half_w, -half_h],
        [half_w, half_h],
        [-half_w, half_h],
    ] {
        let rotated_x = local_x * cos_theta - local_y * sin_theta;
        let rotated_y = local_x * sin_theta + local_y * cos_theta;
        let x = center_x + rotated_x;
        let y = center_y + rotated_y;
        min_x = min_x.min(x);
        min_y = min_y.min(y);
        max_x = max_x.max(x);
        max_y = max_y.max(y);
    }

    SymbolCollisionBox {
        min: [min_x, min_y],
        max: [max_x, max_y],
    }
}

fn merge_collision_boxes(boxes: &[SymbolCollisionBox]) -> SymbolCollisionBox {
    let mut min_x = f64::INFINITY;
    let mut min_y = f64::INFINITY;
    let mut max_x = f64::NEG_INFINITY;
    let mut max_y = f64::NEG_INFINITY;

    for bbox in boxes {
        min_x = min_x.min(bbox.min[0]);
        min_y = min_y.min(bbox.min[1]);
        max_x = max_x.max(bbox.max[0]);
        max_y = max_y.max(bbox.max[1]);
    }

    if boxes.is_empty() {
        SymbolCollisionBox {
            min: [0.0, 0.0],
            max: [0.0, 0.0],
        }
    } else {
        SymbolCollisionBox {
            min: [min_x, min_y],
            max: [max_x, max_y],
        }
    }
}

fn ordered_candidate_anchors(candidate: &SymbolCandidate, previous: Option<SymbolAnchor>) -> Vec<SymbolAnchor> {
    let mut anchors = candidate.anchors.clone();
    if anchors.is_empty() {
        anchors.push(SymbolAnchor::Center);
    }
    if let Some(previous) = previous {
        if let Some(index) = anchors.iter().position(|anchor| *anchor == previous) {
            anchors.swap(0, index);
        }
    }
    anchors
}

fn viewport_contains_box(
    viewport_bounds: Option<&WorldBounds>,
    bbox: &SymbolCollisionBox,
    padding_factor: f64,
) -> bool {
    let Some(bounds) = viewport_bounds else {
        return true;
    };
    let width = (bbox.max[0] - bbox.min[0]).abs() * padding_factor;
    let height = (bbox.max[1] - bbox.min[1]).abs() * padding_factor;
    !(bbox.max[0] < bounds.min.position.x - width
        || bbox.min[0] > bounds.max.position.x + width
        || bbox.max[1] < bounds.min.position.y - height
        || bbox.min[1] > bounds.max.position.y + height)
}

fn symbol_half_extents(
    size_px: f32,
    text: Option<&str>,
    icon_image: Option<&str>,
    writing_mode: SymbolWritingMode,
    placement: SymbolPlacement,
    text_max_width: Option<f32>,
    text_line_height: Option<f32>,
    text_letter_spacing: Option<f32>,
    icon_text_fit: SymbolIconTextFit,
    icon_text_fit_padding: [f32; 4],
    offset_px: [f32; 2],
    padding_px: f64,
) -> [f64; 2] {
    let size_px = size_px.max(1.0) as f64;
    let (text_width_px, text_height_px) = estimate_text_box(
        text,
        size_px,
        placement,
        text_max_width,
        text_line_height,
        text_letter_spacing,
    );
    let icon_size_px = if icon_image.is_some() { size_px * 1.2 } else { 0.0 };
    let (width_px, height_px) = match writing_mode {
        SymbolWritingMode::Horizontal => fitted_symbol_box(
            text_width_px.max(size_px),
            text_height_px.max(size_px),
            icon_image.is_some(),
            icon_size_px,
            icon_text_fit,
            icon_text_fit_padding,
            padding_px,
        ),
        SymbolWritingMode::Vertical => fitted_symbol_box(
            text_height_px.max(size_px),
            text_width_px.max(size_px),
            icon_image.is_some(),
            icon_size_px,
            icon_text_fit,
            icon_text_fit_padding,
            padding_px,
        ),
    };
    [
        (width_px + offset_px[0].abs() as f64) * 0.5,
        (height_px + offset_px[1].abs() as f64) * 0.5,
    ]
}

/// Estimate the placeholder text box used by the current simplified symbol renderer.
///
/// Mapbox and MapLibre perform full shaping and line breaking. The engine still
/// uses a lightweight character-based approximation, but honoring
/// `text-max-width` for point labels makes wrapped labels occupy a footprint
/// much closer to the eventual shaped result than always treating text as a
/// single line. `text-line-height` feeds the wrapped height estimate so the
/// style can influence multi-line placeholder spacing as well, and
/// `text-letter-spacing` expands the estimated line width so collisions react
/// to basic glyph spacing changes before full shaping exists.
fn estimate_text_box(
    text: Option<&str>,
    size_px: f64,
    placement: SymbolPlacement,
    text_max_width: Option<f32>,
    text_line_height: Option<f32>,
    text_letter_spacing: Option<f32>,
) -> (f64, f64) {
    let Some(text) = text else {
        return (0.0, 0.0);
    };

    let glyph_count = text.chars().count() as f64;
    let letter_spacing_px = text_letter_spacing.unwrap_or(0.0).max(0.0) as f64 * size_px;
    let total_width_px = glyph_count * size_px * 0.6 + (glyph_count - 1.0).max(0.0) * letter_spacing_px;
    let line_height_px = size_px * text_line_height.unwrap_or(1.2).max(0.1) as f64;

    if placement != SymbolPlacement::Point {
        return (total_width_px, line_height_px);
    }

    let Some(max_width_em) = text_max_width else {
        return (total_width_px, line_height_px);
    };
    let max_width_px = (max_width_em.max(1.0) as f64) * size_px;
    if total_width_px <= max_width_px {
        return (total_width_px, line_height_px);
    }

    let line_count = (total_width_px / max_width_px).ceil().max(1.0);
    (max_width_px, line_height_px * line_count)
}

/// Combine placeholder text and icon extents, including simplified icon-text-fit support.
///
/// Mapbox and MapLibre can stretch icons around the shaped text box when
/// `icon-text-fit` is enabled. The engine approximates that by resizing the
/// placeholder icon box around the estimated text box plus fit padding instead
/// of treating the icon as a separate side-by-side glyph.
fn fitted_symbol_box(
    text_width_px: f64,
    text_height_px: f64,
    has_icon: bool,
    icon_size_px: f64,
    icon_text_fit: SymbolIconTextFit,
    icon_text_fit_padding: [f32; 4],
    padding_px: f64,
) -> (f64, f64) {
    if !has_icon {
        return (text_width_px + padding_px * 2.0, text_height_px + padding_px * 2.0);
    }

    let icon_base_width = icon_size_px;
    let icon_base_height = icon_size_px;
    if icon_text_fit == SymbolIconTextFit::None || text_width_px <= 0.0 || text_height_px <= 0.0 {
        return (
            text_width_px + icon_base_width + padding_px * 2.0,
            text_height_px.max(icon_base_height) + padding_px * 2.0,
        );
    }

    let fit_width = match icon_text_fit {
        SymbolIconTextFit::None | SymbolIconTextFit::Height => icon_base_width,
        SymbolIconTextFit::Width | SymbolIconTextFit::Both => {
            text_width_px + icon_text_fit_padding[1] as f64 + icon_text_fit_padding[3] as f64
        }
    };
    let fit_height = match icon_text_fit {
        SymbolIconTextFit::None | SymbolIconTextFit::Width => icon_base_height,
        SymbolIconTextFit::Height | SymbolIconTextFit::Both => {
            text_height_px + icon_text_fit_padding[0] as f64 + icon_text_fit_padding[2] as f64
        }
    };

    (
        fit_width.max(text_width_px) + padding_px * 2.0,
        fit_height.max(text_height_px) + padding_px * 2.0,
    )
}

/// Resolve the effective offset for a symbol after anchor selection.
///
/// The engine treats `text-radial-offset` as an anchor-direction displacement
/// expressed in symbol-size units. When it is present it overrides the fixed
/// `text-offset` vector, matching the style-spec precedence while still using a
/// simple geometry model that does not depend on full glyph metrics. When no
/// radial offset is present, the fixed offset is resolved relative to the
/// chosen anchor so anchored labels move in the same general direction as the
/// corresponding Mapbox and MapLibre placement rules.
fn resolve_symbol_offset(
    anchor_mode: SymbolAnchor,
    offset_px: [f32; 2],
    radial_offset: Option<f32>,
    variable_anchor_offsets: Option<&[(SymbolAnchor, [f32; 2])]>,
    size_px: f32,
) -> [f32; 2] {
    if let Some(anchor_offsets) = variable_anchor_offsets {
        if let Some((_, offset)) = anchor_offsets.iter().find(|(anchor, _)| *anchor == anchor_mode) {
            return [offset[0] * size_px.max(1.0), offset[1] * size_px.max(1.0)];
        }
    }
    let Some(radial_offset) = radial_offset else {
        return resolve_anchor_relative_text_offset(anchor_mode, offset_px);
    };

    let radial_px = radial_offset.max(0.0) * size_px.max(1.0);
    let diagonal_px = radial_px / std::f32::consts::SQRT_2;
    match anchor_mode {
        SymbolAnchor::Center => [0.0, 0.0],
        SymbolAnchor::Top => [0.0, radial_px],
        SymbolAnchor::Bottom => [0.0, -radial_px],
        SymbolAnchor::Left => [radial_px, 0.0],
        SymbolAnchor::Right => [-radial_px, 0.0],
        SymbolAnchor::TopLeft => [diagonal_px, diagonal_px],
        SymbolAnchor::TopRight => [-diagonal_px, diagonal_px],
        SymbolAnchor::BottomLeft => [diagonal_px, -diagonal_px],
        SymbolAnchor::BottomRight => [-diagonal_px, -diagonal_px],
    }
}

/// Resolve a fixed text offset relative to the selected anchor.
///
/// Mapbox and MapLibre interpret `text-offset` relative to anchor direction
/// rather than as a raw free-form XY translation for non-centered anchors. The
/// engine keeps a simplified baseline-free version of that rule here: centered
/// labels retain the raw offset vector, while anchored labels use the absolute
/// offset magnitudes projected into the anchor's readable directions.
fn resolve_anchor_relative_text_offset(
    anchor_mode: SymbolAnchor,
    offset_px: [f32; 2],
) -> [f32; 2] {
    let offset_x = offset_px[0].abs();
    let offset_y = offset_px[1].abs();

    match anchor_mode {
        SymbolAnchor::Center => offset_px,
        SymbolAnchor::Top => [0.0, offset_y],
        SymbolAnchor::Bottom => [0.0, -offset_y],
        SymbolAnchor::Left => [offset_x, 0.0],
        SymbolAnchor::Right => [-offset_x, 0.0],
        SymbolAnchor::TopLeft => [offset_x, offset_y],
        SymbolAnchor::TopRight => [-offset_x, offset_y],
        SymbolAnchor::BottomLeft => [offset_x, -offset_y],
        SymbolAnchor::BottomRight => [-offset_x, -offset_y],
    }
}

fn append_symbol_quad(
    mesh: &mut crate::layers::VectorMeshData,
    symbol: &PlacedSymbol,
    projection: CameraProjection,
    half_w: f64,
    half_h: f64,
    mut color: [f32; 4],
    opacity: f32,
    meters_per_pixel: f64,
) {
    color[3] *= opacity.clamp(0.0, 1.0);
    let scale = projection.scale_factor(&symbol.anchor).max(1e-6);
    let offset_scale = 1.0 / scale;
    let signs = symbol.anchor_mode.offset_signs();
    let center_x = symbol.world_anchor[0]
        + symbol.offset_px[0] as f64 * meters_per_pixel * offset_scale
        + signs[0] * half_w * 2.0;
    let center_y = symbol.world_anchor[1]
        + symbol.offset_px[1] as f64 * meters_per_pixel * offset_scale
        + signs[1] * half_h * 2.0;
    let z = symbol.world_anchor[2];
    let sin_theta = symbol.rotation_rad.sin() as f64;
    let cos_theta = symbol.rotation_rad.cos() as f64;
    let base = mesh.positions.len() as u32;
    for [local_x, local_y] in [
        [-half_w, -half_h],
        [half_w, -half_h],
        [half_w, half_h],
        [-half_w, half_h],
    ] {
        let rotated_x = local_x * cos_theta - local_y * sin_theta;
        let rotated_y = local_x * sin_theta + local_y * cos_theta;
        mesh.positions.push([center_x + rotated_x, center_y + rotated_y, z]);
    }
    for _ in 0..4 {
        mesh.colors.push(color);
    }
    mesh.indices.extend_from_slice(&[base, base + 1, base + 2, base, base + 2, base + 3]);
}

fn cross_tile_id_for_symbol(
    text: Option<&str>,
    icon: Option<&str>,
    anchor: &GeoCoord,
    meters_per_pixel: f64,
) -> String {
    let world = CameraProjection::WebMercator.project(anchor);
    let bucket = (meters_per_pixel * 32.0).max(1.0);
    let x = (world.position.x / bucket).round() as i64;
    let y = (world.position.y / bucket).round() as i64;
    format!("{}|{}|{}|{}", text.unwrap_or(""), icon.unwrap_or(""), x, y)
}

// ---------------------------------------------------------------------------
// SDF distance transform (Felzenszwalb & Huttenlocher 2012)
// ---------------------------------------------------------------------------

/// Convert a binary alpha bitmap into an SDF bitmap with padding.
///
/// The output bitmap is `(width + 2*buffer)` × `(height + 2*buffer)` pixels.
/// Values encode the signed distance to the glyph edge: ~128 (0.5) = edge,
/// >128 = inside, <128 = outside.
fn binary_to_sdf(
    alpha: &[u8],
    width: usize,
    height: usize,
    buffer: usize,
) -> Vec<u8> {
    if width == 0 || height == 0 {
        return Vec::new();
    }
    let new_w = width + 2 * buffer;
    let new_h = height + 2 * buffer;
    let len = new_w * new_h;
    let big = (new_w * new_w + new_h * new_h) as f32;

    // Outer grid: seeds are "inside" pixels (distance 0 to nearest inside);
    // non-seeds (outside / padding) start at `big`.
    let mut outer = vec![big; len];
    // Inner grid: seeds are "outside" pixels (distance 0 to nearest outside);
    // non-seeds (inside) start at `big`.  Padding is outside → 0.
    let mut inner = vec![0.0f32; len];

    for y in 0..height {
        for x in 0..width {
            let dst = (y + buffer) * new_w + (x + buffer);
            if alpha[y * width + x] > 127 {
                outer[dst] = 0.0;
                inner[dst] = big;
            }
        }
    }

    edt_2d(&mut outer, new_w, new_h);
    edt_2d(&mut inner, new_w, new_h);

    let buf_f = buffer as f32;
    let mut sdf = vec![0u8; len];
    for i in 0..len {
        let dist = outer[i].sqrt() - inner[i].sqrt();
        let normalized = 0.5 - dist / (2.0 * buf_f);
        sdf[i] = (normalized.clamp(0.0, 1.0) * 255.0) as u8;
    }
    sdf
}

/// 2D squared-Euclidean distance transform (separable row + column passes).
fn edt_2d(grid: &mut [f32], width: usize, height: usize) {
    for y in 0..height {
        let offset = y * width;
        edt_1d(&mut grid[offset..offset + width]);
    }
    let mut col = vec![0.0f32; height];
    for x in 0..width {
        for y in 0..height {
            col[y] = grid[y * width + x];
        }
        edt_1d(&mut col);
        for y in 0..height {
            grid[y * width + x] = col[y];
        }
    }
}

/// 1D squared-Euclidean distance transform (Felzenszwalb & Huttenlocher).
///
/// Overwrites `f` in-place: seeds have `f[i] == 0.0`, non-seeds start at a
/// large value.  On output `f[i]` is the **squared** distance to the nearest
/// seed.
fn edt_1d(f: &mut [f32]) {
    let n = f.len();
    if n <= 1 {
        return;
    }
    let mut v = vec![0usize; n]; // Locations of parabolas in the lower envelope.
    let mut z = vec![0.0f32; n + 1]; // Range boundaries.
    let mut d = vec![0.0f32; n]; // Output.

    z[0] = f32::NEG_INFINITY;
    z[1] = f32::INFINITY;
    let mut k: usize = 0;

    for q in 1..n {
        let q2 = (q * q) as f32;
        loop {
            let vk = v[k];
            let vk2 = (vk * vk) as f32;
            let s = ((f[q] + q2) - (f[vk] + vk2)) / (2.0 * (q - vk) as f32);
            if s > z[k] {
                k += 1;
                v[k] = q;
                z[k] = s;
                z[k + 1] = f32::INFINITY;
                break;
            }
            // Safe: z[0] = −∞ guarantees s > z[0] for any finite s.
            k -= 1;
        }
    }

    k = 0;
    for q in 0..n {
        while z[k + 1] < q as f32 {
            k += 1;
        }
        let dq = q as f32 - v[k] as f32;
        d[q] = dq * dq + f[v[k]];
    }
    f.copy_from_slice(&d);
}

fn blit_alpha(
    atlas: &mut [u8],
    atlas_width: usize,
    origin: [u16; 2],
    width: usize,
    height: usize,
    src: &[u8],
) {
    for row in 0..height {
        let dst_start = (origin[1] as usize + row) * atlas_width + origin[0] as usize;
        let src_start = row * width;
        atlas[dst_start..dst_start + width].copy_from_slice(&src[src_start..src_start + width]);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::camera_projection::CameraProjection;
    use rustial_math::GeoCoord;

    fn candidate(id: &str, lon: f64, text: &str) -> SymbolCandidate {
        SymbolCandidate {
            id: id.into(),
            layer_id: Some("symbols".into()),
            source_id: Some("source".into()),
            source_layer: Some("poi".into()),
            source_tile: None,
            feature_id: id.into(),
            feature_index: 0,
            placement_group_id: id.into(),
            placement: SymbolPlacement::Point,
            anchor: GeoCoord::from_lat_lon(0.0, lon),
            text: Some(text.into()),
            icon_image: None,
            font_stack: "Test Sans".into(),
            cross_tile_id: id.into(),
            rotation_rad: 0.0,
            size_px: 16.0,
            padding_px: 2.0,
            allow_overlap: false,
            ignore_placement: false,
            sort_key: None,
            radial_offset: None,
            variable_anchor_offsets: None,
            text_max_width: None,
            text_line_height: None,
            text_letter_spacing: None,
            icon_text_fit: SymbolIconTextFit::None,
            icon_text_fit_padding: [0.0, 0.0, 0.0, 0.0],
            anchors: vec![SymbolAnchor::Center],
            writing_mode: SymbolWritingMode::Horizontal,
            offset_px: [0.0, 0.0],
            fill_color: [1.0, 1.0, 1.0, 1.0],
            halo_color: [0.0, 0.0, 0.0, 1.0],
        }
    }

    #[test]
    fn glyph_atlas_tracks_unique_glyphs() {
        let mut atlas = GlyphAtlas::new();
        atlas.request_text("Test Sans", "aba");
        assert_eq!(atlas.len(), 2);
        atlas.load_requested(&ProceduralGlyphProvider::new());
        assert_eq!(atlas.entries().count(), 2);
        assert!(atlas.dimensions()[0] > 0);
    }

    #[test]
    fn image_manager_tracks_referenced_ids() {
        let mut images = ImageManager::new();
        images.register_image(SpriteImage::new("marker", [32, 32]));
        images.request("marker");
        assert!(images.contains("marker"));
        assert_eq!(images.referenced().collect::<Vec<_>>(), vec!["marker"]);
    }

    #[test]
    fn placement_filters_colliding_symbols() {
        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(&[candidate("a", 0.0, "Alpha"), candidate("b", 0.00001, "Beta")], CameraProjection::WebMercator, 2.0, 1.0 / 60.0, None);
        assert_eq!(placed.iter().filter(|symbol| symbol.visible).count(), 1);
    }

    #[test]
    fn placement_dedupes_nearby_repeated_labels() {
        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(&[candidate("a", 0.0, "Same"), candidate("b", 0.0, "Same")], CameraProjection::WebMercator, 2.0, 1.0 / 60.0, None);
        assert_eq!(placed.len(), 1);
    }

    #[test]
    fn placement_tries_alternate_anchors() {
        let mut a = candidate("a", 0.0, "Alpha");
        let mut b = candidate("b", 0.0, "Beta");
        a.anchors = vec![SymbolAnchor::Center];
        b.anchors = vec![SymbolAnchor::Center, SymbolAnchor::Top];

        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(&[a, b], CameraProjection::WebMercator, 2.0, 1.0, None);
        assert_eq!(placed.iter().filter(|symbol| symbol.visible).count(), 2);
        assert_eq!(placed[1].anchor_mode, SymbolAnchor::Top);
    }

    #[test]
    fn placement_preserves_previous_anchor_by_cross_tile_id() {
        let mut first = candidate("a", 0.0, "Alpha");
        first.cross_tile_id = "shared".into();
        first.anchors = vec![SymbolAnchor::Center, SymbolAnchor::Top];

        let mut blocker = candidate("blocker", 0.0, "Block");
        blocker.anchors = vec![SymbolAnchor::Center];

        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(&[blocker.clone(), first.clone()], CameraProjection::WebMercator, 2.0, 1.0, None);
        assert_eq!(placed[1].anchor_mode, SymbolAnchor::Top);

        let mut second = candidate("b", 0.0, "Alpha");
        second.cross_tile_id = "shared".into();
        second.anchors = vec![SymbolAnchor::Center, SymbolAnchor::Top];
        let placed = engine.place_candidates(&[blocker, second], CameraProjection::WebMercator, 2.0, 1.0 / 60.0, None);
        assert_eq!(placed[1].anchor_mode, SymbolAnchor::Top);
    }

    #[test]
    fn placement_honors_symbol_sort_key_order() {
        let mut low = candidate("low", 0.0, "Low");
        low.sort_key = Some(0.0);

        let mut high = candidate("high", 0.0, "High");
        high.sort_key = Some(10.0);

        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(
            &[high, low],
            CameraProjection::WebMercator,
            2.0,
            1.0,
            None,
        );

        assert_eq!(placed.iter().filter(|symbol| symbol.visible).count(), 1);
        assert_eq!(placed.iter().find(|symbol| symbol.visible).map(|symbol| symbol.id.as_str()), Some("low"));
    }

    #[test]
    fn fixed_offset_is_resolved_relative_to_anchor_direction() {
        assert_eq!(
            resolve_symbol_offset(SymbolAnchor::TopRight, [3.0, 4.0], None, None, 10.0),
            [-3.0, 4.0]
        );
        assert_eq!(
            resolve_symbol_offset(SymbolAnchor::BottomLeft, [3.0, 4.0], None, None, 10.0),
            [3.0, -4.0]
        );
    }

    #[test]
    fn centered_fixed_offset_preserves_raw_vector() {
        assert_eq!(
            resolve_symbol_offset(SymbolAnchor::Center, [3.0, -4.0], None, None, 10.0),
            [3.0, -4.0]
        );
    }

    #[test]
    fn radial_offset_overrides_fixed_offset_for_anchor_direction() {
        let resolved = resolve_symbol_offset(
            SymbolAnchor::TopRight,
            [99.0, 99.0],
            Some(2.0),
            None,
            10.0,
        );

        assert!(resolved[0] < 0.0);
        assert!(resolved[1] > 0.0);
        assert!(resolved[0].abs() < 99.0);
        assert!(resolved[1].abs() < 99.0);
    }

    #[test]
    fn variable_anchor_offset_overrides_radial_and_fixed_offsets() {
        let resolved = resolve_symbol_offset(
            SymbolAnchor::Top,
            [99.0, 99.0],
            Some(5.0),
            Some(&[(SymbolAnchor::Top, [1.0, 2.0])]),
            10.0,
        );

        assert_eq!(resolved, [10.0, 20.0]);
    }

    #[test]
    fn point_text_max_width_wraps_placeholder_text_box() {
        let single_line = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Point,
            None,
            None,
            None,
        );
        let wrapped = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Point,
            Some(3.0),
            None,
            None,
        );

        assert!(wrapped.0 < single_line.0);
        assert!(wrapped.1 > single_line.1);
    }

    #[test]
    fn line_text_max_width_does_not_wrap_placeholder_text_box() {
        let unbounded = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Line,
            None,
            None,
            None,
        );
        let bounded = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Line,
            Some(3.0),
            None,
            None,
        );

        assert_eq!(bounded, unbounded);
    }

    #[test]
    fn wrapped_text_box_uses_text_line_height() {
        let compact = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Point,
            Some(3.0),
            Some(1.0),
            None,
        );
        let spacious = estimate_text_box(
            Some("abcdefghij"),
            10.0,
            SymbolPlacement::Point,
            Some(3.0),
            Some(2.0),
            None,
        );

        assert_eq!(compact.0, spacious.0);
        assert!(spacious.1 > compact.1);
    }

    #[test]
    fn text_letter_spacing_expands_placeholder_text_box_width() {
        let compact = estimate_text_box(
            Some("abcde"),
            10.0,
            SymbolPlacement::Point,
            None,
            None,
            None,
        );
        let spaced = estimate_text_box(
            Some("abcde"),
            10.0,
            SymbolPlacement::Point,
            None,
            None,
            Some(0.25),
        );

        assert!(spaced.0 > compact.0);
        assert_eq!(spaced.1, compact.1);
    }

    #[test]
    fn icon_text_fit_both_wraps_icon_around_text_box() {
        let fitted = symbol_half_extents(
            10.0,
            Some("abcdefghij"),
            Some("marker"),
            SymbolWritingMode::Horizontal,
            SymbolPlacement::Point,
            Some(3.0),
            Some(1.5),
            Some(0.25),
            SymbolIconTextFit::Both,
            [1.0, 2.0, 3.0, 4.0],
            [0.0, 0.0],
            0.0,
        );
        let unfitted = symbol_half_extents(
            10.0,
            Some("abcdefghij"),
            Some("marker"),
            SymbolWritingMode::Horizontal,
            SymbolPlacement::Point,
            Some(3.0),
            Some(1.5),
            Some(0.25),
            SymbolIconTextFit::None,
            [0.0, 0.0, 0.0, 0.0],
            [0.0, 0.0],
            0.0,
        );

        assert!(fitted[0] < unfitted[0]);
        assert!(fitted[1] > unfitted[1]);
    }

    #[test]
    fn icon_text_fit_width_only_keeps_base_height() {
        let fitted = fitted_symbol_box(
            40.0,
            18.0,
            true,
            12.0,
            SymbolIconTextFit::Width,
            [2.0, 3.0, 4.0, 5.0],
            0.0,
        );

        assert_eq!(fitted.1, 18.0);
        assert_eq!(fitted.0, 48.0);
    }

    #[test]
    fn placement_ignored_symbol_does_not_block_later_symbol() {
        let mut first = candidate("first", 0.0, "Alpha");
        first.ignore_placement = true;

        let second = candidate("second", 0.0, "Beta");

        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(
            &[first, second],
            CameraProjection::WebMercator,
            2.0,
            1.0,
            None,
        );

        assert_eq!(placed.iter().filter(|symbol| symbol.visible).count(), 2);
    }

    #[test]
    fn asset_registry_rebuilds_from_visible_symbols() {
        let mut registry = SymbolAssetRegistry::new();
        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(
            &[SymbolCandidate {
                id: "icon".into(),
                layer_id: Some("symbols".into()),
                source_id: Some("source".into()),
                source_layer: Some("poi".into()),
                source_tile: None,
                feature_id: "icon".into(),
                feature_index: 0,
                placement_group_id: "icon".into(),
                placement: SymbolPlacement::Point,
                anchor: GeoCoord::from_lat_lon(0.0, 0.0),
                text: Some("Hi".into()),
                icon_image: Some("marker".into()),
                font_stack: "Test Sans".into(),
                cross_tile_id: "icon".into(),
                rotation_rad: 0.0,
                size_px: 14.0,
                padding_px: 0.0,
                allow_overlap: true,
                ignore_placement: false,
                sort_key: None,
                radial_offset: None,
                variable_anchor_offsets: None,
                text_max_width: None,
                text_line_height: None,
                text_letter_spacing: None,
                icon_text_fit: SymbolIconTextFit::None,
                icon_text_fit_padding: [0.0, 0.0, 0.0, 0.0],
                anchors: vec![SymbolAnchor::Center],
                writing_mode: SymbolWritingMode::Horizontal,
                offset_px: [0.0, 0.0],
                fill_color: [1.0, 1.0, 1.0, 1.0],
                halo_color: [0.0, 0.0, 0.0, 1.0],
             }],
             CameraProjection::WebMercator,
              1.0,
              0.5,
             None,
         );
         registry.rebuild_from_symbols(&placed);
         assert!(registry.glyphs().len() >= 2);
         assert_eq!(registry.images().referenced().collect::<Vec<_>>(), vec!["marker"]);
     }

    #[test]
    fn placed_symbols_generate_render_mesh() {
        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(&[candidate("a", 0.0, "Alpha")], CameraProjection::WebMercator, 1.0, 1.0, None);
        let mesh = symbol_mesh_from_placed_symbols(&placed, CameraProjection::WebMercator, 1.0);
        assert_eq!(mesh.vertex_count(), 8);
        assert_eq!(mesh.index_count(), 12);
    }

    #[test]
    fn rotated_collision_box_expands_for_diagonal_symbols() {
        let bbox = rotated_collision_box(0.0, 0.0, 10.0, 2.0, std::f32::consts::FRAC_PI_4);
        // A 20x4 box rotated 45 deg produces an AABB of ~17x17.  The height
        // should expand well beyond the unrotated 4.0 (2 * half_h), and
        // both AABB axes should be wider than the minimum dimension.
        let width = bbox.max[0] - bbox.min[0];
        let height = bbox.max[1] - bbox.min[1];
        assert!(width > 4.0, "rotated AABB width {width} should exceed the unrotated height");
        assert!(height > 4.0, "rotated AABB height {height} should exceed the unrotated height");
        // Verify the AABB is roughly square for a 45-degree rotation.
        assert!((width - height).abs() < 1.0, "45 deg rotation should produce a near-square AABB");
    }

    #[test]
    fn line_candidates_use_multiple_collision_boxes() {
        let mut line = candidate("line", 0.0, "Long river label");
        line.placement = SymbolPlacement::Line;
        line.rotation_rad = std::f32::consts::FRAC_PI_4;

        let boxes = candidate_collision_boxes(&line, CameraProjection::WebMercator, SymbolAnchor::Center, 2.0);
        assert!(boxes.len() > 1);
    }

    #[test]
    fn rotated_line_candidates_can_coexist_when_segment_boxes_no_longer_overlap() {
        let mut a = candidate("a", 0.0, "Alpha");
        a.placement = SymbolPlacement::Line;
        a.rotation_rad = std::f32::consts::FRAC_PI_2;

        let mut b = candidate("b", 0.0005, "Beta");
        b.placement = SymbolPlacement::Line;
        b.rotation_rad = std::f32::consts::FRAC_PI_2;

        let mut engine = SymbolPlacementEngine::new();
        let placed = engine.place_candidates(
            &[a, b],
            CameraProjection::WebMercator,
            2.0,
            1.0,
            None,
        );
        assert_eq!(placed.iter().filter(|symbol| symbol.visible).count(), 2);
    }

    #[test]
    fn equirectangular_symbol_anchor_differs_from_mercator() {
        let mut engine = SymbolPlacementEngine::new();
        let mut merc_candidate = candidate("a", 10.0, "Alpha");
        merc_candidate.anchor = GeoCoord::from_lat_lon(45.0, 10.0);
        let mut eq_candidate = candidate("b", 10.0, "Alpha");
        eq_candidate.anchor = GeoCoord::from_lat_lon(45.0, 10.0);
        let merc = engine.place_candidates(&[merc_candidate], CameraProjection::WebMercator, 1.0, 1.0, None);
        let eq = engine.place_candidates(&[eq_candidate], CameraProjection::Equirectangular, 1.0, 1.0, None);
        assert_eq!(merc.len(), 1);
        assert_eq!(eq.len(), 1);
        assert!((merc[0].world_anchor[1] - eq[0].world_anchor[1]).abs() > 1.0);
    }

    // -- SDF distance transform tests -------------------------------------

    #[test]
    fn sdf_single_pixel_inside_produces_centered_gradient() {
        // 1x1 fully-inside bitmap: the center of the padded SDF should be
        // bright (inside), edges should taper toward 128 (the edge value).
        let alpha = vec![255u8];
        let sdf = binary_to_sdf(&alpha, 1, 1, 3);
        let w = 1 + 2 * 3; // 7
        assert_eq!(sdf.len(), w * w);
        // Center pixel (3, 3): should be above 128 (inside).
        let center = sdf[3 * w + 3];
        assert!(center > 140, "center SDF value {center} should be inside (>140)");
        // Corner pixel (0, 0): should be well below 128 (outside).
        let corner = sdf[0];
        assert!(corner < 100, "corner SDF value {corner} should be outside (<100)");
    }

    #[test]
    fn sdf_empty_bitmap_is_all_outside() {
        // All-zero bitmap: everywhere is "outside" → values below 128.
        let alpha = vec![0u8; 4];
        let sdf = binary_to_sdf(&alpha, 2, 2, 2);
        for &v in &sdf {
            assert!(v <= 128, "SDF value {v} should be ≤128 for all-outside");
        }
    }

    #[test]
    fn sdf_full_bitmap_is_all_inside() {
        // All-255 bitmap: everywhere is "inside" → values above 128.
        let alpha = vec![255u8; 4];
        let sdf = binary_to_sdf(&alpha, 2, 2, 2);
        let w = 2 + 2 * 2;
        // Interior of the original bitmap region should be solidly inside.
        let interior = sdf[(2) * w + (2)]; // top-left of the original region
        assert!(interior > 128, "SDF interior {interior} should be >128");
    }

    #[test]
    fn sdf_adds_padding_to_dimensions() {
        let alpha = vec![255u8; 6]; // 3x2
        let sdf = binary_to_sdf(&alpha, 3, 2, 3);
        assert_eq!(sdf.len(), (3 + 6) * (2 + 6)); // 9 * 8 = 72
    }

    #[test]
    fn sdf_zero_size_returns_empty() {
        assert!(binary_to_sdf(&[], 0, 0, 3).is_empty());
    }

    #[test]
    fn glyph_atlas_sdf_entries_include_padding() {
        // When the atlas loads glyphs with SDF, each entry should be wider
        // than the raw procedural bitmap (8 + 2*3 = 14 wide).
        let mut atlas = GlyphAtlas::new();
        atlas.request_text("Test Sans", "A");
        atlas.load_requested(&ProceduralGlyphProvider::new());
        let entry = atlas.get("Test Sans", 'A').expect("glyph A");
        // Procedural glyphs are 8x12; with SDF_BUFFER=3 padding → 14x18.
        assert_eq!(entry.size[0], 8 + 2 * SDF_BUFFER);
        assert_eq!(entry.size[1], 12 + 2 * SDF_BUFFER);
    }

    #[test]
    fn glyph_atlas_sdf_alpha_contains_gradient_values() {
        // SDF atlas alpha should contain intermediate values (not just 0/255).
        let mut atlas = GlyphAtlas::new();
        atlas.request_text("Test Sans", "X");
        atlas.load_requested(&ProceduralGlyphProvider::new());
        let has_intermediate = atlas.alpha().iter().any(|&v| v > 10 && v < 245);
        assert!(has_intermediate, "SDF atlas should contain gradient values between 0 and 255");
    }

    #[test]
    fn glyph_atlas_render_em_px_from_procedural() {
        let mut atlas = GlyphAtlas::new();
        atlas.request_text("Test Sans", "A");
        atlas.load_requested(&ProceduralGlyphProvider::new());
        assert_eq!(atlas.render_em_px(), 12.0);
    }

    #[test]
    fn edt_1d_seeds_remain_zero() {
        let mut f = vec![0.0, 1e10, 1e10, 0.0, 1e10];
        edt_1d(&mut f);
        assert_eq!(f[0], 0.0);
        assert_eq!(f[3], 0.0);
        assert!(f[1] > 0.0);
        assert!(f[2] > 0.0);
    }

    #[test]
    fn edt_1d_distances_increase_from_seed() {
        let mut f = vec![0.0, 1e10, 1e10, 1e10, 1e10];
        edt_1d(&mut f);
        // Squared distances: 0, 1, 4, 9, 16
        assert!((f[0] - 0.0).abs() < 0.01);
        assert!((f[1] - 1.0).abs() < 0.01);
        assert!((f[2] - 4.0).abs() < 0.01);
        assert!((f[3] - 9.0).abs() < 0.01);
        assert!((f[4] - 16.0).abs() < 0.01);
    }
}