CMYK closed-loop search algorithm on a two-dimensional matrix

This story is not so much about the algorithms as about the association. It is the association with color coding channels that caused this article to be written.




')
______________________________________________________________________________________________________

The bottom line:

At the input, an arbitrary point is transmitted that lies on the contour of a figure from a group of points of a two-dimensional matrix (a usual field of black and white cells), and a matrix describing the position of the points.

The CMYK class creates an empty copy of the matrix (all cells are white) and, as the contour is processed, fills it with already analyzed nodes, if the algorithm detects a node in it, it clarifies from which channel this node was created. If it turns out that this node was created in the native channel, then one of the previously analyzed nodes created it, perhaps the closest neighbor that has just been processed by the loop in the previous step of the iteration, if, suddenly, it turns out that the node was created by another channel, the algorithm found the connection.

There are four channels, because there are only four possible directions of movement from the initial starting point, if the task is to connect the filled points of the field by touching their corners and not the edges, four additional channels will need to be entered to process other starting analysis motion vectors.

The entry point is immediately marked with all four channels, the nearest neighbors are marked with one single channel, and all further movements from these neighbors go with the marking of a specific channel, each node marked with a channel falls into a common flow for all channels and is processed in one of the following iterations.

All processed nodes are cached in the same additional node matrix and removed from the common loop.

As soon as it is found out that two channels work with any particular node, the algorithm fixes the closure of the circuit.

If the closure is set, the class will return a list of all points in the contour, no, it will return undefined.

Coloring vectors allows you to get rid of toxic sites for analysis in one of the directions, and at the same time leave the nodes for processing in other channels relevant. It is the finding of one node in two channels and establishes a connection. A node in two or more channels detected is a connecting node.

_____________________________________________________________________________________



In the picture: on top of the visualization of iterations of the cycle, from the bottom an arbitrary figure of points with a closed contour. In my case, if it is determined that there is a circuit in the circuit, all unclosed parts of the circuit will also be highlighted.

When initiating a search, first of all the nearest neighbors of the incoming point are set, in the figure the incoming point is green, I deliberately clicked into the core to start processing on the maximum number of channels.

The first registered left from the central cell, then the right, upper and lower.

In subsequent iterations, these cells recorded their neighbors with a specific channel marking. The cycle processed the black channel first, then the blue one (immediately established the connection), then the last yellow purple.

The algorithm found two nodes, the only blue and adjacent purple. He marked both cells as junction nodes.

______________________________________________________________________________________________________

Association history:

As part of the test task for one promising company, it became necessary to provide the following functionality: when clicking on an arbitrary non-empty point, if it lies on a closed contour of a figure, select all points of the figure for its further transformation.

The task will probably seem rather simple to you, but I would like to clarify that I work at the intersection of two areas of programming and design, in connection with which I do not consider myself a strong programmer or a strong designer, but in sum I have a good background for areas of generative art or data visualization. I entered the world of programming through a game. dev By the age of thirty, I had accumulated a lot of interesting knowledge, but given the fact that hiring usually requires highly specialized specialists, I sometimes have a hard time. In a word, this is all the lyrics, returning to the algorithm I did not have at the time of the start of the work of the finished algorithm and I left to google, given the fact that the task is actually complex and is not limited solely to this task, I considered it quite correct.

First of all, I found articles on finding the shortest ways out of the maze and the algorithms associated with the game in points , and there and there the topics were very close, but the functions that were needed for a specific task were not in them. The compilation of the knowledge gained to a ready-made solution also did not lead; moreover, I did not leave the feeling that I had embarked on the wrong path, because, in fact, I was thinking more about a free, unoccupied field than about the contour figures themselves. I thought that it might come in handy for me to maintain additional functionality that would allow me to select the inner region of the closed loop, but I couldn’t think of how to get close to the closed loop.

I continued the search, this time I decided to look for algorithms that are used to fill the area with a uniform color in graphic editors, after a while I went to the freeman chain code . Then there were articles about contour recognition in two-dimensional and three-dimensional spaces, contour recognition of faces and road signs, OpenCV, AutoCad insides, and a large base of theoretical mathematics of contours, in short, an incredibly exciting adventure that, nevertheless, burned time. After four hours of reading, I realized that I was plunging deeper and deeper into theoretical jungles and sad. Time ruthlessly ran away, the pet dog asked for a walk and I decided that as soon as I came back I would write the algorithm myself.

I will not describe my entire train of thought, upon returning I had one idea from which I wanted to push off. I understood that, in reality, everything is not so difficult, our algorithm has very limited possibilities in moving around the matrix, and I just need a cyclic function that bypasses all connected points. The algorithm could move as much as possible in all four directions, I need to send him on a journey and somehow catch him when approaching the starting point. I remembered, not without a smile, of the guy who yelled at the ISP operator, well, you remember, about the “disconnection”. Actually, this was our half-ready idea with the dog. Initially, I wanted to deliberately break one of the directions of movement and, if he returned along the broken line, to establish that the contour was closed. Having drawn a little on paper, I realized that my version has a lot of complex exceptions, the main thing of which is that I can break the connection by a false vector and, as a result, just stand up to a dead end. Other important exceptions were related to a certain “toxicity” of the points already passed, from which it was necessary to get rid of, but which, in the case of their utilization, blocked the entire cycle. I'm not sure that I describe the possible problems too accurately, but I hope you understand me. In short, everything was very bad until I suddenly found a more appropriate and capacious definition for vectors. I was looking for a solution in four possible traffic channels . Wait, four channels, I heard it somewhere already. CMYK. A solution was found. I decided to paint the channels and thereby get rid of the toxicity of the already treated cells.
Further work was already connected exclusively with the implementation of this idea on typescript.

Instead of concluding, I would just like to advise everyone to get acquainted with the wonderful book by Dan Roma "Visual Thinking". Perhaps this is not quite appropriate, but I was at one time delighted with her reading.

I will calmly accept your criticism, so you can point me to my possible mistakes and not too slender architecture. The code is only one day, I hope it will find its application.

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