agent_image_diff/

merge.rs

use crate::region::{BoundingBox, Region};

/// Merge regions whose bounding boxes are within `max_gap` pixels of each other.
///
/// Uses greedy iterative merging. O(n²) per pass on region count,
/// repeated until stable. Region count is typically small (<100) so this is fast.
pub fn merge_regions(regions: &mut Vec<Region>, max_gap: u32) {
    if max_gap == 0 || regions.len() < 2 {
        return;
    }

    let mut merged = true;
    while merged {
        merged = false;
        let mut i = 0;
        while i < regions.len() {
            let mut j = i + 1;
            while j < regions.len() {
                if bbox_gap(&regions[i].bounding_box, &regions[j].bounding_box) <= max_gap {
                    // Merge j into i
                    let removed = regions.remove(j);
                    let target = &mut regions[i];
                    let new_bbox = bbox_union(&target.bounding_box, &removed.bounding_box);
                    let total_px = target.pixel_count + removed.pixel_count;
                    target.avg_delta = (target.avg_delta * target.pixel_count as f64
                        + removed.avg_delta * removed.pixel_count as f64)
                        / total_px as f64;
                    target.max_delta = target.max_delta.max(removed.max_delta);
                    target.pixel_count = total_px;
                    target.bounding_box = new_bbox;
                    target.component_ids.extend(removed.component_ids);
                    merged = true;
                    // Don't increment j — next element shifted into position
                } else {
                    j += 1;
                }
            }
            i += 1;
        }
    }

    // Re-sort by pixel count descending and re-assign IDs
    regions.sort_by(|a, b| b.pixel_count.cmp(&a.pixel_count));
    for (i, region) in regions.iter_mut().enumerate() {
        region.id = (i + 1) as u32;
    }
}

/// Compute the minimum gap (in pixels) between two bounding boxes.
/// Returns 0 if they overlap or touch.
fn bbox_gap(a: &BoundingBox, b: &BoundingBox) -> u32 {
    let a_right = a.x + a.width;
    let a_bottom = a.y + a.height;
    let b_right = b.x + b.width;
    let b_bottom = b.y + b.height;

    let gap_x = if a_right <= b.x {
        b.x - a_right
    } else if b_right <= a.x {
        a.x - b_right
    } else {
        0
    };

    let gap_y = if a_bottom <= b.y {
        b.y - a_bottom
    } else if b_bottom <= a.y {
        a.y - b_bottom
    } else {
        0
    };

    // Chebyshev distance between closest edges
    gap_x.max(gap_y)
}

/// Compute the union (smallest enclosing) bounding box of two bounding boxes.
fn bbox_union(a: &BoundingBox, b: &BoundingBox) -> BoundingBox {
    let x = a.x.min(b.x);
    let y = a.y.min(b.y);
    let right = (a.x + a.width).max(b.x + b.width);
    let bottom = (a.y + a.height).max(b.y + b.height);
    BoundingBox {
        x,
        y,
        width: right - x,
        height: bottom - y,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn make_region(id: u32, x: u32, y: u32, w: u32, h: u32, px: u32) -> Region {
        Region {
            id,
            bounding_box: BoundingBox {
                x,
                y,
                width: w,
                height: h,
            },
            pixel_count: px,
            avg_delta: 0.5,
            max_delta: 0.8,
            label: String::new(),
            component_ids: vec![id],
        }
    }

    #[test]
    fn no_merge_when_disabled() {
        let mut regions = vec![
            make_region(1, 0, 0, 10, 10, 100),
            make_region(2, 15, 0, 10, 10, 50),
        ];
        merge_regions(&mut regions, 0);
        assert_eq!(regions.len(), 2);
    }

    #[test]
    fn nearby_regions_merge() {
        let mut regions = vec![
            make_region(1, 0, 0, 10, 10, 100),
            make_region(2, 15, 0, 10, 10, 50),
        ];
        merge_regions(&mut regions, 10);
        assert_eq!(regions.len(), 1);
        assert_eq!(regions[0].bounding_box.x, 0);
        assert_eq!(regions[0].bounding_box.width, 25);
        assert_eq!(regions[0].pixel_count, 150);
    }

    #[test]
    fn distant_regions_stay_separate() {
        let mut regions = vec![
            make_region(1, 0, 0, 10, 10, 100),
            make_region(2, 100, 100, 10, 10, 50),
        ];
        merge_regions(&mut regions, 20);
        assert_eq!(regions.len(), 2);
    }

    #[test]
    fn overlapping_regions_merge() {
        let mut regions = vec![
            make_region(1, 0, 0, 20, 20, 200),
            make_region(2, 10, 10, 20, 20, 100),
        ];
        merge_regions(&mut regions, 1);
        assert_eq!(regions.len(), 1);
        assert_eq!(regions[0].bounding_box.x, 0);
        assert_eq!(regions[0].bounding_box.y, 0);
        assert_eq!(regions[0].bounding_box.width, 30);
        assert_eq!(regions[0].bounding_box.height, 30);
    }

    #[test]
    fn chain_merge() {
        // Three regions in a line, each within distance of the next
        // A -- B -- C should all merge into one
        let mut regions = vec![
            make_region(1, 0, 0, 10, 10, 50),
            make_region(2, 15, 0, 10, 10, 50),
            make_region(3, 30, 0, 10, 10, 50),
        ];
        merge_regions(&mut regions, 10);
        assert_eq!(regions.len(), 1);
        assert_eq!(regions[0].pixel_count, 150);
    }
}