Векторизация контура. Как масштабировать картинку?

[arthur2]

Нужно масштабировать картинку такого плана:

Причем, клава может быть любой самой замысловатой формы, например, такой:

На любой изначальной картинке у всех клавиш будет контур в один пиксель.

Как масштабировать так, чтобы при любом масштабе контуры оставались в 1 пиксель? Есть идеи?

[Хакер]

1) Векторизовать, отмасштабировать, растеризовать.
2) Ещё более сложный алгоритм. С виду сложный, но по сути с вычислительной точки зрения эквивалентный первому.

Стоит, правда, указать, о каком мастабировании идёт речь. Пропорциональном или непропорциональном. И в каких пределах.

Вот, например, уменьши (вручную!) первую картинку до ширины в 32 px и покажи мне, где там будут границы клавиш в 1 px шириной.

[arthur2]

Стоит, правда, указать, о каком мастабировании идёт речь. Пропорциональном или непропорциональном. И в каких пределах.

Пропорциональное. Нижний предел - как раз тот, при котором выполняется условие. И даже чуть больше (с запасом) - вообще-то, нижний предел определяется тем, чтобы на клавишах можно было написать символы не меньше чем в 8 пунктов.

В принципе, достаточно было бы сгенерировать по исходной, скажем, 5 или 7 картинок разного масштаба, а потом - в оконцовке - "масштабировать", просто подставляя ближайшую к нужному размеру картинку.

Абстрактно я себе представляю задачу так: векторизирую контуры, стираю их на исходной картинке, масштабирую, рисую контуры заново, выползания за контуры затираю, недотягивания до контура дорисовываю...

Нужно понять: 1. Как векторизовать контур 2. Как дорисовать, если появятся просветы между контуром и кнопкой.

[Хакер]

Абстрактно я себе представляю задачу так: векторизирую контуры, стираю их на исходной картинке, масштабирую, рисую контуры заново, выползания за контуры затираю, недотягивания до контура дорисовываю...

Что за глупость? Векторизировал, умножил на число, нарисова заново. Какие ещё подтирания ?

1. Как векторизовать контур

Думай, я в своё время думал и придумал, теперь думай ты. Уверен, что придумаешь.

Как дорисовать, если появятся просветы между контуром и кнопкой.

Это что-то ненужное.

[arthur2]

- Как сделать то-то и то-то?
- Думай. Я придумал и ты сможешь.

Помог, спасибо

[Хакер]

Вселить уверенность в своих силах порой важнее, чем указать на результат приложения чужих сил.

[arthur2]

Да я не страдаю от недостатка уверенности И не такие стенки пробивал лбом Просто кроме моральной поддержки хотелось бы чуть больше конкретики: куда рыть-то? А то пока-что ты сказал более-менее очевидное.

[Хакер]

Рыть в новом разделе темы. Там есть топик, предметом которого является то, на что ты должен обратить внимание при решении проблемы векторизации замкнутого конутра.

[arthur2]

Нашел это: viewtopic.php?f=73&t=35397&start=0 Очень интересно и доходчиво, но про другое

Что за привычка говорить намёками - ткни пальцем, если не трудно.

[Хакер]

Очень интересно и доходчиво, но про другое

«Про другое» — это значит, ты не можешь сообразить, как это применить.

У тебя есть замкнутые контуры, состоящие из вершин и отрезков, соединяющих эти вершины. Вершины принадлежат отрезкам (одна любая вершина двум отрезкам). Иными словами, можно сказать, что замкнутые контуры определяются набором отрезков, а отрезки являются набором точек. Твои контуры нарисованы при помощи алгоритма Брезенхема.

При рисовании входящей информацией было: упорядоченное множество вершин (пар координат).
А на выходе после алгоритма получилось: множество закрашенных точек растра (тоже пары координат).

Это сделал алгоритм Брезенхема. Твоя задача написать обратный алгоритм, который из множества закрашашенных точек растра выведет множество вершин.

