Это история не столько про алгоритмы сколько про ассоциации. Именно ассоциация с каналами кодирования цветов и послужила причиной написания этой статьи.





______________________________________________________________________________________

Суть:

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

Класс CMYK создает пустую копию матрицы (все клетки белые) и по мере обработки контура заполняет ее уже проанализированными узлами, если алгоритм обнаруживает в ней узел, то он уточняет из какого канала был создан этот узел. Если обнаруживается что этот узел был создан в родном канале, значит его создал кто-то из предыдущих уже проанализованных узлов, возможно ближайший сосед, который только что был обработан циклом в предыдущий шаг иттерации цикла, если же, вдруг, выясняется что узел был создан другим каналом, то алгоритм нашел соединение.

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

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

Все обработанные узлы кешируются в той самой дополнительной матрице узлов и удаляются из общего цикла.

Как только обнаруживается что с каким-то конкретным узлом работают два канала, алгоритм фиксирует замыкание контура.

Если замыкание установлено класс вернет список всех точек контура, нет, он вернет undefined.

Раскраска векторов позволяет избавиться от токсичных узлов для анализа в одном из направлений, и при этом оставить актуальными узлы для обработки в других каналах. Именно нахождение одного узла в двух каналах и устанавливает соединение. Узел в двух и более обнаруженных каналах, является связующим узлом.

_____________________________________________________________________________________



На картинке: сверху визуализация итераций цикла, cнизу произвольная фигура из точек с замкнутым контуром. В моем случае если установлено, что в контуре есть замыкание все незамкнутые части контура также будут выделены.

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

Первым зарегистрировалась левая от центральной клетка, далее правая, верхняя и нижняя.

В последующих итерациях эти клетки регистрировали своих соседей с маркировкой конкретного канала. Цикл обработал сначала черный канал, потом голубой (сразу же установил соединение), далее желтый последний фиолетовый.

Алгоритм нашел два узла, единственную голубую и примыкающую к ней фиолетовую. Он пометил обе клетки как узлы соединения.

______________________________________________________________________________________

История ассоциаций:

В рамках тестового задания для одной подающей большие надежды компании возникла необходимость обеспечить следующую функциональность: при клике на произвольную непустую точку, в случае если она лежит на замкнутом контуре фигуры, выделить все точки фигуры для дальнейшей ее трансформации.

Задача, вероятно, покажется вам достаточно простой, но я бы хотел пояснить что работаю на стыке двух областей программирования и дизайна, в связи с чем я не считаю себя ни сильным программистом ни сильным дизайнером, но в сумме у меня не плохой бекграунд для работы в области generative art или data visualization. В мир программирования я вошел через гейм. дев. К тридцати годам я накопил множество интересных знаний, но с учетом того что в найм обычно требуются узко специализированные специалисты мне порой приходится нелегко. Словом, это все лирика, возвращаясь к алгоритму у меня не было на момент начала работ готового алгоритма и я ушел гуглить, с учетом того что задание на самом деле комплексное и не ограничивается исключительно этой задачей, я посчитал это вполне корректным.

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

Я продолжил поиски, на этот раз я решил искать алгоритмы которые используются для заливки области однородным цветом в графических редакторах, через некоторое время я вышел на цепной код Фримена. Далее были статьи про распознавание контура в двухмерных и трехмерных пространствах, распознавание контура лиц и дорожных знаков, OpenCV, внутренности AutoCad, и большая база теоретической математики контуров, словом, невероятно увлекательное приключение, которое, тем не менее, жгло время. После если четырех часов чтива, я понял что все глубже погружаюсь в теоретические дебри и загрустил. Время безжалостно убегало, домашний пес просился на прогулку и я решил что сразу как вернусь буду писать алгоритм сам.

