Помогите придумать алгоритм :)

[arthur2]

Есть картинка такого плана:


Нужно получить из неё массив ректов Натолкните на мысль?

Хитрее всего с энтером: из него ведь нужно получить два ректа

[Хакер]

Чё?

[arthur2]

dim keys() as RECT
Перебираем картинку по пикселям и заполняем массив. Вопрос - по какому принципу перебирать?

[Хакер]

Эта задача нерешаема, потому что форма кнопки Enter непрямоугольна.

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

[arthur2]

Мне нужны не контуры, а именно ректы. Энтер предполагается получить как два ректа, касающиеся одной стороной - верхний рект и нижний (именно верхний и нижний, а не левый и правый).
Для начала - отложим эту заковырку с энтером на по-позже, пусть у нас энтер квадратный (как на некоторых клавах).

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

Нужен как раз алгоритм, как получить эти координаты по картинке.

Пусть это не картинка, а матрица нулей и единиц. Задача - получить вершины и распределить их - какая какому ректу принадлежит.

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

[Proxy]

Пробежать от левого верхнего угла к правому нижнему построчно в поисках чёрных пикселов. При нахождении чёрного запускать процедуру поиска ещё 2 точек для "ректа", т.е. от найденной точки идём вправо до первой белой точки, аналогично вниз. Вот три точки. По ним находим по координатам четвёртую и регаем прямоугольник. После этого на исходном (или копии) строим прямоугольник белый по этим координатам (дабы далее не детектировалось как левая верхняя точка) и идём далее построчно. Сложные полигоны заранее детектировать и распилить на прямоугольники отдельной процедурой (из принципа, что все удовлетворяющие горизонтальные отрезки в окрестностях своих концов имеют точки по одну сторону и в начале и в конце, если не по одну, то надо горизонтальный отрезок достраивать до тех пор, пока в конце не будет найдена точка ниже(выше) как и в начальной точке). Т.е. если у отрезка в левом конце есть точка выше(ниже) в окрестности, а в конце ниже(выше), то необходимо к отрезку добавлять точки справа до тех пор, пока не появится точка выше(ниже) правого конца.

[Хакер]

Артур, опиши задачу точно, а не размыто.

[arthur2]

Proxy Спасибо! ты меня сдвинул с мертвой точки - вроде бы, начало что-то придумываться

Хакер Не занаю, как внятнее Proxy понял, чего мне надо...
Задача - перебирая двухцветную картинку попиксельно, получить массив всех кнопок. Под кнопкой понимается структура RECT либо два ректа, соединенные сторонами. На картинке заведомо нет разомкнутых контуров и контуров, которые не могут быть представлены одним или двумя ректами. Все кнопки заведомо не соприкасаются (если ректы соприкасаются - значит это одна кнопка сложной формы).

[Хакер]

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

Подробнее насчёт картинки.

[arthur2]

А всё Ни каких других требований к картинке нет.

Ну разве что, ширина контура - один пиксель.

[Хакер]

Так нет ни других, ни вообще каких-либо требований. Опиши хоть какие-то.

[arthur2]

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

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

[Joo]

Тебе надо в автоматическом режиме получить на основе изображения массив прямоугольников???

[arthur2]

Ну

[hclubmk]

Межкнопочное пространство, которое, кстати, того же цвета что и кнопки, существует всегда, или возможен вариант без него?

[arthur2]

Существует всегда.

Все кнопки заведомо не соприкасаются (если ректы соприкасаются - значит это одна кнопка сложной формы).

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

[Mikle]

1. Заливаем картинку чёрным цветом от точки (0, 0) - удаляем межклавищные промежутки.
2. Построчно сканируем картинку, как только находим белый пиксель - его координаты, это Left и Top очередного ректа. Двигаемся от этой точки вправо до последнего белого пикселя - это Right, и вниз - это Bottom.
3. Закрашиваем полученный рект любым (не белым) цветом. Goto 2.
Это алгоритм для клавы с прямой клавишей Enter.
Алгоритм быстрой заливки есть в "Кирпичах".

[arthur2]

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

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

Забавно, что те, кто задавали наводящие вопросы - ни чего не предлагают, а предлагают те, кто ничего не уточнял.

[arthur2]

так-с... с GetDIBits получилось мутно и путано - матрица, на сколько я понял, заполняется снизу вверх?

[Mikle]

А вместо заливки, собственно - можно просто изменить требования к картинке.

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

матрица, на сколько я понял, заполняется снизу вверх?

Да.

[arthur2]

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

Мой алгоритм такой:
1. Перебираю слева направо. Если встречаю цвет контура, то это левый верхний угол, left и top. Запускаю процедуру обхода по контуру. Двигаясь по контуру, одновременно его затираю.
2. Продолжаю движение слева направо, пока не кончится цвет контура. Получили правый верхний угол. Это right.
3. Поворачиваю вниз. Двигаюсь, пока не кончится цвет контура. Это нижний правый угол. Bottom.
4. Поворачиваю налево. Если там нет контура, то это либо ошибка в картинке, либо контур пошел снова вправо. Второй вариант пока не рассматриваю, чтобы не запутаться (благо, таких кнопок все равно не бывает).
5. Двигаюсь справа налево, пока не найду угол. Это нижний левый угол. Снова left.
6. Если первый left и второй совпали, кнопка прямоугольная. Затираю последнюю сторону, становлюсь на правый верхний угол, увеличиваю счётчик ректов, выхожу из процедуры обхода контура. Готу 1
7. Если left-ы не совпали, поворачиваю вверх. Увеличиваю счётчик ректов, копирую второй полученный left, right и bottom в новый рект. В предыдущем ректе теперь bottom не корректно.
8. Двигаюсь вверх до угла. Это top текущего ректа и bottom предыдущего ректа (с разницей в единицу, смотря в какую сторону загнута кнопка). Кстати, если бы кнопки на картинке были не контуром, а спрошные, то этот угол было бы труднее найти при ноутной форме энтера.
9. Поворачиваю влево или вправо (в зависимости от того, какой из двух лефтов был больше) и двигаясь до первого left-a, затирая горизонтальную линию. Затем поворачиваю вверх и затираю последнюю линию. Становлюсь в правый верхний угол предыдущего ректа, выхожу из процедуры обхода контура, готу 1.

Вроде, всё

[arthur2]

так-с... с GetDIBits получилось мутно и путано - матрица, на сколько я понял, заполняется снизу вверх?

А чтобы матрица заполнялась привычно - сверху вниз - нужно было всего-то в поле bi32BitInfo.bmiHeader.biHeight установить отрицательное значение