CMYK zweidimensionaler Matrix-Suchalgorithmus mit geschlossener Schleife

    In dieser Geschichte geht es weniger um Algorithmen als um Assoziationen. Es war die Assoziation mit Farbcodierungskanälen, die als Grund für das Schreiben dieses Artikels diente.

    Bild



    ______________________________________________________________________________________

    Essenz:

    Bei der Eingabe wird ein beliebiger Punkt, der auf der Kontur einer Figur liegt, aus einer Gruppe von Punkten einer zweidimensionalen Matrix (einem gewöhnlichen Feld aus schwarzen und weißen Zellen) und einer Matrix, die die Position der Punkte beschreibt, übertragen.

    Die CMYK-Klasse erstellt eine leere Kopie der Matrix (alle Zellen sind weiß) und füllt sie beim Verarbeiten der Kontur mit den bereits analysierten Knoten. Wenn der Algorithmus einen Knoten darin findet, gibt er an, aus welchem ​​Kanal dieser Knoten erstellt wurde. Wenn sich herausstellt, dass dieser Knoten im nativen Kanal erstellt wurde, bedeutet dies, dass er von einer Person aus den zuvor analysierten Knoten erstellt wurde, möglicherweise dem nächsten Nachbarn, der gerade vom Zyklus im vorherigen Schritt der Schleifeniteration verarbeitet wurde, wenn sich plötzlich herausstellt, dass der Knoten von einem anderen Knoten erstellt wurde Kanal, dann hat der Algorithmus eine Verbindung gefunden.

    Es gibt vier Kanäle, da es nur vier mögliche Bewegungsrichtungen ab dem Startpunkt gibt. Wenn Sie die gefüllten Feldpunkte durch Berühren ihrer Winkel anstelle von Kanten verbinden möchten, müssen Sie vier zusätzliche Kanäle eingeben, um andere Bewegungsvektoren für die Startanalyse zu verarbeiten.

    Der Eintrittspunkt wird sofort mit allen vier Kanälen markiert, die nächsten Nachbarn werden mit einem einzigen Kanal markiert, und alle weiteren Bewegungen von diesen Nachbarn gehen mit der Markierung eines bestimmten Kanals einher, wobei jeder mit einem Kanal markierte Knoten in einen für alle Kanäle gemeinsamen Stream fällt und in einer der folgenden Iterationen des Zyklus verarbeitet wird.

    Alle verarbeiteten Knoten werden in dieser zusätzlichen Knotenmatrix zwischengespeichert und aus dem allgemeinen Zyklus entfernt.

    Sobald erkannt wird, dass zwei Kanäle mit einem bestimmten Knoten arbeiten, korrigiert der Algorithmus den Schleifenschluss.

    Wenn der Abschluss gesetzt ist, gibt die Klasse eine Liste aller Punkte im Pfad zurück, nein, sie gibt undefiniert zurück.

    Mit Farbvektoren können Sie toxische Knoten für die Analyse in eine der Richtungen entfernen und gleichzeitig die Knoten für die Verarbeitung in anderen relevanten Kanälen belassen. Das Auffinden eines Knotens in zwei Kanälen stellt eine Verbindung her. Ein Knoten in zwei oder mehr erkannten Kanälen ist ein Verbindungsknoten.

    _____________________________________________________________________________________



    Im Bild: Visualisierung von Iterationen des Zyklus über, unter einer beliebigen Anzahl von Punkten mit einer geschlossenen Schleife. Wenn in meinem Fall festgestellt wird, dass sich ein Stromkreis im Stromkreis befindet, werden auch alle nicht geschlossenen Teile des Stromkreises hervorgehoben.

    Wenn Sie eine Suche starten, werden zunächst die nächsten Nachbarn des eingehenden Punkts festgelegt. In der Abbildung ist der eingehende Punkt grün. Ich habe absichtlich in den Kern geklickt, um die Verarbeitung für die maximale Anzahl von Kanälen zu starten.

    Der erste befand sich links von der zentralen Zelle, dann der rechte, obere und untere.

    In nachfolgenden Iterationen registrierten diese Zellen ihre Nachbarn mit einer bestimmten Kanalbezeichnung. Der Zyklus verarbeitete zuerst den schwarzen Kanal, dann den blauen Kanal (stellte sofort die Verbindung her) und dann das letzte gelbe Lila.

    Der Algorithmus hat zwei Knoten gefunden, von denen nur der blaue und der violette daneben liegen. Er markierte beide Zellen als Knotenpunkte.

    ______________________________________________________________________________________

    Geschichte der Assoziationen:

    Im Rahmen der Testaufgabe für ein vielversprechendes Unternehmen wurde es erforderlich, die folgende Funktionalität bereitzustellen: Wenn Sie auf einen beliebigen nicht leeren Punkt klicken, wenn dieser auf einer geschlossenen Kontur der Figur liegt, wählen Sie alle Punkte der Figur für ihre weitere Transformation aus.

    Die Aufgabe wird Ihnen wahrscheinlich recht einfach erscheinen, aber ich möchte klarstellen, dass ich an der Schnittstelle der beiden Bereiche Programmierung und Design arbeite und mich daher nicht als starken Programmierer oder starken Designer betrachte, aber in der Summe habe ich keinen schlechten Hintergrund für die Arbeit in Bereiche der generativen Kunst oder Datenvisualisierung. Ich bin durch das Spiel in die Welt des Programmierens eingetreten. Mädchen Im Alter von 30 Jahren hatte ich viele interessante Kenntnisse gesammelt, aber angesichts der Tatsache, dass das Einstellen normalerweise hochspezialisierte Fachkräfte erfordert, ist es manchmal schwierig für mich. Mit einem Wort, das sind alle Texte. Zurück zu dem Algorithmus, über den ich zu Beginn der Arbeit noch keinen vorgefertigten Algorithmus verfügte, und ich ging zu Google, da die Aufgabe tatsächlich komplex und nicht ausschließlich auf diese Aufgabe beschränkt ist. Ich hielt dies für richtig.

    Zunächst habe ich Artikel über die Suche gefunden.Die kürzesten Wege aus dem Labyrinth und den mit dem Spiel verbundenen Algorithmen in Punkten , und hier und da waren die Themen sehr eng, aber die Funktionen, die für eine bestimmte Aufgabe benötigt wurden, waren nicht vorhanden. Die Zusammenstellung der gewonnenen Erkenntnisse führte nicht zu einer vorgefertigten Lösung, außerdem ließ mich das Gefühl, den falschen Weg eingeschlagen zu haben, nicht los, weil ich in Wirklichkeit mehr an ein freies, unbesetztes Feld dachte als an die Konturfiguren selbst. Ich dachte, dass es für mich nützlich sein könnte, zusätzliche Funktionen beizubehalten, die es mir ermöglichen, den inneren Bereich der geschlossenen Schleife zu unterscheiden, aber ich konnte mir nicht vorstellen, wie ich zur geschlossenen Schleife komme.

    Ich setzte die Suche fort, dieses Mal entschied ich mich dafür, nach Algorithmen zu suchen, mit denen der Bereich in Grafikeditoren mit einheitlichen Farben gefüllt wird, und ging nach einer Weile zum Freeman-Kettencode . Außerdem gab es Artikel über das Erkennen einer Kontur in zweidimensionalen und dreidimensionalen Räumen, das Erkennen einer Kontur von Gesichtern und Verkehrszeichen, OpenCV, das Innere von AutoCad und eine große Basis theoretischer Konturenmathematik, kurz gesagt, ein unglaublich aufregendes Abenteuer, das jedoch Zeit in Brand steckte. Nach vier Stunden stellte ich fest, dass ich tiefer in den theoretischen Dschungel versank und traurig war. Die Zeit rannte unbarmherzig davon, der Haushund bat um einen Spaziergang und ich beschloss, dass ich den Algorithmus selbst schreiben würde, sobald ich zurückkam.

    Ich werde nicht meinen gesamten Gedankengang beschreiben, als ich zurückkam, hatte ich eine Idee, von der ich mich abbringen wollte. Ich habe verstanden, dass in Wirklichkeit alles nicht so kompliziert ist, unser Algorithmus nur sehr begrenzte Möglichkeiten hat, sich in der Matrix zu bewegen, und ich brauche nur eine zyklische Funktion, die alle verbundenen Punkte umgeht. Der Algorithmus könnte sich so weit wie möglich in nur vier Richtungen bewegen, ich muss ihn auf die Straße schicken und ihn irgendwie auffangen, wenn ich mich dem Startpunkt nähere. Nicht ohne ein Lächeln erinnerte ich mich an den Typ, der den Internetdienstanbieter angeschrien hatte. Eigentlich war das unsere halbfertige Idee mit dem Hund. Anfangs wollte ich absichtlich eine der Bewegungsrichtungen brechen und, wenn er entlang der unterbrochenen Linie zurückkehrte, feststellen, dass der Stromkreis geschlossen war. Ein wenig auf Papier gezeichnet, Ich erkannte, dass meine Version viele komplexe Ausnahmen hat. Die wichtigste davon ist, dass ich die Verbindung auf einem falschen Vektor unterbrechen und am Ende einfach in eine Sackgasse geraten kann. Weitere wichtige Ausnahmen betrafen eine gewisse „Toxizität“ bereits bestandener Punkte, die entsorgt werden mussten, bei deren Entsorgung jedoch der gesamte Kreislauf blockiert wurde. Ich bin mir nicht sicher, ob ich die möglichen Probleme zu genau beschreibe, aber ich hoffe, Sie verstehen mich. Mit einem Wort, alles war sehr schlecht, bis ich plötzlich eine passendere und umfassendere Definition für Vektoren fand. Ich suchte nach einer Lösung in vier möglichen von dem es notwendig war, loszuwerden, der aber, wenn er entsorgt wurde, den gesamten Zyklus blockierte. Ich bin mir nicht sicher, ob ich die möglichen Probleme zu genau beschreibe, aber ich hoffe, Sie verstehen mich. Mit einem Wort, alles war sehr schlecht, bis ich plötzlich eine passendere und umfassendere Definition für Vektoren fand. Ich suchte nach einer Lösung in vier möglichen von dem es notwendig war, loszuwerden, der aber, wenn er entsorgt wurde, den gesamten Zyklus blockierte. Ich bin mir nicht sicher, ob ich die möglichen Probleme zu genau beschreibe, aber ich hoffe, Sie verstehen mich. Mit einem Wort, alles war sehr schlecht, bis ich plötzlich eine passendere und umfassendere Definition für Vektoren fand. Ich suchte nach einer Lösung in vier möglichenKanal - Bewegung. Warten Sie, vier Kanäle, aber ich habe es schon irgendwo gehört. CMYK. Eine Lösung wurde gefunden. Ich beschloss, die Kanäle zu färben und so die Toxizität der bereits behandelten Zellen zu beseitigen.
    Weitere Arbeiten waren bereits ausschließlich mit der Umsetzung dieser Idee in Maschinenschrift verbunden.

    Anstelle eines Abschlusses möchte ich nur jedem raten, sich mit Dan Rums bemerkenswertem Buch "Visual Thinking" vertraut zu machen. Vielleicht ist das nicht ganz unangebracht, aber ich war einmal sehr begeistert davon, es zu lesen.

    Ich werde Ihre Kritik ruhig annehmen, damit Sie mich auf mögliche Fehler und nicht zu schlanke Architektur hinweisen können. Der Code ist nur ein Tag, ich hoffe, es findet seine Anwendung.

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

    Jetzt auch beliebt: