Это история не столько об алгоритмах, сколько об ассоциациях.
Именно ассоциация с каналами цветового кодирования побудила к написанию этой статьи.
______________________________________________________________________________________
Сущность:
На входе — произвольная точка, лежащая на контуре фигуры из группы точек двумерной матрицы (обычное поле черных и белых клеток), и матрица, описывающая положение точек.
Класс CMYK создает пустую копию матрицы (все ячейки белые) и по мере обработки контура заполняет ее уже проанализированными узлами.
Если алгоритм обнаруживает в нем узел, то он указывает, из какого канала этот узел был создан.
Если окажется, что этот узел создан в нативном канале, то он создан одним из предыдущих уже проанализированных узлов, возможно, ближайшим соседом, который только что был обработан циклом на предыдущем шаге цикла, если вдруг , оказывается, что узел был создан другим каналом, значит алгоритм нашел соединение.
Каналов четыре, потому что существует только четыре возможных направления движения от начальной отправной точки; если стоит задача соединить заполненные точки поля, касаясь их углов, а не краев, то потребуется ввести четыре дополнительных канала для обработки других стартовых векторов движения анализа.
Точка входа маркируется сразу всеми четырьмя каналами, ближайшие соседи маркируются одним единственным каналом, а все дальнейшие перемещения от этих соседей маркируются определенным каналом, каждый узел, отмеченный каналом, попадает в общий для всех каналов поток и обрабатывается на одной из следующих итераций цикла.
Все обработанные узлы кэшируются в той же дополнительной матрице узлов и удаляются из общего цикла.
Как только обнаруживается, что с конкретным узлом работают два канала, алгоритм фиксирует замыкание цепи.
Если замыкание установлено, класс вернет список всех точек контура, нет, он вернет неопределенное значение.
Векторная раскраска позволяет избавиться от токсичных узлов для анализа в одном из направлений, оставив при этом актуальные узлы для обработки в других каналах.
Именно наличие одного узла в двух каналах устанавливает соединение.
Узел в двух или более обнаруженных каналах является соединительным узлом.
_____________________________________________________________________________________ 
На картинке: вверху визуализация итераций цикла, внизу произвольная фигура из точек с замкнутым контуром.
В моем случае, если будет определено, что в контуре есть замыкание, то все незамкнутые части контура также будут подсвечены.
При запуске поиска сначала определяются ближайшие соседи входящей точки; на рисунке входящая точка выделена зеленым цветом; Я намеренно нажал на ядро, чтобы начать обработку по максимальному количеству каналов.
Первой регистрировалась ячейка слева от центральной, затем правая, верхняя и нижняя.
В последующих итерациях эти ячейки регистрировали своих соседей с определенной маркировкой канала.
В цикле обрабатывался сначала черный канал, затем синий (сразу установилось соединение), затем желтый и последний фиолетовый.
Алгоритм нашел два узла: один синий и прилегающий к нему фиолетовый.
Он отметил обе ячейки как узлы соединения.
______________________________________________________________________________________ История ассоциаций: В рамках тестового задания для одной перспективной компании возникла необходимость предусмотреть следующий функционал: при нажатии на произвольную непустую точку, если она лежит на замкнутом контуре фигуры, выбирать все точки фигуры для ее дальнейшая трансформация.
Задача, возможно, покажется вам довольно простой, но хотелось бы уточнить, что я работаю на стыке двух направлений программирования и дизайна, а потому не считаю себя ни сильным программистом, ни сильным дизайнером, но в целом я иметь хороший опыт работы в области генеративного искусства или визуализации данных.
Я вошел в мир программирования через игры.
разработчик К тридцати годам у меня накопилось много интересных знаний, но с учетом того, что для приема на работу обычно требуются узкоспециализированные специалисты, мне иногда приходится нелегко.
Одним словом это всё лирика, возвращаясь к алгоритму, готового алгоритма на момент начала работы у меня не было и я пошёл в гугл с учётом того, что задача на самом деле сложная и не ограничена исключительно под эту задачу, я посчитал это вполне правильным.
Первым делом я нашел статьи о поиске кратчайшие пути выхода из лабиринта И алгоритмы, связанные с игрой в точки , в обоих случаях темы были очень близки, но не имели той функции, которая нужна для конкретной задачи.
Обобщение полученных знаний также не привело к готовому решению; более того, я не мог избавиться от ощущения, что пошел неверным путем, потому что в действительности я больше думал о свободном поле, незанятом клетками, чем о самих контурных фигурах.
Я думал, что мне это может понадобиться для поддержки дополнительного функционала, который позволит мне подсветить внутреннюю область замкнутого контура, но так и не смог придумать, как приблизиться к замкнутому контуру.
Я продолжил свои поиски, на этот раз решил поискать алгоритмы, которые используются для заливки области равномерным цветом в графических редакторах, через некоторое время я придумал Цепной код Фримена .
Дальше были статьи про распознавание контуров в двухмерном и трехмерном пространствах, контурное распознавание лиц и дорожных знаков, OpenCV, внутренности AutoCad и большую базу теоретической математики контуров, словом невероятно увлекательное приключение , что, тем не менее, сожгло время.
После четырёх часов чтения я понял, что всё глубже погружаюсь в теоретические дебри и стало грустно.
Время убегало нещадно, семейная собака просилась на прогулку, и я решил, что как только вернусь, напишу алгоритм сам.
Я не буду описывать весь ход моих мыслей; По возвращении у меня возникла одна идея, которую я хотел развить.
Я понял, что на самом деле все не так сложно, наш алгоритм имеет очень ограниченные возможности по перемещению по матрице, и мне просто нужна циклическая функция, проходящая через все связанные точки.
Алгоритм мог двигаться максимум только в четырех направлениях, мне нужно отправить его в путь и как-то поймать при приближении к начальной точке.
Вспомнил не без улыбки парня, который кричал на оператора интернет-провайдера, помните, об «отключении».
На самом деле это была незаконченная идея между мной и собакой.
Изначально я хотел намеренно разорвать одно из направлений движения и, если он вернется по ломаной, установить, что цепь замкнута.
Немного порисовав на бумаге, я понял, что в моей версии много сложных исключений, главное из которых — я могу разорвать связь по ложному вектору и в итоге просто зайти в тупик.
Другие важные исключения были связаны с определенной «токсичностью» уже пройденных пунктов, от которых нужно было избавиться, но избавление от которых блокировало весь цикл.
Не уверен, что слишком точно описываю возможные проблемы, но надеюсь, вы меня поймете.
Словом, все было очень плохо, пока я вдруг не нашел более подходящее и емкое определение векторов.
Я искал решение четырьмя возможными способами каналы движения.
Подождите, четыре канала, я где-то это уже слышал.
CMYK. Решение найдено.
Я решил закрасить каналы и тем самым избавиться от токсичности уже обработанных клеток.
Дальнейшая работа была связана исключительно с реализацией этой идеи в машинописном виде.
Вместо заключения я бы просто посоветовал всем прочитать замечательную книгу Дэна Роума «Визуальное мышление».
Возможно, это не совсем уместно, но в свое время я был очень рад ее прочтению.
Я спокойно приму вашу критику, чтобы вы могли указать на мои возможные ошибки и не очень гармоничную архитектуру.
Коду всего один день, надеюсь, он найдет свое применение.
Теги: #JavaScript #алгоритм #визуальное мышление #JavaScript #Алгоритмы// 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;
-
Дешевые Колонки
19 Oct, 24 -
Демонстрация Svg/Smil "Doc"
19 Oct, 24 -
Изменение Размера Любых Окон В Windows Xp
19 Oct, 24 -
Контейнеризация — Новый Виртуальный Хостинг
19 Oct, 24
