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

[Хакер]

как вычленить разные фигуры и как вычленить контуры дырок.

«Чё??? » (с)

[arthur2]

Тестил на такой картинке:

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

[Хакер]

По условию таких фигур быть не может.

[arthur2]

По какому условию?

[Хакер]

Смотри свой первый пост.

[arthur2]

клава может быть любой самой замысловатой формы

То есть, вполне допускаю, что кнопки могут быть с дыркой, внутри которой, например, будет ещё одна кнопка. Да мало ли...

И потом - алгоритм должен правильно работать вне зависимости от того, какую ему картинку подсунули. Раз уж взялся - нужно бы получить "общий случай"

[Хакер]

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

Сейчас я не вижу препятствия в обработке таких фигур (с контурами внутри). При объединении островков в конце концов будет просто два (а не одно) кольца.

[arthur2]

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

[Хакер]

Может ты что-то своё, не связанное с предложенным пишешь?

При проходе по первой строке образуется N островков. При проходе по второй строке образуется M островков. Часть из них присоединяются к началам островков из множества N. Часть из них присоединяется к концам островков из множества N. Часть никуда не присоединяется.

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

В конце останутся одни только кольца.

В чём, чёрт возьми, проблема-то?

[arthur2]

Ну, в общих чертах так и есть

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

Проблема здесь. Когда дохожу до момента замыкания, я уже не знаю, соединились ли это концы одной фигуры, которая раньше разъединилась, или это две фигуры срослись в одну.

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

[Хакер]

Проблема здесь. Когда дохожу до момента замыкания, я уже не знаю, соединились ли это концы одной фигуры, которая раньше разъединилась, или это две фигуры срослись в одну.

???

Понимаешь, к чему такая реакция? К тому, что ты, видимо, вообще неправильно понял идею с островками и реализуешь что-то глупое и непродуктивное. Идея с островками проста, и в этом её превосходство. В том, что там всё просто и никаких вопросов не возникает.

[arthur2]

Описываю подробно:

1. Проходим по строке, отмечая и запоминая все точки перехода фона в фигуру и обратно. Получается некоторое количество пар вход-выход.
2. Проходим по следующей строке.
3. Сравниваем результаты текущей и предыдущей строки:

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

4.Текущая строка становится предыдущей, а следующая - текущей.
5. В конце получаем набор готовых контуров-колец. (ну или ещё - кольца, вырожденные в линии иди даже точки)


Фигуры я идентифицирую по верхушкам. Если проходя по контуру одной фигуры встречаю верхушку второй, то это фигуры, сросшиеся в одну. Иду по контуру, пока он не замкнется.

Дырки я идентифицирую по по началам разветвления фигур. Если проходя по контуру предполагаемой дырки, натыкаюсь на верхушку какой-либо фигуры, значит "дырка" не замкнулась, иначе контур дырки замкнется. Как узнать, внутри какой из фигур дырка - идей пока нет

И дырки и фигуры надо бы вычленять, ещё при проходе по строкам, но получается очень запутано. Ведь в одном и том же ряду может одновременно закрыться несколько фигур, открыться несколько новых, а так же разветвится и сомкнуться несколько фигур.

[Хакер]

разветвления

Что это? Откуда это взялось?

[arthur2]

Разветвление - не контура, а фигуры:

Код: Выделить всё

'      xxxxxxx
'     xooooooox
'    xooooxxoooox
'   xoooox  xoooox
'  xoooox    xoooox
'   xxxx      xxxx

[Хакер]

Мы вообще-то контур обходим, в котором нет никаких разветвлений. Зачем обходить вместо контура фигуру и этим усложнять себе жизнь, внося необходимость обработки каких-то разветвлений — ума не приложу.

[arthur2]

Стоп! Мы вообще-то обошли все контуры, не отвлекаясь ни на фигуры, ни на дырки и не усложняя себе жизнь.

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

[Хакер]

О боже, что за трудности.

