______________________________________________________________________________________
要点：
2次元マトリックス（白黒セルの通常のフィールド）のポイントのグループからの図形の輪郭上にある任意のポイントと、ポイントの位置を記述するマトリックスが入力で送信されます。
CMYKクラスは行列の空のコピーを作成し（すべてのセルは白です）、輪郭が処理されると、既に分析されたノードで塗りつぶします。アルゴリズムがその中にノードを見つけると、このノードが作成されたチャンネルを指定します。 このノードがネイティブチャネルで作成されたことが判明した場合、それは既に分析された以前のノードの誰か、おそらくループ反復の前のステップでサイクルによって処理された最も近い隣人によって作成されたことを意味します。突然、ノードが別のノードによって作成されたことが判明した場合チャネル、それからアルゴリズムは接続を見つけました。
最初の開始点から移動できる方向は4つしかないため、4つのチャネルがあります。タスクがエッジではなく角度に触れることで塗りつぶされたフィールドポイントを接続する場合、他の開始解析モーションベクトルを処理するために4つの追加チャネルを入力する必要があります。
エントリポイントは4つのチャネルすべてですぐにマークされ、最も近い隣人は1つの単一のチャネルでマークされ、これらの隣人からのすべての移動は特定のチャネルのマーク付けで行われ、チャネルでマークされた各ノードはすべてのチャネルに共通のストリームに分類され、サイクルの次の反復のいずれかで処理されます
処理されたすべてのノードは、追加のノードマトリックスにキャッシュされ、一般サイクルから削除されます。
2つのチャネルが特定のノードで機能していることが検出されるとすぐに、アルゴリズムはループクロージャを修正します。
クロージャが設定されている場合、クラスはパス内のすべてのポイントのリストを返します。いいえ、未定義を返します。
着色ベクトルを使用すると、ある方向の分析のために有毒なノードを取り除き、同時に関連する他のチャネルで処理するためにノードを残すことができます。 接続を確立するのは、2つのチャネルで1つのノードを見つけることです。 検出された2つ以上のチャネルのノードは接続ノードです。
_____________________________________________________________________________________
図：閉ループの任意のポイントの図の下にある、上記のサイクルの反復の視覚化。 私の場合、回路内に回路があることが確認されると、回路の閉じていない部分もすべて強調表示されます。
検索を開始すると、まず、着信ポイントの最近傍が設定されます。図では着信ポイントが緑色であるため、最大数のチャネルで処理を開始するために意図的にコアをクリックしました。
最初のものは中央セルの左側に登録され、次に右側、上部、下部に登録されました。
その後の繰り返しで、これらのセルは特定のチャネルラベルで隣接セルを登録しました。 サイクルは最初に黒チャネルを処理し、次に青チャネル（接続をすぐに確立した）、最後の黄色紫を処理しました。
アルゴリズムは、それに隣接する唯一の青と紫の2つのノードを見つけました。 彼は両方のセルをジャンクションノードとしてマークしました。
______________________________________________________________________________________
協会の歴史：
大きな希望を与えるある会社のテストタスクの一部として、次の機能を提供する必要が生じました：任意の空でないポイントをクリックすると、それが図形の閉じた輪郭上にある場合、そのさらなる変換のために図形のすべてのポイントを選択します。
タスクはおそらく非常に単純に思えますが、私はプログラミングとデザインの2つの分野の接点で働いていることを明確にしたいと思います。したがって、私は自分が強力なプログラマーまたは強力なデザイナーだとは思いませんが、ジェネレーティブアートまたはデータの視覚化の分野。 ゲームを通してプログラミングの世界に入りました。 乙女 30歳までに、私は多くの興味深い知識を蓄積していましたが、雇用には通常、高度に専門化された専門家が必要であるという事実を考えると、私にとっては難しい場合があります。 一言で言えば、これはすべての歌詞です。作業の開始時に既製のアルゴリズムを持っていなかったアルゴリズムに戻り、Googleに行きました。タスクは実際には複雑で、このタスクだけに限定されないことを考慮して、これはかなり正しいと考えました。
まず、迷路からの最短の道を見つけるための記事とゲームに関連するアルゴリズムをポイントで見つけました。そして、あちこちでトピックは非常に近かったのですが、特定のタスクに必要な機能はありませんでした。 得られた知識の編集は既成の解決策につながりませんでした。さらに、間違った道を進んだという感覚は私を離れませんでした。実際には、私は輪郭図形自体よりも自由で空いているフィールドについて考えていたからです。 閉ループの内側の領域を区別できる追加機能を維持することは有益だと思いましたが、閉ループに到達する方法を考えることができませんでした。
私は検索を続けましたが、今回はグラフィックエディターで領域を均一な色で塗りつぶすために使用されるアルゴリズムを探すことにしました。しばらくしてからFreemanチェーンコードに行きました。 さらに、2次元および3次元空間の輪郭の認識、顔と道路標識の輪郭の認識、OpenCV、AutoCadの内部、および輪郭の理論的数学の大規模なベースに関する記事がありました。 4時間の読書の後、私は理論的なジャングルの奥深くに沈み込んでおり、悲しいことに気付いた。 時間は容赦なく逃げ出し、飼い犬は散歩を求め、帰ってすぐにアルゴリズムを自分で書くことにしました。
思考の流れ全体を説明するのではなく、帰国後、私は自分自身をプッシュしたいアイデアが1つありました。 現実には、すべてがそれほど複雑ではなく、私たちのアルゴリズムは行列内を移動する可能性が非常に限られており、すべての接続されたポイントをバイパスする巡回関数が必要なことを理解しました。 アルゴリズムは可能な限り4方向にしか移動できませんでした。道路上に送信し、出発点に近づくと何らかの方法でキャッチする必要があります。 笑顔がなかったのではなく、インターネットサービスプロバイダーに叫んでいた男を思い出しました。まあ、あなたは「切断」について覚えています。 最初に、私は意図的に移動の方向の1つを壊し、彼が破線に沿って戻った場合、サーキットが閉じられたことを確認したかったのです。 紙に少し書いて、私のバージョンには多くの複雑な例外があることに気付きました。その主なものは、誤ったベクトルで接続を切断し、最終的に行き止まりに陥ることです。 他の重要な例外は、すでに通過したポイントの特定の「毒性」に関連しており、廃棄する必要がありますが、廃棄するとサイクル全体がブロックされます。 起こりうる問題をあまりにも正確に説明しているかどうかはわかりませんが、理解していただければ幸いです。 一言で言えば、ベクターに対してより適切で容量のある定義を突然見つけたまで、すべてが非常に悪かった。 4つの可能なトラフィックチャネルで解決策を探しました。 4つのチャンネルを待ってください。しかし、すでにどこかで聞きました。 CMYK。 解決策が見つかりました。 私は運河を着色し、それによってすでに処理された細胞の毒性を取り除くことにしました。
さらなる作業は、このアイデアをタイプスクリプトで実装することだけにすでに関係していました。
結論の代わりに、ダンラムの注目すべき本「ビジュアルシンキング」に精通するよう、皆さんにアドバイスしたいと思います。 おそらくこれは完全に場違いではありませんが、かつて私はそれを読むことに非常に熱心でした。
私はあなたの批判を冷静に受け入れますので、あなたは私に起こりうる間違いを指摘することができます。 コードはたった1日で、そのアプリケーションが見つかることを期待しています。
// 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;