Не буду описывать весь свой ход мыслей, по возвращению у меня была одна идея от которой я хотел оттолкнуться. Я понимал что, в действительности все не так сложно, у нашего алгоритма очень ограниченные возможности в передвижении по матрице, и мне просто нужна циклическая функция которая обходит все связанные точки. Алгоритм мог двигаться максимально всего в четырех направлениях, мне нужно отправить его в путь и как-то поймать его при приближении к исходной точки. Я не без улыбки вспоминал того парня который орал на оператора интернет провайдера, ну вы помните, про «разрыв соединения». Собственно это и была наша с псом полу-готовая идея.Изначально я хотел намеренно разорвать одно из направлений движения и, в случае если бы он вернулся по разорванной линии установить что контур замкнулся. Порисовав немного на бумаге, я понял что у моего варианта есть множество сложных исключений, главное из которых заключается в том что я могу разорвать связь по ложному вектору и, в итоге, просто упереться в тупик. Другие важные исключения были связаны с некой «токсичностью» уже пройденных точек, от которых нужно было избавляться, но которые в случае их утилизации блокировали весь цикл. Не уверен что я слишком точно описываю возможные проблемы, но надеюсь вы меня понимаете. Словом, все было очень плохо до тех пор пока я вдруг не нашел для векторов более подходящего и емкого определения. Я искал решение в четырех возможных каналах движения. Постойте, четыре канала, я же где-то уже это слышал. CMYK. Решение было найдено. Я решил покрасить каналы и тем самым избавиться от токсичности уже обработанных клеток.
Дальнейшая работа была связана уже исключительно с реализацией этой идеи на typescript.

Вместо заключения я хотел бы просто посоветовать всем желающим ознакомится с замечательной книгой Дэна Рома «Визуальное мышление». Возможно это не совсем к месту, но я был в свое время в большом восторге от ее прочтения.

Я спокойно приму вашу критику, поэтому вы можете указать мне на мои возможные ошибки и не слишком стройную архитектуру. Коду всего один день, надеюсь он найдет свое применение.

// algorith/cmyk.ts

import Point from "./../geom/point";

class StreamNode {

    // channel statuses
    public static BLACK: number = 0;
    public static CYAN: number = 1;
    public static YELLOW: number = 2;
    public static MAGENTA: number = 3;

    // link to position in original field
    public point: Point;

    // actual statuses channels
    protected cyan: boolean = false;
    protected yellow: boolean = false;
    protected magenta: boolean = false;
    protected black: boolean = false;

    // current channel
    public channel: number;

    /*
     * @ point - position in field
     * @ channel - node stream channel
     * @ full - if it is a entry point 
    */
    constructor(point: Point, channel: number, full: boolean = false) {
        this.point = point;
        this.channel = channel;
        if (full) {
            this.cyan = true;
            this.yellow = true;
            this.black = true;
            this.magenta = true;
        } else {
            this.registerChannel(channel);
        }

    }

    // register channel status, if it is a connection node or entry node several channels can be marked
    public registerChannel (channel: number): void {
        switch (channel) {
            case StreamNode.BLACK:
                this.black = true;
                break;
            case StreamNode.CYAN:
                this.cyan = true;
                break;
            case StreamNode.YELLOW:
                this.yellow = true;
                break;
            case StreamNode.MAGENTA:
                this.magenta = true;
                break;
            default:
                break;
        }
    }

    // check if it is a native or foreign channel
    public varifyChannel (channel: number): boolean {
        switch (channel) {
            case StreamNode.BLACK:
                return this.black === true;
            case StreamNode.CYAN:
                return this.cyan === true;
            case StreamNode.YELLOW:
                return this.yellow === true;
            case StreamNode.MAGENTA:
                return this.magenta === true;
            default:
                throw "can not identify channel";
        }
    }
}

class CMYK  {

    // matrix of field points, points can be full/empty/transformed
    private matrix: number[][];

    // matrix of stream nodes
    private nodes: StreamNode[][];

    // start point fo analize
    private sourcePoint: Point;

    // status of contrur, if we find connection, we will register it
    private connection: boolean = false;

