具有种子点的区域的Floodfill算法

Question

我有一组由开始 xy 和结束 xy 点定义的小区域，并且我有种子 xy 点，它们共同位于该区域的某个地方。所以我的目标是找到所有链接到种子点的区域。所以任何想法如何去做，我知道对于图像我们有 floodfill 算法，我们在所有四个方向上寻找像素颜色。那么有没有可能对地区做点什么。

我的js代码

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);

所以对于像 [90,222] 这样的 xy 种子，我的坐标范围应该是 #p3302 到 #left_p3307喜欢

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}
];

对于像 [93,221] 这样的种子点，我应该只有 #center 区域喜欢

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

对于像[100,222]这样的种子点，我应该只有正确的块喜欢

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}
];

Answer 1

这是一个图形问题，区域是节点，区域重叠时存在边。将种子点映射到包含它的区域后，只需沿着图形的边缘找到所有链接区域即可。

这是一个实现：

  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);

具有种子点的区域的Floodfill算法

Floodfill algorithm for area with seed point

javascript

multidimensional-array