具有种子点的区域的泛洪填充算法

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

因此，对于像[90222]这样的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}
];

对于像[9321]这样的种子点，我应该只有#中心区域像

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

对于种子点，如[1000222]，我应该只有右块像

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