Я расшибусь, сгорю, но не пойму, как при обработке картинки с двумя контурами можно получить один общий контур. А потом страдать, как из этого общего одного контура сделать два.

Две кнопки — получится два контура.
Кнопка с дыркой — получится два контура.
Кнопка и кнопка с дыркой — получится три контура.

[arthur2]

Мы друг друга не понимаем. Точнее, ты меня.

Кнопка с дыркой — получится два контура.

Мне не надо два контура - мне надо одну кнопку с дыркой.

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

Я получил набор точек. Каждая точка соединена с одной следующей и одной предыдущей. Чтобы понять, что этот набор точек - два контура, а не один или три, мне нужно от точки к точке ещё раз пройти.

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

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

[Хакер]

Точнее, ты меня.

Ну да, а ты добрый и пушистый.

Мне не надо два контура - мне надо одну кнопку с дыркой.

Кнопку с дыркой — вытащи её из клавиатуры, просверли. Я думал, мы об обработке картинок с целью получения векторных контуров... А мы...

Я получил набор точек. Каждая точка соединена с одной следующей и одной предыдущей. Чтобы понять, что этот набор точек - два контура, а не один или три, мне нужно от точки к точке ещё раз пройти.

Даже не знаю, что ответить. Чудеса, сказки. Этот набор точек — один контур. Этот набор точек не может быть двумя контурами, тремя и так далее. Один набор точек — один контур. Другой набор точек — второй контур. Третий набор точек — третий контур.

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

Да какого чёрта? По условию контуры не пересекающиеся.

Просто после прохождения алгоритма у меня готовые контуры есть, но я не знаю, сколько их. Могу посчитать - совсем не сложно.

Ты их куда добавляешь? В коллекцию? В массив? И что, проблема вызвать метод Count или псевдо-функцию UBound?

могу выяснить, какие из колец - внешние контуры, а какие - дырки.

Даже если хочется, нужно бить себя по разным частям тела, чтобы небыло желания различать контуры на дырки и не дырки. Контуры и всё. Так их и обрабатываем.

[arthur2]

Даже если хочется, нужно бить себя по разным частям тела, чтобы небыло желания различать контуры на дырки и не дырки.

Мне не нужны контуры, мне нужны фигуры, ограниченные этими контурами. Мне не нужно просто масштабировать картинку целиком, мне нужно масштабировать каждую кнопку по-отдельности.

[arthur2]

Да какого чёрта? По условию контуры не пересекающиеся.

Я знаю

[Хакер]

Мне не нужны контуры, мне нужны фигуры, ограниченные этими контурами.

Мы в самом начале темы определились, что фигура вместе с контуром определяется одним только контуром.

[arthur2]

Ты их куда добавляешь? В коллекцию? В массив? И что, проблема вызвать метод Count или псевдо-функцию UBound?

В самодельный двусвязный список. Про "посчитать" я не точно выразился - посчитать можно и во время алгоритма. Скажем так - пронумировать.

Мы в самом начале темы определились, что фигура вместе с контуром определяется одним только контуром.

Фигура с дыркой будет определена двумя контурами. А с двумя дырками - тремя

[Хакер]

В самодельный двусвязный список.

И в чём смысл держать двухсвязный список {двухсвязных списков}/массивов? Такой вид мазохизма что-ли?

Фигура с дыркой будет определена двумя контурами. А с двумя дырками - тремя

Тебе-то какая разница? Чем является контур. Внешним контуром кнопки или контуром отверстия в кнопке?

[arthur2]

У меня есть только один двусхсвязный список - список точек. Списка отдельных контуров у меня нет.

Как у меня это работает:
Изначально есть некое поле ячеек для хранения точек.
1. При просмотре текущего ряда в ячейки заносятся координаты левых и правых точек. Значения next и prev пока пустые.
2. Затем происходит сравнение с результатами просмотра предыдущего ряда. На его основании у всех левых точек заполняются значения next, а у всех правых - значение prev. То есть, все найденные точки соединяются либо с точками предыдущего ряда, либо между собой.
3. Значения prev у правых и next у левых точек - заполняются, когда текущий ряд становится предыдущим.