Иными словами, растеризация замкнутых однопиксельных самонепересекающихся контуров делается так:

• Составляется список несмежных фигур (по смыслу — клавиш)
• Для каждой фигуры составляешь список закрашенных пикселов.
• Для каждой фигуры заводишь изначально пустой список вершин.
• Сортируешь список закрашенных точек так, чтобы порядок следования точек в списке был таким, чтобы любая пара смежных элементов списка являлась смежными пикселами и в растре. Иными словами, избавляешься от обходческих тупиков:
  

  

  pixel_sorting.png (4.08 Кб) Просмотров: 19791

  
  (тупик 13—14—15, слева смежные в списке точки несмежны в растре)
• При этом появятся неустранимые тупики. Такие места нужно разрешить. Для этого в списке точек дублируешь в обратном порядке точки, мешающие «проходимости». Устранимые тупики тоже можно так разрешать, но это неэффективно. Но для примера: на приведённом выше рисунке для разрешения требуется дублировать точку-13 (в списке) и назначить ей позицию «15» (а точку с 15-ой позиции сдвинуть на 16-ую, с 16-ой — на 17-ую и так далее). Но, повторяю, делать такое надо только с неустранимыми тупиками.
• Важнейший пункт разрешения неустранимых тупиков: центральную точку неустранимого тупика ты добавляешь в список (изначально пустой) вершин фигуры.
• Далее берёшь любую точку фигуры, но эффективнее брать точку, являющуюся вершиной (есть в списке вершин). Начинаешь проходить (walk) по списку точек от этой точки в любом направлении (вперёд/по-часовой или назад/против). При этом на каждой итерации делаешь Bresenham Complete Test (я сам придумал термин, читай описание ниже) от выбранной изначально точки (я советовал в качестве такой брать вершину) до текущей точки. Если тест выполнился, берёшь в качестве текущей точки следующую (по списку (отсортированному) точек) точку. Если тест не выполнился, добавляешь текущую точку в список вершин (важное замечание!), назначёшь текущую точку начальной точкой, а новой текущей точкой — следующую в списке точку и продолжаешь шаги с выполнением теста.
• Когда дойдёшь до самой первой начальной точки — прекращаешь работу. В списке вершин у тебя все вершины фигуры.

Bresenham Complete Test
Тест можно определить как функциональную зависимость.
— предикат от двух переменных pfrom и pto над упорядоченным множеством точек P.
Предикат истенен, если подмножество (множества P) точек эквивалентно (с точностью до порядка следования) множеству , то есть множеству точек, выдаваемым алгоритмом Брезенхема при нахождении всех точек отрезка от pfrom до pto. И ложный — в противном случае.

Для нашего случая и более простым языком: тест успешен, если набор всех точек от начальной до текущей (включая начальную и текущую) совпадает с набором точек, который возвращается алгоритмом Брезенхема для отрезка от начальной точки до текущей. Совпадает — значит одинаковыый набор элементов и одинаковые порядок их следования.

Важное замечание (см. текст выше)
В случае неуспешности BCT нужно текущую точку добавлять в список вершин. Так вот, добавлять нужно не в конец списка, а используя следующую логику:

• Если вершина уже есть в списке, не добавлять вообще.
• Если в списке нет вершин, просто добавлять.
• В противном случае вставлять между двумя вершинами, такими, что точка, соответствующая добавляемой вершине, в отсортированном списке точек находится между точками, соответствующим паре вершин, между которыми ты собрался добавлять.

.

P.S. Делать BCT для каждой итерации, на каждой итерации пересчитывая с нуля множество точек Бр.-отрезка — крайне неэффективно. Придумай «дифференциальную» форму теста, такую, что ты оперируешь разницей между аргументами прошлого теста и аргументами текущего теста и на основе этой разницы определяешь, будет ли разница между результатом текущего BCT и результатом прошлого BCT. Это куда эффективнее. Для этого медитируй над «фактором ошибки».

