diff options
Diffstat (limited to 'src/smart_positioning.rs')
| -rw-r--r-- | src/smart_positioning.rs | 85 |
1 files changed, 56 insertions, 29 deletions
diff --git a/src/smart_positioning.rs b/src/smart_positioning.rs index 77fd1b6..81a2c3d 100644 --- a/src/smart_positioning.rs +++ b/src/smart_positioning.rs @@ -1,5 +1,7 @@ -use crate::geometry::{Line, Rect}; +use crate::geometry::{Line, Rect, SpatialGrid}; use crate::utils::percent_to_pixel; + +use cairo::{Context, Error}; use wmap_parser::{Component, Map}; #[derive(Debug, Clone)] @@ -8,23 +10,30 @@ pub struct LabelPosition { pub y: f64, } -/// Calculate the optimal position for a vertex label with pre-cached collision data +#[derive(Debug, Clone)] +pub struct PositioningDimensions { + pub map_size: (f64, f64), + pub vertex_size: f64, + pub font_size: f64, +} + +/// Calculate the optimal position for a vertex label with pre-cached collision data and spatial grid pub fn calculate_optimal_label_position_cached( component: &Component, - map_width: f64, - map_height: f64, - vertex_size: f64, - ctx: &cairo::Context, - font_size: f64, + dimensions: &PositioningDimensions, + context: &Context, all_lines: &[Line], + spatial_grid: &SpatialGrid, note_rects: &[Rect], -) -> Result<LabelPosition, cairo::Error> { +) -> Result<LabelPosition, Error> { + let map_width = dimensions.map_size.0; + let map_height = dimensions.map_size.1; let vertex_pixel_x = percent_to_pixel(component.coordinates.0, map_width); let vertex_pixel_y = percent_to_pixel(component.coordinates.1, map_height); // Calculate label size - ctx.set_font_size(font_size); - let extents = ctx.text_extents(&component.label)?; + context.set_font_size(dimensions.font_size); + let extents = context.text_extents(&component.label)?; let label_width = extents.width() + 4.0; let label_height = extents.height() + 2.0; @@ -32,7 +41,7 @@ pub fn calculate_optimal_label_position_cached( let candidates = generate_candidate_positions( vertex_pixel_x, vertex_pixel_y, - vertex_size, + dimensions.vertex_size, label_width, label_height, ); @@ -46,7 +55,7 @@ pub fn calculate_optimal_label_position_cached( label_height, ); - if count_line_collisions(&default_rect, all_lines) == 0 + if count_line_collisions_with_grid(&default_rect, all_lines, spatial_grid) == 0 && count_note_collisions(&default_rect, note_rects) == 0 { return Ok(default_position.clone()); @@ -59,14 +68,14 @@ pub fn calculate_optimal_label_position_cached( for (index, position) in candidates.iter().enumerate() { let label_rect = Rect::new(position.x, position.y, label_width, label_height); - let collision_count = count_line_collisions(&label_rect, all_lines); + let collision_count = count_line_collisions_with_grid(&label_rect, all_lines, spatial_grid); let note_collision_count = count_note_collisions(&label_rect, note_rects); // Distance from label center to vertex center let label_center_x = position.x + label_width / 2.0; let label_center_y = position.y + label_height / 2.0; - let vertex_center_x = vertex_pixel_x + vertex_size / 2.0; - let vertex_center_y = vertex_pixel_y + vertex_size / 2.0; + let vertex_center_x = vertex_pixel_x + dimensions.vertex_size / 2.0; + let vertex_center_y = vertex_pixel_y + dimensions.vertex_size / 2.0; let distance = ((label_center_x - vertex_center_x).powi(2) + (label_center_y - vertex_center_y).powi(2)) .sqrt(); @@ -76,7 +85,7 @@ pub fn calculate_optimal_label_position_cached( &label_rect, vertex_pixel_x, vertex_pixel_y, - vertex_size, + dimensions.vertex_size, ); // Score: collisions * 100 + note_collisions * 500 + distance * 0.5 + index * 0.1 + ownership @@ -95,7 +104,6 @@ pub fn calculate_optimal_label_position_cached( Ok(best_position) } - /// Generate 8 candidate positions around a vertex fn generate_candidate_positions( vertex_x: f64, @@ -156,7 +164,7 @@ pub fn collect_all_lines( map_width: f64, map_height: f64, vertex_size: f64, - component_map: &std::collections::HashMap<String, (f64, f64)>, + component_map: &rustc_hash::FxHashMap<String, (f64, f64)>, ) -> Vec<Line> { let mut lines = Vec::new(); @@ -216,24 +224,38 @@ pub fn collect_all_lines( lines } +/// Build a spatial grid from a collection of lines for fast collision detection +pub fn build_spatial_grid(lines: &[Line], map_width: f64, map_height: f64) -> SpatialGrid { + // Use a cell size that balances grid overhead with query efficiency + // For typical maps, 100x100 pixel cells work well + let cell_size = 100.0; + let mut grid = SpatialGrid::new(map_width, map_height, cell_size); + + for (idx, line) in lines.iter().enumerate() { + grid.insert_line(idx, line); + } + + grid +} + /// Collect rectangles for all notes pub fn collect_note_rects( map: &Map, map_width: f64, map_height: f64, - ctx: &cairo::Context, + context: &Context, font_size: f64, -) -> Result<Vec<Rect>, cairo::Error> { +) -> Result<Vec<Rect>, Error> { let mut rects = Vec::new(); - ctx.set_font_size(font_size); + context.set_font_size(font_size); for note in &map.notes { let x = percent_to_pixel(note.coordinates.0, map_width); let y = percent_to_pixel(note.coordinates.1, map_height); // Calculate note size (simplified - just use text extents) - let extents = ctx.text_extents(¬e.text)?; + let extents = context.text_extents(¬e.text)?; let width = extents.width() + 10.0; // padding let height = extents.height() + 10.0; // padding @@ -243,11 +265,15 @@ pub fn collect_note_rects( Ok(rects) } -/// Count how many lines intersect with a label rectangle -fn count_line_collisions(label_rect: &Rect, lines: &[Line]) -> usize { - lines - .iter() - .filter(|line| crate::geometry::line_intersects_rect(line, label_rect)) +/// Count how many lines intersect with a label rectangle using spatial grid +fn count_line_collisions_with_grid( + label_rect: &Rect, + lines: &[Line], + spatial_grid: &SpatialGrid, +) -> usize { + spatial_grid + .query_rect(label_rect) + .filter(|&idx| crate::geometry::line_intersects_rect(&lines[idx], label_rect)) .count() } @@ -272,8 +298,9 @@ fn calculate_ownership_penalty_fast( let vertex_center_x = vertex_x + vertex_size / 2.0; let vertex_center_y = vertex_y + vertex_size / 2.0; - let distance = - ((label_center_x - vertex_center_x).powi(2) + (label_center_y - vertex_center_y).powi(2)).sqrt(); + let distance = ((label_center_x - vertex_center_x).powi(2) + + (label_center_y - vertex_center_y).powi(2)) + .sqrt(); // Apply penalty if label is too far from its vertex if distance > 100.0 { |