Как сделать функцию заливки рекурсивно заполнить изображение ASCII - PullRequest
Новая
       42

Как сделать функцию заливки рекурсивно заполнить изображение ASCII

1 голос
/ 05 апреля 2019

Мне нужно использовать функцию floodFill, чтобы все точки внутри контура звездочки изображения ASCII превратились в звездочки. Может ли кто-нибудь помочь? 

"use strict";

let bitmap = [
  "................**********........................",
  "...............*..........*.......................",
  "..........*****............*........*.............",
  ".........*.................*.......*.*....*****...",
  "........*................***......*...*.**.....**.",
  "....****.................*.......*.....*.........*",
  "..**......................*******................*",
  ".*...............................................*",
  ".*...............................................*",
  "*...........****.............................****.",
  "*..........*....*.........................***.....",
  ".*.........*....*.......................**........",
  "..***.......****.......................*..........",
  ".....****......................******..*..........",
  ".........**********************.....****.........."
];



const bitmap2string = bitmap => bitmap.join("\n");

console.log(bitmap2string(bitmap));

const showOnPosition = (x, y) => 
  bitmap[y].charAt(x);

const changeSymbol = (x, y, symbol) => 
  bitmap[y].substr(0, x) + symbol + bitmap[y].substr(x + 1);

const floodFill = (x, y) => 
  showOnPosition(x, y) !== "*" 
    ? bitmap.map((line, i) => (i === y ? changeSymbol(x, y, "*") : line)) 
    : bitmap;

Я написал код для:

  • showOnPosition - проверить, что в данный момент находится в координатах x, y массива
  • changeSymbol - изменить символ в любой заданной позиции
  • floodFill - проверяет, что находится в текущей позиции, и, если это не звездочка, меняет ее на звездочку и выдает обновленный массив в консоли.

Теперь я застрял в том, как заставить все это рекурсивно проходить по изображению (справа) и заполняет данный контур звездочками.

Результат должен быть: с вызовом функции floodFill с любыми координатами, например, console.log (floodFill (8, 7)) в консоли отображается следующее:

1 Ответ

2 голосов
/ 05 апреля 2019

Вот ленивая, но простая реализация: 

let bitmap = [
    "................**********........................",
    "...............*..........*.......................",
    "..........*****............*........*.............",
    ".........*.................*.......*.*....*****...",
    "........*................***......*...*.**.....**.",
    "....****.................*.......*.....*.........*",
    "..**......................*******................*",
    ".*...............................................*",
    ".*...............................................*",
    "*...........****.............................****.",
    "*..........*....*.........................***.....",
    ".*.........*....*.......................**........",
    "..***.......****.......................*..........",
    ".....****......................******..*..........",
    ".........**********************.....****.........."
];

// convert to an array of arrays
bitmap = bitmap.map(row => [...row]);
xsize = bitmap[0].length;
ysize = bitmap.length;

floodFill = (x, y) => {

    // check bounds
    if (y < 0 || y >= ysize) return;
    if (x < 0 || x >= xsize) return;

    // already painted?
    if (bitmap[y][x] === '*') return;

    // paint!
    bitmap[y][x] = '*';

    // fill neighbours
    floodFill(x - 1, y);
    floodFill(x + 1, y);
    floodFill(x, y - 1);
    floodFill(x, y + 1);
};

floodFill(7, 8);

// convert to string
bitmap = bitmap.map(row => row.join('')).join('\n');

document.write('<pre>' + bitmap);

Проблема с этим решением заключается в том, что отправная точка произвольна и вполне может лежать за пределами границ.Лучшим подходом было бы сканировать матрицу построчно и выполнять своего рода «трассировку лучей», чтобы определить, находится ли точка внутри или снаружи.Это будет выполняться без рекурсии, по линейному времени.

...