P.P.S. Прошу, не надо больше просить меня говорить не «намёками». Я умею отвечать только в двух режимах: «намёками» и подобными постами.

P.P.S-2. Описанный алгоритм векторизации — придуман мною весной этого года и сформулирован/описан впервые здесь и сейчас. Если кто-то придумал это и опубликовал раньше (это вполнее вероятно) — тогда я не претендую на авторство.

[arthur2]

Здорово! Правда, с ходу не разобрался - пошел медитировать

[arthur2]

Разобрался до этого места:

тест успешен, если набор всех точек от начальной до текущей (включая начальную и текущую) совпадает с набором точек, который возвращается алгоритмом Брезенхема для отрезка от начальной точки до текущей.

Тут получается непонятно:
На отрезке от синей до синей точки алгоритм выполняется, а вот от синей до зеленой - нет, хотя зеленая - ну никак не вершина. Я понимаю, что чего-то недопонял А с порядком добавления вершин - вообще не понял:

В противном случае вставлять между двумя вершинами, такими, что точка, соответствующая добавляемой вершине, в отсортированном списке точек находится между точками, соответствующим паре вершин, между которыми ты собрался добавлять.

У меня родился другой вариант:
1. Составляем список всех закрашенных пикслелей и избавляемся от тупиков - по твоему варианту.

2. Добавляем в список вершин все точки, которые стыкуются с предыдущей точкой не так, как со следующей.

3. Берем три вершины подряд. Если между первой и третьей BCT выполняется, то вторую вершину исключаем из списка. Если не выполняется - вторая вершина подтвердила право быть вершиной.

Ещё такое соображение: так мы векторизируем только прямые линии. То есть, если этим способом векторизировать растровую окружность, а потом увеличить - получится многоугольник.

[Хакер]

На отрезке от синей до синей точки алгоритм выполняется, а вот от синей до зеленой - нет, хотя зеленая - ну никак не вершина. Я понимаю, что чего-то недопонял

Зря, это особенность алгоритма. Действительно, проблема есть, но она не такая страшная: можно после обхода пройтись по списку вершин и удалить все коллинеарные тройки. Это не сложно, если точек много, а вершин — мало. Другой способ: вместо того, чтобы ждать первого неуспешного BCT, обходишь список точек с конца до первого успешного BCT. Тогда до зелёной вершины дело не дойдёт, а ложных срабатываний (если нет смыкающихся участков контура вообще не будет никогда) не произойдёт. Но здесь ́б́ольшая вычислительная сложность. Третий вариант: так видиозменить дифференциальный BCT, что для зелёной точки срабатывания не произойдёт. И ещё вариант: вместо того, чтобы действовать при первом 1-пиксельном сбое BCT, замечать такие сбои, но не останавливаться на них, а идти дальше до 2-пиксельного сбоя BCT. При двухпиксельном сбое останавливаться и брать во внимание как вершину from-точку, которая дала последний успешный BCT. При таком случае зелёная точка «обнаружится», но проскочится, и выполнение дойдёт до истинной вершины (она зафиксируется как «последняя успешная»), а потом после этой точки как ни крути произойдёт 2-px-сбой BCT. Последний вариант при правильной реализации выглядит наиболее привлекательным. В общем, вариантов я предложил море.

А с порядком добавления вершин - вообще не понял

Список вершин надо реализовывать не как список пар координат точек, а как список указателей/индексов на элементы отсортированного списка точек. При добавлении элемента в список вершин надо перебирать его с начала до пункта, значение (а это указатель/индекс элемента в др. списке (точек)) которого будет меньше или равно порядковому номеру элемента списка точек, который (элемент) соответствует текущей точке, то есть точке, которая детектирована как вершина и как раз сейчас добавляется в список.

