Один штрих — это теория графовнаучно-популярныйИзвестная проблема в Кенигсберге, возникшая из-за Семи мостов.научно-популярный. Математик Эйлер не только решил проблему семи мостов в своей статье «Семь мостов Кенигсберга», опубликованной в 1736 году, но и предложил теорему о рисовании одним штрихом, которая, кстати, решила проблему рисования одним мазком. В терминах теории графов для данного связного графанаучно-популярныйСуществует путь, содержащий ровно все отрезки линии и не имеющий повторов, и этот путь является «одноходовым».
Процесс нахождения пути связного графа представляет собой игровой процесс «раскрашивания одним мазком» следующим образом:
Реализация игры
Выполнение «живописи одним мазком» не представляет сложности, автор делит процесс реализации на два этапа:
- Рисование базовой карты
- Интерактивный рисунок
«Рисование базовой карты» отображает связанный граф на холсте в виде «точек и линий», что является самой простой частью игры для реализации; «интерактивное рисование» — это процесс рисования пользователем пути решения проблемы, и этот процесс будет в основном иметь дело с точками и динамически связанной логикой точек.
Рисование базовой карты
"Окрашивание одним мазком" - многоуровневый игровой режим Автор решил выставить кастомизацию уровня (карты подключения) в виде интерфейса настройки. Для раскрытия интерфейса уровня снаружи требуется набор спецификаций, описывающих форму связного графа, и передо мной есть два варианта:
- запись через точку
- линейное обозначение
Возьмем в качестве примера связный граф — пятиконечную звезду, чтобы проиллюстрировать эти два варианта.
Обозначения следующие:
levels: [
// 当前关卡
{
name: "五角星",
coords: [
{x: Ax, y: Ay},
{x: Bx, y: By},
{x: Cx, y: Cy},
{x: Dx, y: Dy},
{x: Ex, y: Ey},
{x: Ax, y: Ay}
]
}
...
]Обозначение линии следующим образом:
levels: [
// 当前关卡
{
name: "五角星",
lines: [
{x1: Ax, y1: Ay, x2: Bx, y2: By},
{x1: Bx, y1: By, x2: Cx, y2: Cy},
{x1: Cx, y1: Cy, x2: Dx, y2: Dy},
{x1: Dx, y1: Dy, x2: Ex, y2: Ey},
{x1: Ex, y1: Ey, x2: Ax, y2: Ay}
]
}
]«Точечная нотация» записывает ответ на уровень, то есть конечные точки должны храниться в массиве в определенном порядкеcoords, это упорядоченная запись. «Линейное обозначение» описывает отрезок прямой связного графа через две точки, который является неупорядоченной записью. Самым большим преимуществом "точечной записи" является то, что она более краткая, но она должна фиксировать ответ на разрешение.Автор является только носителем уровня, а не создателем уровня, поэтому я, наконец, выбрал "линейную запись". :)
Интерактивный рисунок
Рисование пути на холсте визуально представляет собой процесс «выбора или соединения конечных точек связного графа», который должен решить две проблемы:
- Есть ли конечная точка под пальцем
- Можно ли построить линию между выбранной точкой и точкой, которую нужно выбрать
Соберите координаты концов связного графа, а затем отслеживайте координаты скольжения пальца, чтобы знать, «есть ли точка под пальцем». Следующий псевдокод предназначен для сбора координат конечной точки:
// 端点坐标信息
let coords = [];
lines.forEach(({x1, y1, x2, y2}) => {
// (x1, y1) 在 coords 数组不存在
if(!isExist(x1, y1)) coords.push([x1, y1]);
// (x2, y2) 在 coords 数组不存在
if(!isExist(x2, y2)) coords.push([x2, y2]);
});Следующий псевдокод прослушивает смахивание пальцем:
easel.addEventListener("touchmove", e => {
let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY;
// 端点半径 ------ 取连通图端点半径的2倍，提升移动端体验
let r = radius * 2;
for(let [x, y] of coords){
if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){
// 手指下有端点，判断能否连线
if(canConnect(x, y)) {
// todo
}
break;
}
}
})До того, как будет нарисован какой-либо отрезок линии или конечная точка, любая конечная точка, по которой скользит палец, будет считаться начальной точкой «рисования одним мазком»; после того, как отрезок линии (или выбранная точка) будет нарисован, конечная точка может что палец скользит, находится на одной линии с выбранной точкой?Соединительные сегменты линии должны оцениваться в соответствии с существующими условиями.
На приведенном выше рисунке точку A и точку B можно соединить, чтобы сформировать отрезок, но точку A и точку C соединить нельзя. Автор называет «конечную точку, которая может быть соединена с указанной конечной точкой, чтобы сформировать отрезок линии, какдопустимая точка подключения". Допустимые точки соединения для конечных точек связного графа извлекаются из сегментов связного графа:
coords.forEach(coord => {
// 有效连接点（坐标）挂载在端点坐标下
coord.validCoords = [];
lines.forEach(({x1, y1, x2, y2}) => {
// 坐标是当前线段的起点
if(coord.x === x1 && coord.y === y1) {
coord.validCoords.push([x2, y2]);
}
// 坐标是当前线段的终点
else if(coord.x === x2 && coord.y === y2) {
coord.validCoords.push([x1, y1]);
}
})
})Но... Эффективные точки соединения могут только определить, являются ли две точки линейными сегментами базовой карты.Это всего лишь статическая ссылка.В фактическом "интерактивном рисовании" будут встречаться следующие ситуации:
Как показано на рисунке выше, AB соединен последовательно, а эффективной точкой соединения текущей выбранной точки B являются A и C. AB был подключен к проводке, если BA подключен последовательно, то сегмент линии повторяется, поэтому BA не может быть подключен, только AC может быть подключен.
Для выбранной точки у нее есть две действительные точки подключения:
- «Действительная точка подключения на одной линии» с выбранной точкой
- С выбранной точкой "действительная точка соединения без линии"
Среди них в «интерактивном рисовании» могут участвовать только «действительные точки соединения, которые не подключены», и оно является динамическим.
Оглядываясь назад на два вопроса, поднятых в начале этого раздела, «Есть ли конечная точка под пальцем» и «Можно ли провести линию между выбранной точкой и точкой, которую нужно выбрать», на самом деле можно объединить в один вопрос:Есть ли под пальцем «неподключенная действующая точка подключения». Все координаты конечных точек связанного графа должны быть сдвинуты и пройдены пальцем монитора.coordsЕго можно заменить на «действительную точку соединения без линии» текущей выбранной точки.
На данный момент основная функция «Живописи одним мазком» реализована. Вы можете сначала попробовать:
Ли Эн X.GitHub.IO/onestroke/ это…
Автоматическое распознавание изображений
Когда я вошел в конфигурацию уровня, я обнаружил, что связный граф с более чем 7 сторонами легко записать неправильные или жирные отрезки. Автор думает над тем, не разработать ли плагин, автоматически распознающий графику, ведь графика «живописи одним мазком» — это правильные геометрические фигуры.
На приведенной выше «базовой карте» вы можете сразу распознать три цвета:
- белый фон
- цвет конечной точки
- цвет линии
И порядок размера области этих трех цветов в «базовой карте» следующий: белый фон > цвет сегмента линии > цвет конечной точки. «Алгоритм таблицы значений цвета коллекции» базовой карты очень прост, следующий псевдокод:
let imageData = ctx.getImageData();
let data = imageData.data;
// 色值表
let clrs = new Map();
for(let i = 0, len = data.length; i < len; i += 4) {
let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
let key = `rgba(${r}, ${g}, ${b}, ${a})`;
let value = clrs.get(key) || {r, g, b, a, count: 0};
clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count});
}Для связного графа, если конечные точки идентифицированы, получится контур связного графа.
Идентификация конечной точки
Теоретически, собранные «Таблица цветовой стоимости» могут быть непосредственно идентифицированы напрямую. «Алгоритм распознавания конечной точки» автор составляет 2 шага:
- Сканируйте базовую карту попиксельно, пока не встретите пиксель «конечного цвета», и перейдите ко второму шагу.
- Удалите конечную точку с базовой карты и запишите ее координаты, вернитесь к первому шагу.
Псевдокод выглядит следующим образом:
for(let i = 0, len = data.length; i < len; i += 4) {
let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
// 当前像素颜色属于端点
if(isBelongVertex(r, g, b, a)) {
// 在 data 中清空端点
vertex = clearVertex(i);
// 记录端点信息
vertexes.push(vertext);
}
}Но... приведенный выше алгоритм может работать только с графиками без потерь. Когда я использовал скриншот мобильного телефона для тестирования, я обнаружил, что длина собранной «таблицы значений цвета» составляет 5000+! Это напрямую приводит к тому, что значения цвета конечных точек и отрезков прямых не могут быть получены напрямую.
После анализа можно обнаружить, что большинство значений цвета в «таблице значений цвета» схожи, то есть на основе исходного «алгоритма таблицы значений цвета коллекции» можно добавить приблизительный цветовой фильтр к узнать основные точки конечных точек и отрезков цвета. Реализация псевдокода выглядит следующим образом:
let lineColor = vertexColor = {count: 0};
for(let clr of clrs) {
// 与底色相近，跳过
if(isBelongBackground(clr)) continue;
// 线段是数量第二多的颜色，端点是第三多的颜色
if(clr.count > lineColor.count) {
[vertexColor, lineColor] = [lineColor, clr]
}
}После получения основного цвета конечных точек снова запустите «Алгоритм распознавания конечных точек» и определите 203 конечных точки! Почему это?
Изображение выше является частью базового изображения после увеличения в 5 раз. Вокруг и внутри синей конечной точки много шумов (шумовых блоков). Фактически, во время процесса «идентификации конечной точки» из-за наличия шума исходная конечная точка была разложена на дюжину или десятки небольших конечных точек.Ниже приведена базовая карта после запуска «алгоритма идентификации конечных точек»:
Из приведенного выше рисунка можно интуитивно сделать вывод: идентифицированные малые конечные точки концентрируются только на целевой (большой) конечной точке, а малые конечные точки в пределах диапазона больших конечных точек накладываются и чередуются.
Если наложенные в шахматном порядке малые конечные точки объединяются в большую конечную точку, большая конечная точка будет очень близка к целевой конечной точке. Псевдокод слияния малой конечной точки выглядит следующим образом:
for(let i = 0, len = vertexes.length; i < len - 1; ++i) {
let vertexA = vertexes[i];
if(vertextA === undefined) continue;
// 注意这里 j = 0 而不是 j = i +1
for(let j = 0; j < len; ++j) {
let vertexB = vertexes[j];
if(vertextB === undefined) continue;
// 点A与点B有叠加，点B合并到点A并删除点B
if(isCross(vertexA, vertexB)) {
vertexA = merge(vertexA, vertexB);
delete vertexA;
}
}
}После добавления алгоритма слияния малых конечных точек точность «идентификации конечных точек» повышается. Авторский локальный тест смог идентифицировать связный граф с потерями на 100%.
Распознавание сегментов линии
Автор завершает «идентификацию сегмента линии» в два этапа:
- Две заданные конечные точки соединяются в линию, и на линии собираются N «точек выборки»;
- Пройдите пиксели точки выборки, если значение цвета пикселя не равно значению цвета сегмента линии, это означает, что между двумя конечными точками нет сегмента линии.
Как собрать "точки шаблона" - проблема. Слишком плотный повлияет на производительность, слишком слабая точность не может быть гарантирована.
Передо мной два варианта: N — константа, N — переменная.
ПредположениеN === 5. Локальное извлечение «точек стиля» выглядит следующим образом:
На изображении выше выделены три отрезка линии: AB, BC и AC. На самом деле AC не может образовывать линию, это просто результат визуального совмещения AB и BC. Конечно, увеличение значения N может решить эту проблему, но если N используется как константа, то о величине этой константы нужно судить опытным путем, и она действительно дает сдачи.
Чтобы избежать признания AC отрезком прямой, когда AB и BC лежат на прямой, на самом деле это очень просто:Интервал между двумя «точками выборки» меньше или равен диаметру конечной точки.
ПредположениеN = S / (2 * R), S представляет расстояние между двумя точками, а R представляет собой радиус конечной точки. Локальное извлечение «точек стиля» выглядит следующим образом:
Как показано выше, AC успешно обойден. Псевдокодовая реализация «Алгоритма распознавания линейных сегментов» выглядит следующим образом:
for(let i = 0, len = vertexes.length; i < len - 1; ++i) {
let {x: x1, y: y1} = vertexes[i];
for(let j = i + 1; j < len; ++j) {
let {x: x2, y: y2} = vertexes[j];
let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
let N = S / (R * 2);
let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n;
while(--N) {
// 样本点不是线段色
if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break;
}
// 样本点都合格 ---- 表示两点成线，保存
if(0 === N) lines.push({x1, y1, x2, y2})
}
}оптимизация производительности
Поскольку «автоматическое распознавание изображений» требует сканирования пикселей изображения, производительность действительно является проблемой, требующей внимания. Разработанный автором «Алгоритм автоматического распознавания изображений» в процессе распознавания изображения должен дважды сканировать пиксели изображения: «таблицу значений цвета коллекции» и «конечную точку коллекции». На самом деле трудно уменьшить количество сканирований, но для750 * 1334Для базовой карты «алгоритм автоматического распознавания изображений» должен пройти вдвое большую длину750 * 1334 * 4 = 4,002,000Массив, давление все равно будет. Автор повышает производительность за счет сжатия размера сканируемого массива.
Как сжать размер сканируемого массива?
Автор напрямую уменьшает размер сканируемого массива за счет уменьшения размера холста. Псевдокод выглядит следующим образом:
// 要压缩的倍数
let resolution = 4;
let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0];
ctx.drawImage(img, 0, 0, width, height);
let imageData = ctx.getImageData(), data = imageData;После уменьшения исходного изображения в 4 раза полученный массив пикселей изображения является только исходным4^2 = 16倍. Это большое улучшение производительности.
Рекомендации по использованию «Автоматического распознавания изображений»
Хотя автор может определить все «базовые карты» при локальном тестировании, нет гарантии, что изображения, загруженные другими разработчиками, будут хорошо идентифицированы. Автор предлагает использовать «Автоматическое распознавание карт» как отдельный инструмент.
Автор написал отдельную страницу инструмента для «Автоматического распознавания изображений»:Ли Эн X.GitHub.IO/onestroke/ это…
Соответствующая конфигурация уровня может быть сгенерирована на этой странице.
Эпилог
Ниже приводится онлайн-"живопись одним мазком", представленная в этой статье.DEMOQR код:
Исходный код игры размещен по адресу:GitHub.com/LeeEnX/ones…
Основной код реализации игры:GitHub.com/LeeEnX/ones…
Код для автоматического распознавания изображений:GitHub.com/LeeEnX/ones…
Спасибо читателям, которые терпеливо читали эту статью. Эта статья представляет только личные взгляды автора, если что-то не так, пожалуйста, не стесняйтесь, дайте мне знать.
Спасибо за прочтение этой статьи отЛаборатория удароввсе права защищены. При перепечатке просьба указывать источник: Bump Lab (Bump.IO/notes/2017/…)