На выходе получаю прочитанными все контуры. Но списка этих контуров у меня нет.

Тебе-то какая разница? Чем является контур. Внешним контуром кнопки или контуром отверстия в кнопке?

Разница принципиальная. Например, мне нужен регион отсечения для конкретной фигуры. Для этого мне нужно построить регион по внешниму контуру и исключить из него внутренний контур.

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

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

[Хакер]

У меня есть только один двусхсвязный список - список точек. Списка отдельных контуров у меня нет.

Вот. Уже не правильно. Переделывай.
Двухсвязный список не нужен вообще нигде.
Нужен массив контуров, а сами контуры:

• во время обработки — пары двух массивов (CCWList и CWList), для добавления островков слева и справа. Массивы CCWList и CWList — массивы Long-ов. С первый добавляются «левые» горизонтальные грани (пиксельных границ), а во второй — «правые». Вертикальные грани никуда не добавляются, потому что каждый добавленный элемент соответствует однопиксельной грани.
• После обработки — как массив пар координат X;Y точек.

Разница принципиальная. Например, мне нужен регион отсечения для конкретной фигуры. Для этого мне нужно построить регион по внешниму контуру и исключить из него внутренний контур.

А без разницы. Если комбинировать регионы (gdi-шные) с помощью Xor-операции, нет разница, дырка это или клавиша. Просто комбинируешь между собой все регионы. Понимаешь? Это очень просто, а к тому же более эффективно, чем сначала аддитивно применять регионы кнопок, а потом субтрактивно применять регионы дырок. При этом ведя дифференциацию регионов на кнопочные и дырочные. Будь ленивым, не думай о лишнем, если можно не думать.

[arthur2]

У меня сначала так и было: каждый контур представлял собой массив левых и массив правых точек. Но потом я от этого отказался. Когда два контура смыкаются - ещё ничего. Просто удаляем второй контур, а все его точки переносим в массив правых точек первого. А вот когда одна фигура разделяется , и у одного контура в ряду оказывается сразу две левых и две правых точки - получается очень запутано.

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

Этой фразы не понял Может, и предыдущее не так понял

А без разницы.

Хм, интересно! Про регионы - пока вообще не понял, но до этого ещё нужно дойти - как дойду, так и переспрошу

[Хакер]

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

Если левый и правый соответствуют пространственной ориентации, то это фатально неправильный подход, потому что он подходит только для полностью выпуклых фигур.

Например фигуру буквы W так не обработаешь.

А вот когда одна фигура разделяется , и у одного контура в ряду оказывается сразу две левых и две правых точки - получается очень запутано.

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

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

Этой фразы не понял

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

Два массива Long-переменных. Никаких пар координат, тем более, состоящих в составе элемента, составляющего двухсвязнный список, а поэтому содержащий ещё и пару указателей/индексов на соседей.

[arthur2]

И очень долго делаешь, причём

Ну дык... по часу по ночам после работы (никак не компьютерной, а очень даже физической)

Опять чертовы разделения

Например фигуру буквы W так не обработаешь

Ну а я о чём!? Вот это и есть чертовы разветвления.

CCW-ветка, во время обработки — пары двух массивов (CCWList и CWList), для добавления островков слева и справа. Массивы CCWList и CWList — массивы Long-ов.

Опять ничего не понял.

Сам алгоритм я понял, и понял, вроде, правильно. А как ты предлагаешь организовать его реализацию - не понимаю.

Два массива Long-переменных.

Всего два или по два на каждый контур? Что в них заносится - Х?

[Хакер]

Ну а я о чём!? Вот это и есть чертовы разветвления.

Вот. Это явное свидетельство, что делаешь ты совершенно что-то своё.

Опять ничего не понял.

Что именно и почему?

Всего два или по два на каждый контур?

По два на каждый растущий контур. Как только контур вырос, два массива ориентированных длин горизонтальных пиксельных границ превращаются в один массив пар координат точек.