Фразу «перебирать его с начала» надо воспринимать условно. Конечно, так можно делать, формально это праивльно, но страшно неэффективно по той причине, что нет смысла в следующий раз перебирать список с начала, потому до уже обойдённого элемента ничего гарантированно измениться не может. Иначе получается «алгоритм маляра Шлемеля» (прочитать о явлении можно тут).

В принципе, можно «не заморачиваться» на этом, а добавлять вершины в список вершин в том порядке, в котором они находятся (обнаруживаются). В конце обхода просто отсортировать этот список по значениям элементов (это указатели/индексы). Но и это неэффективно. Любая сортировка превращает хаос в порядок. Вместо того, чтобы сначала преднамеренно создавать хаос, а потом вынужденно устранять его, я предлагаю изначально создавать порядок, а потом не тратить ресурсы на его создание (он уже есть) из хаоса.

В общем, на шаге фильтрации списка точек, очень вероятно, возникнут неустранимые тупики. Они будут разрешены (resolved), а как побочный эффект — в списке вершин ещё до циклических BCT уже появятся вершины. К моменту начала этапа циклических BCT нужно завести указатель/индекс на элемент списка вершин и установить его на первый элемент списка (если он есть, потому что список запросто может к этому моменту быть пока ещё пустым).

В момент добавления вершины в список вершин нужно сдвигать этот указатель (можно называть его «курсором вставки» (insertion cursor) вперёд до тех пор, пока элемент, на который он указывает, не станет по значение больше индекса текущей точки. При этом (сдвигах курсора) элементы в списке вершин могут кончиться, в этом случае курсорный указатель/индекс нужно обнулить, т.е. привести его в такое состояние, как если бы список вершин вообще был изначально пуст.

А после этого:

• курсор сброшен (список вершин был пуст или достигнут его конец) — добавляем новый элемент в конец списка.
• курсор установлен на какой-то элемент — проверяем, отличается ли индекс добавляемой точки от значения элемента, на который указывает курсор:
  
  • отличается — вставляем в список вершин новый элемент до элемента, на который указывает курсор
  • не отличается — ничего не добавляем (нет смысла плодить дубли), но сдвигаем указатель на следующий элемент списка, либо сбрасываем курсор, если дальше ничего нет.

Ну, надеюсь, теперь понятно? Я уже не знаю, как более доступно разжевать.

То есть, если этим способом векторизировать растровую окружность, а потом увеличить - получится многоугольник.

Увы и ах: это не практически, а теоретически неразрешимая проблема. Извлечь из растра информацию, которой там в принципе нет, — невозможно. Что на самом деле нарисовано — окружность или 10-угольник — не может достоверно сказать никто, кроме растеризатора, если такой был.

Впрочем, можно и это решить: после векторизации полигон превратив в Безье-сплайн, подобрав длину «усиков» по специальному хитрому алгоритму.

[arthur2]

Про порядок добавления вершин - вроде, понял, что ты имел ввиду.

Вот ещё сложность: какую точку считать вершиной?
Если провести идеальные линии, то вообще-то ни одна из четырех под вершину не подходит. Если ввести "дробные пиксели", то вершина будет где-то внутри третьего пикселя чуть выше середины и чуть правее края.

[Хакер]

Вот ещё сложность: какую точку считать вершиной?

На каком этапе?

На сортировке — центры неустранимых тупиков (центры относительно последовательсости точек после разрешения).
На тестах — точку, давшую последний успешный тест.

[Хакер]

Вот ещё что: логика с 1px- и 2-px сбоями должна быть описана другими словами, потому что числа 1 и 2 являются частными случаями.

Рекомендую всё-таки следующую модифицированную логику: определение BCT не менять, кроме того момента, что BCT будет не предикатом. Искать последний успешный BCT, пропускать сбойные BCT и стопать только на таких сбоях BCT, когда появляется точки, которые смежны с точками, составляющими разность множеств и .

[arthur2]

Вершины на выходе всё равно нужны в виде массива поинтов (чтобы передавать в АПИ) Так что предлагаю такой подход: завести массив флагов той же размерности, что и массив точек. При нахождении вершины просто поднимать флаг по тому же индексу, а при лишении точки статуса вершины - флаг опускать. В конце пройти по списку точек, и если флаг поднят, собирать точки в выходной массив (можно прямо в тот же массив точек - дальше он всё равно не понадобится).

Есть ещё несколько признаков вершины, кроме тупиков (эти вершины можно добавить ещё при первом проходе): если точка соседствует по сторонам с тремя белыми полями - она заведомо вершина. Если у точки два белых соседа по сторонам и три - по диагонали - она заведомо вершина. Если у точки только один белый сосед по стороне - она заведомо внутренняя вершина. (Считаем, что все фигуры закрашены серым)

И всё-таки, если после первого прохода ни одна вершина не выявилась, возникает вопрос: а с какой же точки начать проверку по тесту?

Если начать с точки 1 по часовой стрелке, то все следующие скругленные углы прочитаются не так, как первый. Хотя... если несколько отрезков подряд получились слишком короткими, то по-хорошему, нужно бы все точки этих отрезков заносить в список вершин.

Действительно, проблема есть, но она не такая страшная: можно после обхода пройтись по списку вершин и удалить все коллинеарные тройки

Как? Тем более, что это будут не обязательно тройки, а и четвёрки и пятерки...

[Хакер]

Вершины на выходе всё равно нужны в виде массива поинтов (чтобы передавать в АПИ) Так что предлагаю такой подход: завести массив флагов той же размерности, что и массив точек. При нахождении вершины просто поднимать флаг по тому же индексу, а при лишении точки статуса вершины - флаг опускать. В конце пройти по списку точек, и если флаг поднят, собирать точки в выходной массив (можно прямо в тот же массив точек - дальше он всё равно не понадобится).

Глупо. Флаг потребует 1 бит, а отожрётся паразитно при этом от 7 до 31. В конце ты вынужден будешь бегать по всем точкам и смотреть на флаг. При этом собирать новый массив POINTAPI-вершин. Я предлагаю вести список указатель на элементы массива вершин. Потом так же проходить по нему и на основании его создавать список. Единственный плюс: при этом не надо заботиться пот порядки вставки в список вершин.

Если ввести битовый банк, это может оказаться лучше.

если точка соседствует по сторонам с тремя белыми полями - она заведомо вершина.

Что за поля? Если имелись в виду белые точки, то это не так, потому что у 45°-наклонной все точки имеют три белых соседа.

Если у точки два белых соседа по сторонам и три - по диагонали - она заведомо вершина.

Такие условия слишком сложные, чтобы применять их ко всем точкам полигональной фигуры.

И всё-таки, если после первого прохода ни одна вершина не выявилась, возникает вопрос: а с какой же точки начать проверку по тесту?

С первой в отсортированном списке точек, например.

Если начать с точки 1 по часовой стрелке, то все следующие скругленные углы прочитаются не так, как первый.

Это так, от этого не уйти. Имеет вообще значение, по или против часовой стрелки ты будешь обходить (раз), по или против часовой стрелки ты будешь рисовать (два) и как именно реализован алгоритм рисования линии (Брезенхема) (три). Об этом момент, связанном с неопределённостями, я уже писал в своём блоге.

Как? Тем более, что это будут не обязательно тройки, а и четвёрки и пятерки...

Коллинеарные тройки превращаются в двойки.
Чётверки обрабатываются как тройка и единица. Тройка даёт двойку, двойка и единциа даёт новую тройку, новая тройка (возможно) даёт новую двойку. Итеративное упрощение.

[arthur2]

Что за поля? Если имелись в виду белые точки, то это не так, потому что у 45°-наклонной все точки имеют три белых соседа.

Нет, в этом случае у точек по сторонам - только два белых соседа. Третий сосед - по диагонали.

Вот что я имею ввиду:

В первом ряду - у вершин по три белых соседа по сторонам
Во втором ряду - у вершин по два соседа по сторонам и по три диагональных.
В третьем ряду - у вершины только один белый сосед по стороне.

Такие условия слишком сложные, чтобы применять их ко всем точкам полигональной фигуры.

Во-первых, во время обхода контура у каждой точки всё равно смотреть соседей - иначе как вычленить контур. Во-вторых, это не сложнее, чем ВСТ для каждой точки, так что если некоторые вершины удастся вычислить без теста, это окупится.

Флаг потребует 1 бит, а отожрётся паразитно при этом от 7 до 31. <...> Я предлагаю вести список указатель на элементы массива вершин.

Упс... а список ты в чём хранить будешь? Это по меньшей мере массив интеджей (если хранить просто индексы).

Да и потом, не так уж и много с флагами - по байту на точку. Зато не нужно будет вставлять элементы в середину массива (а для этого ведь придется сдвигать весь массив после места вставки). По-моему, расход окупится. И код получится проще.

Если ввести битовый банк, это может оказаться лучше.

Что такое битовый банк? догадываюсь, что что-то вроде битового поля, но как это реализовать на бейсике? Тем более - с индексами отдельных битов?

[Хакер]

Во-первых, во время обхода контура у каждой точки всё равно смотреть соседей - иначе как вычленить контур.

Контур можно обходить грубо, а потом приводить в правильный вид сортировкой. Но есть классный способ обходить растр построчно и при этом получать правильную последовательность точек. Здесь весь смысл в том, что последовательный (serial) обход растра на порядок эффективнее случайного (random-access).

Во-вторых, это не сложнее, чем ВСТ для каждой точки, так что если некоторые вершины удастся вычислить без теста, это окупится.

Это почти бесполезное занятие. Обнаружение вершин не спасает от циклических BCT. Допустим ты найдёшь вершины, но нет никакой гарантии, что между парой смежных вершин нет ещё одной — не обнаруженной вершины. Поэтому всё равно придётся делать BCT. BCT выполняется не на растре, а на списке точек. Нет случайного доступа к памяти. В общем, это намного эффективнее, чем тесты соседей.
То есть ты не прав, что это не сложнее. Это намного «дороже», чем BCT. А пользы — меньше.

Понимаешь?

Упс... а список ты в чём хранить будешь? Это по меньшей мере массив интеджей (если хранить просто индексы).

Конечно, но они у меня будут хранить полезную информацию, а у тебя — оставаться почти пустыми.

Да и потом, не так уж и много с флагами - по байту на точку.

А на координаты точки — 3 байта? По 12 бит (!!!) на координату?

По-моему, расход окупится.

Неа, не окупится.

Что это? догадываюсь, что что-то вроде битового поля, но как это реализовать на бейсике? Тем более - с индексами отдельных битов?

Реализовать с помощью битовых операций. Удобно это сделать не получится.

[arthur2]

А на координату точки — 3 байта? По 12 бит (!!!) на координату?

Не понял Поинт - это ведь два лонга. Ну ладно, пусть будет два интеджа - всё равно 4 байта.

Контур можно обходить грубо, а потом приводить в правильный вид сортировкой. Но есть классный способ обходить растр построчно и при этом получать правильную последовательность точек. Здесь весь смысл в том, что последовательный (serial) обход растра на порядок эффективнее случайного (random-access).

Это как? не понял принципа

[Хакер]

Не понял Поинт - это ведь два лонга. Ну ладно, пусть будет два интеджа - всё равно 4 байта.

Два лонга и один бит на флаг. Итого 65 битов. Сколько надо лишних битов, чтобы «поинт» стал «круглым»? 31 или 63? Лишних-то бита, только для выравнивая до кратной границы...

Это как? не понял принципа

Боже упаси. Ты хочешь, чтобы я и этот свой принцип тебе расписал?

[arthur2]

Два лонга и один бит на флаг. Итого 65 битов. Сколько надо лишних битов, чтобы «поинт» стал «круглым»? 31 или 63? Лишних-то бита, только для выравнивая до кратной границы...

Ничего не понял. У меня - массив байтов-флагов (по байту добавки на точку) У тебя - массив интеджей-индексов (по два байта). У меня экономней. Ну ладно - у тебя массив короче, потому что там не все точки, а только вершины... Всё равно почти поровну.

Боже упаси. Ты хочешь, чтобы я и этот свой принцип тебе расписал?

Ну я-то хочу, но если тебе в лом, то не надо

[Хакер]

У меня экономней. Ну ладно - у тебя массив короче, потому что там не все точки, а только вершины... Всё равно почти поровну.

Дело не в том, что он короче. Он действительно короче. Но мне его не нужно обходить чтобы что-то там искать. А у тебя он мало того, что больше, так в нем ещё и положительные элементы искать надо.

Ну как тебя переубедить. Представь, что у тебя квадрат 50×50 px. У меня будет 4 индекса/указателя, а у тебя 196 байтов-флагов. Чуешь разницу? Причём я, используя индексы/указатели, сразу смогу обратиться к 4 элементам списка точек. А тебе надо будет пробегать по 196 элементам, делать 196 проверок флага, чтобы найти всего-лишь 4 установленных флажка. Что, эффективно?

Ну я-то хочу, но если тебе в лом, то не надо

Концепция островков/мозайки. Сканируешь строку, находишь непрерывные последовательности черных точек. Это и есть островки. На следующей строке будут новые островки. Фишка в соединении островков. То, что левее прошлого островка — добавлять (в списке!) перед, а то, что права — после. А островок, соединяющий два вырхних островка, соединяет два несвязанных списка в один. Или замыкает список.

Дальше сам.

[arthur2]

Дальше сам.

Круто! Попробую

Что, эффективно?

Зато, если вершин много, если вершины нужно будет добавлять не в конец списка, если потом лишние вершины нужно будет подчищать - у меня нужно будет только поднимать или опускать флаги, а у тебя - сдвигать элементы массива... К тому же, если бы я делал по твоему варианту, я бы всё рано заранее проредимил массив индексов с запасом - чтобы не перередимливать.

В общем, не знаю - может ты и прав. Но в моём варианте код понятнее. Подумаю про битовое поле

[Хакер]

Короче, если у тебя получится, отпишись сюда.

Я это придумал ещё весной, но испытать и реализовать, как обычно, времени нет. Будет хорошо, если всё это отлично сработает. Контурообход и векторизация — небольшая часть задуманного мною алгоритма (и формата) сжатия изображений без потерь, который, по моим оценками, имеет большие шансы обогнать существующие форматы.

[Хакер]

Ну как?

[arthur2]

Ещё никак - времени нет
Кстати, условия несколько изменились: контура у каждой клавиши теперь нет. Есть только сама клавиша и фон, так что контур сначала нужно вычислить Это мне несколько подпортило построчное считывание контура - теперь не соображу, как его реализовать.

А флаги-биты, кстати, можно хранить, например, в первом бите икса Всё равно лонга для одной координаты - слишком уж дофига.

[Хакер]

Это мне несколько подпортило построчное считывание контура - теперь не соображу, как его реализовать.

Вместо цвета обращаешь внимание на изменение цвета. Опять дифференцируешь, иными словами.

[arthur2]

Победил пока только построчное чтение контура. Блин, чуть разрыв мозга не заработал Кстати, тупиков при таком методе обхода не возникает

Осталась пара нерешенных вопросов: как вычленить разные фигуры и как вычленить контуры дырок.