Floodfill algorithm for area with seed point

March 3, 2022

I have array of small areas defined by start xy and ending xy points, And i have seed xy point which lies somewhere in that area collectively. so my goal is to find all the areas which are linked to seed point. so any idea how to do it, i know for images we have floodfill algo in which we look for pixel color in all four directions. so is it possible something can be done for areas.

my js code

let cblock = [
    // 3307 and 3306 touching
    {name: "#left_p3307", xs: 88.29, ys: 219.4, xe: 90.84, ye: 223.94},
    {name: "#p3306", xs: 87.87, ys: 219.83, xe: 91.27, ye: 223.51},
    // 3305 touch with 3307 and 3306
    {name: "#p3305", xs: 90.42, ys: 223.09, xe: 91.27, ye: 223.94},
    // 3304 touch with 3307 and 3306
    {name: "#p3304", xs: 90.42, ys: 219.4, xe: 91.27, ye: 220.25},
    // 3303 touch with 3307 and 3306
    {name: "#p3303", xs: 87.86, ys: 219.4, xe: 88.71, ye: 220.25},
    // 3302 touch with 3307 and 3306
    {name: "#p3302", xs: 87.86, ys: 223.09, xe: 88.71, ye: 223.94},
    // center no touch with any coordinates
    {name: "#center", xs: 93.68, ys: 221.1, xe: 95.09, ye: 222.24},
    
    {name: "#right_p3301", xs: 97.93, ys: 219.4, xe: 100.48, ye: 223.94},
    {name: "#p3300", xs: 97.5, ys: 219.83, xe: 100.91, ye: 223.51},
    {name: "#p3299", xs: 100.05, ys: 223.09, xe: 100.91, ye: 223.94},
    {name: "#p3298", xs: 100.05, ys: 219.4, xe: 100.91, ye: 220.25},
    {name: "#p3297", xs: 97.5, ys: 219.4, xe: 98.35, ye: 220.25},
    {name: "#p3296", xs: 97.5, ys: 223.09, xe: 98.35, ye: 223.94}
];


// seed xy
let seed_x = 90;
let seed_y = 222;

// possible 4 direction
let dx = [0, -1, +1, 0];
let dy = [-1, 0, 0, +1];

let storage = [];

// loop on coordinates
for (let i in cblock) {
    
    let cord = cblock[i];
    // check if touching seed point
    if( (seed_x >= cord.xs && seed_x <= cord.xe) && (seed_y >= cord.ys && seed_y <= cord.ye) ){
        storage.push(cord);
    }
    
    //console.log(cblock[i]);
} 

// output points touching seed
console.log(storage);

so with xy seeds like [90,222] i should have coordinates of range #p3302 to #left_p3307 like

storage = [
    {name: "#left_p3307", xs: 88.29, ys: 219.4, xe: 90.84, ye: 223.94},
    {name: "#p3306", xs: 87.87, ys: 219.83, xe: 91.27, ye: 223.51},
    {name: "#p3305", xs: 90.42, ys: 223.09, xe: 91.27, ye: 223.94},
    {name: "#p3304", xs: 90.42, ys: 219.4, xe: 91.27, ye: 220.25},
    {name: "#p3303", xs: 87.86, ys: 219.4, xe: 88.71, ye: 220.25},
    {name: "#p3302", xs: 87.86, ys: 223.09, xe: 88.71, ye: 223.94}
];

and for seed point like [93,221] i should only have #center area
like

storage = [
{name: "#center", xs: 93.68, ys: 221.1, xe: 95.09, ye: 222.24}
];

and for seed point like [100,222] i should only have right block
like

storage = [
   {name: "#right_p3301", xs: 97.93, ys: 219.4, xe: 100.48, ye: 223.94},
    {name: "#p3300", xs: 97.5, ys: 219.83, xe: 100.91, ye: 223.51},
    {name: "#p3299", xs: 100.05, ys: 223.09, xe: 100.91, ye: 223.94},
    {name: "#p3298", xs: 100.05, ys: 219.4, xe: 100.91, ye: 220.25},
    {name: "#p3297", xs: 97.5, ys: 219.4, xe: 98.35, ye: 220.25},
    {name: "#p3296", xs: 97.5, ys: 223.09, xe: 98.35, ye: 223.94}
];

>Solution :

This is a graph problem, where the areas are the nodes, and edges exist when areas overlap. Once the seed point has been mapped to area(s) that contain it, it is a matter of following the edges of the graph to find all linked areas.

Here is an implementation:

  function overlaps(areaA, areaB) {
    return areaA.xs <= areaB.xe && areaB.xs <= areaA.xe &&  
           areaA.ys <= areaB.ye && areaB.ys <= areaA.ye;     
}

function includes(area, x, y) {
    return area.xs <= x && x <= area.xe &&
           area.ys <= y && y <= area.ye;
}

function createGraph(cblock) {
    let graph = new Map(cblock.map(area => [area, []]));
    for (let areaA of cblock) {
        let adjacent = graph.get(areaA);
        for (let areaB of cblock) {
            if (areaA !== areaB && overlaps(areaA, areaB)) adjacent.push(areaB);
        }
    }
    return graph;
}

function findConnectedAreas(cblock, seedX, seedY) {
    let graph = createGraph(cblock);
    let areas = new Set(cblock.filter(area => includes(area, seedX, seedY)));
    for (let area of areas) {
        for (let adjacent of graph.get(area)) areas.add(adjacent);
    }
    return Array.from(areas);
}

// Example run
let cblock = [
    {name: "#left_p3307", xs: 88.29, ys: 219.4, xe: 90.84, ye: 223.94},
    {name: "#p3306", xs: 87.87, ys: 219.83, xe: 91.27, ye: 223.51},
    {name: "#p3305", xs: 90.42, ys: 223.09, xe: 91.27, ye: 223.94},
    {name: "#p3304", xs: 90.42, ys: 219.4, xe: 91.27, ye: 220.25},
    {name: "#p3303", xs: 87.86, ys: 219.4, xe: 88.71, ye: 220.25},
    {name: "#p3302", xs: 87.86, ys: 223.09, xe: 88.71, ye: 223.94},
    {name: "#center", xs: 93.68, ys: 221.1, xe: 95.09, ye: 222.24},    
    {name: "#right_p3301", xs: 97.93, ys: 219.4, xe: 100.48, ye: 223.94},
    {name: "#p3300", xs: 97.5, ys: 219.83, xe: 100.91, ye: 223.51},
    {name: "#p3299", xs: 100.05, ys: 223.09, xe: 100.91, ye: 223.94},
    {name: "#p3298", xs: 100.05, ys: 219.4, xe: 100.91, ye: 220.25},
    {name: "#p3297", xs: 97.5, ys: 219.4, xe: 98.35, ye: 220.25},
    {name: "#p3296", xs: 97.5, ys: 223.09, xe: 98.35, ye: 223.94}
];
let seedX = 90;
let seedY = 222;
let result = findConnectedAreas(cblock, seedX, seedY);
console.log(result);