    /*
     * @source:Point - start point for analyze
     * @matrix:number [][] - matrix of points and there states
     */
    public getStream (source: Point, matrix: number[][]): Point[] {

        // register sourcePoint 
        this.sourcePoint = source;

        // list of all points of cursor
        let responseStream: Point[] = [source];

        // no connections, contur is not closed at the moment
        this.connection = false;

        // sync matrix of points with matrix of stream nodes 
        this.syncMatrixes(matrix);

        // create a node for source point
        let sourceNode: StreamNode = new StreamNode(source, 0, true);

        // register node in matrix of nodes
        this.nodes[source.x][source.y] = sourceNode;

        // init nearest neighbors
        let neighbors: StreamNode[] = this.censur(source, 0, true);

        // init loop stream
        let stream: StreamNode[] = [];

        // add nearest neighbors into stream
        stream = stream.concat(neighbors);

        // run loop
        while (stream.length) {

            // extract some node 
            sourceNode = stream.pop();

            // register point of contur
            responseStream.push(sourceNode.point);

            // add neighbors of this point to stream 
            stream = stream.concat(this.censur(sourceNode.point, sourceNode.channel));
        };


        if (this.connection) {
            // if contur is closed return list of cursor points
            return responseStream;
        } else {
            return undefined;
        }
    }

    /*
     *  Sync matrix of points and matrix of stream nodes
     *  @matrix number[][] - number of points in field    
     */
    private syncMatrixes (matrix: number[][]): void {
        this.matrix = matrix;
        let rows: number = matrix.length;
        let lines: number  = matrix[0].length;
        this.nodes = [];
        for (let i: number = 0; i < rows; i ++) {
            this.nodes[i] = [];
            for (let j: number = 0; j < lines; j ++) {
                this.nodes[i][j] = undefined;
            }
        }
    }

    /*
     * Register new nodes, the nearest neighbors of actual stream node
     * 
     * @source - actual stream position
     * @channel - actual direction of analyze 
     * @increment - channel flag, let register the start point, or point of channel direction
     */
    private censur (source: Point, channel: number, increment: boolean = false): StreamNode[] {
        let stream: StreamNode[] = [];
        let xPosition: number = source.x - 1;
        let yPosition: number = source.y;
        let _channel: number = channel;

        // push left neighbor to stream if it not out of matrix border 
        if (source.x > 0) {
           this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        // change chanel for start point registration 
        if (increment) {
            _channel ++;
        }

        // push right neighbor 
        if (source.x < this.nodes.length - 1) {
            xPosition += 2;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        if (increment) {
            _channel ++;
        }

        // push up neighbor
        if (source.y > 0) {
            xPosition = source.x;
            yPosition -= 1;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        if (increment) {
            _channel ++;
        }

        // push down neighbor
        if (source.y < this.nodes[0].length - 1) {
            xPosition = source.x;
            yPosition += 2;
            this.pushToStream(xPosition, yPosition, stream, _channel);
        }
        return stream;
    }

    /*
     * Register new node for analyze if it doesn't analized yet
     * If it does we varifyChannel, if the channel is the same of parameter channel,
     * it mean that this is parent node, who create this one, and we ignore it. 
     * If the chanels are not the same, we found the connection and contur is closed 
     * If the status of point is empty, we ignore this point, and don't register new node 
     * 
     * @ xPosition - point X
     * @ yPosition - point Y
     * @ stream - stream of nodes which used in node
     * @ channel - actual direction channel
     */
    private pushToStream (xPosition: number, yPosition: number, stream: StreamNode[], channel: number): void {
        // new node
        let node: StreamNode;

        // there is no point in field (empty status) 
        if (this.matrix[xPosition][yPosition] !== 1) {
            // ignore it
            return;
        }
        // this node is already created
        if (this.nodes[xPosition][yPosition] !== undefined) {
            node = this.nodes[xPosition][yPosition];

            // check if this a parent node
            if (node.varifyChannel(channel)) {
                // ignore if it is
                return;
            } else {
                // Congratulattions! We found the connection
                this.connection = true;
                // add one mode channel status to node
                node.registerChannel(channel);

                // here we also can add the point of this node to coonections list ...
                // I don't need it, so I didn't 
            }
        } else {
            // register new node and add it in loop stream
            let point = new Point(xPosition, yPosition);
            node = new StreamNode(point, channel);
            this.nodes[xPosition][yPosition] = node;
            stream.push(node);
        }
    }
}

export default CMYK;

     
//  geom/point.ts
 
class Point {
    public x: number;
    public y: number;

    constructor(x: number, y:number) {
        this.x = x;
        this.y = y;
    }
}

export default Point;