conraddk wrote: > Пришла в голову еще одна мысль. Совсем с другого края. Раз изображение > растровое, будем вовсю использовать flood fill. Можно заливать > поочередно замкнутые области, учитывая направление границ для > определения соседей. Для упрощения можно заранее залить фон каким-нибудь > отдельным цветом. > Но! Задача сводится к раскраске планарного графа в 2 цвета, что, как > известно, в общем случае невозможно. Поэтому идеального решения не > существует, но для симпатичного представления "на вид" можно > использовать эвристики. Например: при противоречии закрашиваем тем > цветом, которого меньше всего среди соседей. > Хотя, сдается мне, полностью детерминированно можно раскрасить только > после векторизации и полноценного применения even-odd, как предложил
Скорее проблемы с определением соседей. Как различать удачное
пересечение границ от куска общей границы.
Здравствуйте, raskin, Вы писали:
R>Reunion wrote: >> R>>Так там так и сделано. Я еагирую на последовательность черных >> пикселей. Закрашиваю от одной последовательности до другой, потом >> пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает >> >> C>Пришла в голову еще одна мысль. Совсем с другого края. Раз изображение >> растровое, будем вовсю использовать flood fill. Можно заливать >> поочередно замкнутые области, учитывая направление границ для >> определения соседей. Для упрощения можно заранее залить фон каким-нибудь >> отдельным цветом. >> C>Но! Задача сводится к раскраске планарного графа в 2 цвета, что, как >> известно, в общем случае невозможно. Поэтому идеального решения не >> существует, но для симпатичного представления "на вид" можно >> использовать эвристики. Например: при противоречии закрашиваем тем >> цветом, которого меньше всего среди соседей. >> C>Хотя, сдается мне, полностью детерминированно можно раскрасить только >> после векторизации и полноценного применения even-odd, как предложил >> <http://rsdn.ru/forum/Message.aspx?mid=1289220&only=1>
McSeem2. >> >> В моем случае можно всегда покрасить в два цвета — кривая рисуется >> пользователем не отрывая карандаша... Такую кривую можно.
R>А нельзя хранить дополнительную информацию о пути рисования? А то можно R>ведь такого нарисовать..
Упс, , чего-то я вам сказать забыл... Можно. Есть последовательность точек, которую рисует пользователь... Не бейте...
Пардон, там кажется с картинками не так...
R>Всем привет!
R>Есть изображение такого вида: R>
R>Надо сделать так: R>
R>Какие есть алгоритмы? Где можно найти их реализацию? R>Заранее спасибо!
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Reunion, Вы писали:
R>>>Какие есть алгоритмы? Где можно найти их реализацию? R>>>Заранее спасибо!
MS>Я приводил в исходниках: http://www.rsdn.ru/Forum/Message.aspx?mid=461727&only=1
MS>Там можно включить режим even-odd fill. А сглаживание можно выключить. MS>А вообще — искать по словам, типа "even-odd polygon fill algorithm
Кажется, я немного не так выразился. Дело в том, что у меня не известны координаты вершин, т.е. входные данные — бинарное изображение (точнее даже Булева матрица, в которой 1 — белый, 0 — черный, закрасить надо нулями). Как тут мне быть?
Здравствуйте, Reunion, Вы писали:
R>Кажется, я немного не так выразился. Дело в том, что у меня не известны координаты вершин, т.е. входные данные — бинарное изображение (точнее даже Булева матрица, в которой 1 — белый, 0 — черный, закрасить надо нулями). Как тут мне быть?
Насколько я помню это называется алгоритмом сканирующих линий.
В твой случае:
Идёшь слева на право по каждой горизонтальной линии.
Когда встретишь чёрную точку начинаешь за собой закрашивать.
Когда встретишь чёрную точку ещё раз — перестаёшь.
Для линий толщиной больше 1 пикселя надо немного усложнить, но идея та же.
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, Reunion, Вы писали:
R>>Кажется, я немного не так выразился. Дело в том, что у меня не известны координаты вершин, т.е. входные данные — бинарное изображение (точнее даже Булева матрица, в которой 1 — белый, 0 — черный, закрасить надо нулями). Как тут мне быть?
A>Насколько я помню это называется алгоритмом сканирующих линий. A>В твой случае: A>Идёшь слева на право по каждой горизонтальной линии. A>Когда встретишь чёрную точку начинаешь за собой закрашивать. A>Когда встретишь чёрную точку ещё раз — перестаёшь. A>Для линий толщиной больше 1 пикселя надо немного усложнить, но идея та же.
Не уменя однопиксельные будут (это в программе, в которой я рисовал, по умолчанию так). Трабла в том, что могут быть горизонтальные границы и вершины и там уже не надо закрашивать после встречи черной точки. Как тут быть???
R>Не уменя однопиксельные будут (это в программе, в которой я рисовал, по умолчанию так). Трабла в том, что могут быть горизонтальные границы и вершины и там уже не надо закрашивать после встречи черной точки. Как тут быть???
Попробуй так:
a) Проходишь по горизонтали:
Если встречаешь чёрную точку, то запоминашь её позицию, находишь следующую -- закрашиваешь промежуток между ними.
b) Проходишь по вертикали:
Всё тоже самое.
с) Окончательно закрашиваешь только те участки, которые были закрашены при обоих проходах.
WinterMute wrote: > Попробуй так: > > a) Проходишь по горизонтали: > Если встречаешь чёрную точку, то запоминашь её позицию, находишь > следующую -- закрашиваешь промежуток между ними. > b) Проходишь по вертикали: > Всё тоже самое. > > с) Окончательно закрашиваешь только те участки, которые были закрашены > при обоих проходах.
Здравствуйте, raskin, Вы писали:
R>WinterMute wrote: >> Попробуй так: >> >> a) Проходишь по горизонтали: >> Если встречаешь чёрную точку, то запоминашь её позицию, находишь >> следующую -- закрашиваешь промежуток между ними. >> b) Проходишь по вертикали: >> Всё тоже самое. >> >> с) Окончательно закрашиваешь только те участки, которые были закрашены >> при обоих проходах.
R>И при этом не окружены незакрашенными.
Вот то, что получается...
Красные — шел по горизонтали,
Голубые — по вертикали (снизу вверх),
Фиолетовые — и там и там.
Как мне из этого получить то, что надо — т.е. не закрашены только 3 области (не считая фона) — в них больше всего белого цвета...
R>Вот то, что получается... R>
R>Красные — шел по горизонтали, R>Голубые — по вертикали (снизу вверх), R>Фиолетовые — и там и там.
R>Как мне из этого получить то, что надо — т.е. не закрашены только 3 области (не считая фона) — в них больше всего белого цвета...
Очевидно, проблема в том, что проходя по чёрной горизонтальной/вертикальной линии чётной длинны ты перестаёшь закрашивать последующие белые точки. Попробуй реагировать не на одну чёрную точку, а на всю их последовательность. Т.е. после первой чёрной полосы закрашиваешь последующую белую, после второй чппропускаешь следующую белую, и т.д.
Здравствуйте, WinterMute, Вы писали:
R>>Вот то, что получается... R>>
R>>Красные — шел по горизонтали, R>>Голубые — по вертикали (снизу вверх), R>>Фиолетовые — и там и там.
R>>Как мне из этого получить то, что надо — т.е. не закрашены только 3 области (не считая фона) — в них больше всего белого цвета...
WM>Очевидно, проблема в том, что проходя по чёрной горизонтальной/вертикальной линии чётной длинны ты перестаёшь закрашивать последующие белые точки. Попробуй реагировать не на одну чёрную точку, а на всю их последовательность. Т.е. после первой чёрной полосы закрашиваешь последующую белую, после второй чппропускаешь следующую белую, и т.д.
Так там так и сделано. Я еагирую на последовательность черных пикселей. Закрашиваю от одной последовательности до другой, потом пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает
Здравствуйте, Reunion, Вы писали:
R>Здравствуйте, WinterMute, Вы писали:
R>>>Вот то, что получается... R>>>
R>>>Красные — шел по горизонтали, R>>>Голубые — по вертикали (снизу вверх), R>>>Фиолетовые — и там и там.
R>>>Как мне из этого получить то, что надо — т.е. не закрашены только 3 области (не считая фона) — в них больше всего белого цвета...
WM>>Очевидно, проблема в том, что проходя по чёрной горизонтальной/вертикальной линии чётной длинны ты перестаёшь закрашивать последующие белые точки. Попробуй реагировать не на одну чёрную точку, а на всю их последовательность. Т.е. после первой чёрной полосы закрашиваешь последующую белую, после второй чппропускаешь следующую белую, и т.д.
R>Так там так и сделано. Я еагирую на последовательность черных пикселей. Закрашиваю от одной последовательности до другой, потом пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает
Ага, проблема в узлах: когда натыкаешься на узел не нужно чередовать режим рисования/не_рисования. Задача, как определить что мы попали в узел. Должно работать следующее: узел -- это группа пикселей, у которых по внешнему периметру прямоугольника, куда они вписаны, встречается более двух одиночных чёрных пикселей. Т.е. когда находишь чёрную точку, обходишь её по внешнему периметру, если на внешнем периметре встречаются только одиночные чёрные пиксели и их более двух, то это узел, если встречаюется несколько чёрных пикселей подряд, то добавляешь их в рассматриваемую область и начинаешь обходить по новому периметру -- так до тех пор, пока не выяснишь является ли рассматриваемая область узлом. Далее, таким-же образом, обходишь оставшиеся точки, исключая точки уже найденных узлов.
После того, как определишь все узлы, пройдись уже знакомым алгоритмом пропуская узлы (должно хватить даже одного прохода -- по горизонтали).
Здравствуйте, Reunion, Вы писали:
WM>>Очевидно, проблема в том, что проходя по чёрной горизонтальной/вертикальной линии чётной длинны ты перестаёшь закрашивать последующие белые точки. Попробуй реагировать не на одну чёрную точку, а на всю их последовательность. Т.е. после первой чёрной полосы закрашиваешь последующую белую, после второй чппропускаешь следующую белую, и т.д.
R>Так там так и сделано. Я еагирую на последовательность черных пикселей. Закрашиваю от одной последовательности до другой, потом пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает
Естественно, не хватает. Такая методика не различает две ситуации ("*" — граница, "+" — то, что "на самом деле" должно быть закрашено, "-" — что не должно быть закрашено):
Эвристика "если рядом есть закрашенные точки/нет закрашенных точек" выручает в такой ситуации, но можно придумать такие, что и она пролетает.
По-простому, похоже, не сделать. Если даже делать на простых контекстных правилах, то в любом случае нужна постобработка. Пример:
Как догадаться, что область "?" должна остаться пустой? (а кстати, должна ли? ) И вертикальное и горизонтальное сканирование говорит, что это внутренняя область...
Д.К. << RSDN@Home 1.1.4 stable rev. 510>>
Все на свете должно происходить медленно и неправильно...
Здравствуйте, Reunion, Вы писали:
R>Так там так и сделано. Я еагирую на последовательность черных пикселей. Закрашиваю от одной последовательности до другой, потом пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает
Пришла в голову еще одна мысль. Совсем с другого края. Раз изображение растровое, будем вовсю использовать flood fill. Можно заливать поочередно замкнутые области, учитывая направление границ для определения соседей. Для упрощения можно заранее залить фон каким-нибудь отдельным цветом.
Но! Задача сводится к раскраске планарного графа в 2 цвета, что, как известно, в общем случае невозможно. Поэтому идеального решения не существует, но для симпатичного представления "на вид" можно использовать эвристики. Например: при противоречии закрашиваем тем цветом, которого меньше всего среди соседей.
Хотя, сдается мне, полностью детерминированно можно раскрасить только после векторизации и полноценного применения even-odd, как предложил
Здравствуйте, conraddk, Вы писали:
C>Здравствуйте, Reunion, Вы писали:
R>>Так там так и сделано. Я еагирую на последовательность черных пикселей. Закрашиваю от одной последовательности до другой, потом пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает
C>Пришла в голову еще одна мысль. Совсем с другого края. Раз изображение растровое, будем вовсю использовать flood fill. Можно заливать поочередно замкнутые области, учитывая направление границ для определения соседей. Для упрощения можно заранее залить фон каким-нибудь отдельным цветом. C>Но! Задача сводится к раскраске планарного графа в 2 цвета, что, как известно, в общем случае невозможно. Поэтому идеального решения не существует, но для симпатичного представления "на вид" можно использовать эвристики. Например: при противоречии закрашиваем тем цветом, которого меньше всего среди соседей. C>Хотя, сдается мне, полностью детерминированно можно раскрасить только после векторизации и полноценного применения even-odd, как предложил
Здравствуйте, conraddk, Вы писали:
C>Естественно, не хватает. Такая методика не различает две ситуации ("*" — граница, "+" — то, что "на самом деле" должно быть закрашено, "-" — что не должно быть закрашено): C>
C>Эвристика "если рядом есть закрашенные точки/нет закрашенных точек" выручает в такой ситуации, но можно придумать такие, что и она пролетает. C>По-простому, похоже, не сделать. Если даже делать на простых контекстных правилах, то в любом случае нужна постобработка. Пример: C>
C>Как догадаться, что область "?" должна остаться пустой? (а кстати, должна ли? ) И вертикальное и горизонтальное сканирование говорит, что это внутренняя область...
У меня такого по ходу дела быть не может. Кривую рисует пользователь не отрывая карандаша — за один раз. Кривая всегда замкнута.
Reunion wrote: > R>>Так там так и сделано. Я еагирую на последовательность черных > пикселей. Закрашиваю от одной последовательности до другой, потом > пропускаю один промежуток, потом опять крашу... Чего-то тут не хватает > > C>Пришла в голову еще одна мысль. Совсем с другого края. Раз изображение > растровое, будем вовсю использовать flood fill. Можно заливать > поочередно замкнутые области, учитывая направление границ для > определения соседей. Для упрощения можно заранее залить фон каким-нибудь > отдельным цветом. > C>Но! Задача сводится к раскраске планарного графа в 2 цвета, что, как > известно, в общем случае невозможно. Поэтому идеального решения не > существует, но для симпатичного представления "на вид" можно > использовать эвристики. Например: при противоречии закрашиваем тем > цветом, которого меньше всего среди соседей. > C>Хотя, сдается мне, полностью детерминированно можно раскрасить только > после векторизации и полноценного применения even-odd, как предложил > <http://rsdn.ru/forum/Message.aspx?mid=1289220&only=1>
Здравствуйте, Reunion, Вы писали:
R>В моем случае можно всегда покрасить в два цвета — кривая рисуется пользователем не отрывая карандаша... Такую кривую можно.
А ну как он точно-точно проведет по одной и той же линии два раза? Или много раз?
Д.К. << RSDN@Home 1.1.4 stable rev. 510>>
Все на свете должно происходить медленно и неправильно...
Здравствуйте, conraddk, Вы писали:
C>Здравствуйте, Reunion, Вы писали:
R>>В моем случае можно всегда покрасить в два цвета — кривая рисуется пользователем не отрывая карандаша... Такую кривую можно. C>А ну как он точно-точно проведет по одной и той же линии два раза? Или много раз?
Это не важно. Чего получится то и получится. Нефиг по одному месту возить мышку... Не, реально, забей на этот случай.
Reunion wrote: >> > В моем случае можно всегда покрасить в два цвета — кривая рисуется >> > пользователем не отрывая карандаша... Такую кривую можно. > > R>А нельзя хранить дополнительную информацию о пути рисования? А то можно > R>ведь такого нарисовать.. > > Упс, , чего-то я вам сказать забыл... Можно. Есть последовательность > точек, которую рисует пользователь... Не бейте...
Так тогда у Вас есть набор отрезков в пару точек, проведённых
пользователем. И пересечения считаются легко и непринуждённо всегда.
Находите все куски кривой, проходящие через задетые чёрные клетки. После
этого достаточно посчитать число отрезков, уходящих вверх (не вниз) из
задетой чёрной клетки и добавить его к счётчику чётности. Закраска — по
чётности.
Здравствуйте, raskin, Вы писали:
R>Reunion wrote: >>> > В моем случае можно всегда покрасить в два цвета — кривая рисуется >>> > пользователем не отрывая карандаша... Такую кривую можно. >> >> R>А нельзя хранить дополнительную информацию о пути рисования? А то можно >> R>ведь такого нарисовать.. >> >> Упс, , чего-то я вам сказать забыл... Можно. Есть последовательность >> точек, которую рисует пользователь... Не бейте...
R>Так тогда у Вас есть набор отрезков в пару точек, проведённых R>пользователем. И пересечения считаются легко и непринуждённо всегда. R>Находите все куски кривой, проходящие через задетые чёрные клетки. После R> этого достаточно посчитать число отрезков, уходящих вверх (не вниз) из R>задетой чёрной клетки и добавить его к счётчику чётности. Закраска — по R>чётности.
Reunion wrote: > R>Так тогда у Вас есть набор отрезков в пару точек, проведённых > R>пользователем. И пересечения считаются легко и непринуждённо всегда. > R>Находите все куски кривой, проходящие через задетые чёрные клетки. После > R> этого достаточно посчитать число отрезков, уходящих вверх (не вниз) из > R>задетой чёрной клетки и добавить его к счётчику чётности. Закраска — по > R>чётности. > > Можно подробнее, а то я что-то не понял.
Не вопрос. Можно на полупаскаль?
const l=...;
const n=...;
moves: array [1..l] of record
x,y:integer;
end;
field: array[1..n,1..n] of integer; {сейчас — все нули}
i,j,k:integer;
{Поле заполняется по следующим правилам:
0 — пусто
1 — пусто и закрашено
2 — чёрная точка, надо менять чётность
3 — чёрная точка, не надо менять чётность}
for k:=1 to l-1 do begin
(i,j):=(moves[k].x,moves[k].y);
field[i,j] :or= 2;
if moves[k].y>moves[k+1].y then begin
(i,j):=(moves[k+1].x,moves[k+1].y);
field[i,j] :xor= 1;
end else if moves[k].y<moves[k+1].y then begin
field[i,j] :xor= 1;
end;
end;
А после этого — просто Ваш проход на чётность, в каждой клетке написано,
надо ли менять чётность. Другими словами, имеется самопересекающаяся
ломаная. При проходе по строке пустим луч на уровне 1/4 от верхнего края
(мы знаем, что вся пустая клетка целиком в одной области, поэтому всё
равно, где пускать луч) и считаем пересечения с ним с учётом кратности
(это делается легко).
, чего-то я вам сказать забыл... Можно. Есть последовательность точек, которую рисует пользователь... Не бейте...
) И вертикальное и горизонтальное сканирование говорит, что это внутренняя область...
Так что мне делать, в какой последовательности 
