Подскажите как залить произвольную замкнутую область, если не известна ни одна точка внутри этой области и область состои не из отрезков, а просто набор точек? Точнее мне хочется узнать можно ли, как-нибудь залить эту область, не находя точки внутри этой области и не разбивая границу области на отрезки?
Здравствуйте, debjet, Вы писали:
D>Подскажите как залить произвольную замкнутую область, если не известна ни одна точка внутри этой области и область состои не из отрезков, а просто набор точек? Точнее мне хочется узнать можно ли, как-нибудь залить эту область, не находя точки внутри этой области и не разбивая границу области на отрезки?
Не совсем понял, как может область замкнутой, но при этом состоять из точек?
1. Либо из этих точек формируется отрезки.
2. Либо эти точки соединяются последовательно и получается замкнутая область.
Точку ИМХО можно и не находить, достаточно знать одну из пограничных точек.
Насчёт алгоритма посмотри статью на www.codenet.ru, по-моему, раздел Алгоритмы. Статья называется, что-то про волновой метод нахождения кратчайшего пути, там алгоритм для нахождения пути в стратегиях, но (кстати, об этом говорит и автор) немного его модифицировав можно использовать для закраски замкнутой области.
Если сам не разберёшься, пиши постараюсь помочь.
Здравствуйте, debjet, Вы писали:
D>Подскажите как залить произвольную замкнутую область, если не известна ни одна точка внутри этой области и область состои не из отрезков, а просто набор точек? Точнее мне хочется узнать можно ли, как-нибудь залить эту область, не находя точки внутри этой области и не разбивая границу области на отрезки?
Формулировка довольно туманна. Что значит "область состои не из отрезков, а просто набор точек"? Если граница области состоит из точек одного цвета (вариант: состоит из точек цвета, отличного от цвета закрашиваемой области), то есть довольно простой алгоритм. Но для него необходимо знать хотя бы одну точку внутри закрашиваемой области. Это примерно как в графическом редакторе: для заливки нужно кликнуть куда-нибудь инструментом "заливка". Если неизвестно ни одной точки, то вообще неясно, что заливать.
псевдокод:
void fill(int x, int y, int color)
{
// если точка внутри областиif(get_color(x,y)!= color)
{
// закрашиваем точку
set_color(x, y, color);
// находим соседей (рекурсивно)
fill(x-1, y, color);
fill(x, y+1, color);
fill(x+1, y, color);
fill(x, y-1, color);
}
}
Получается рекурсия, и точки проверяются по несколько раз. Это можно устранить, организуя заливку по скан-линиям. То есть можно на каждой подходящей точке сразу заливать влево и вправо "до упора". А когда встретилась граница, добавлять ее координаты в список для последующей обработки.
Если не ошибаюсь, метод описан в книге Роджерса, "Алгоритмические основы машинной графики".
Примерно так работает FloodFill.
в этой матрице значение [0, 1]. 1 — соответственно граница области которую нужно закрасить(область замкнута — это известно). Задача состоит в том чтобы закрасить область ограниченную 1-цами. Как вы понимаете точку внутри этой области мне не дают и отрезков у меня никаких нету. единственное только мне известны две точки на границе области.
Желаю удачи!!!
Re[2]: Растровый алгоритм закраски замкнутой области
А ты уверен, что по диагонали ограничивать можно, например, в твоём рисунке не понятно считать ли 0 отмеченный ! в области, т.к. он находится за непрерывной диагональю из 1.
Здравствуйте, debjet, Вы писали:
D>Подскажите как залить произвольную замкнутую область, если не известна ни одна точка внутри этой области и область состои не из отрезков, а просто набор точек? Точнее мне хочется узнать можно ли, как-нибудь залить эту область, не находя точки внутри этой области и не разбивая границу области на отрезки?
Если гарантируется, что область замкнута, то можно попробовать следующую схему: взять рядом с произвольной точкой границы два пикселя и проверить, какой из них лежит внутри. Алгоритм проверки смотри в этом форуме. После этого залить область, пользуя найденный внутренний пиксел, как затравку.
... << RSDN@Home 1.1 beta 1 >>
Re[2]: Растровый алгоритм закраски замкнутой области
Идешь по каждой строке матрицы (слева на право, например) и анализируешь изменение текущего символа, по сравнению с предыдущим (для самого левого — предыдущий символ =0 ). После смены '1' -> '0' меняешь все 0 на 1, пока не встретишь смену '0'->'1'. После этого снова ждешь 1->0, и так до конца строки. То же для остальных строк.
Можно идти и по столбцам, не мне как-то непривычно...
DS>... После этого снова ждешь 1->0, и так до конца строки. ...
На самом деле первая смена 1->0 бедет означать незаполненную область. Ждать надо вторую.
Re[3]: Растровый алгоритм закраски замкнутой области
Вот и я тож так хотел сначало делать, но проблема возникает когда мы натыкаемся на последовательность 1-ц.
Я пока не вижу иного выхода, как разбивать всю границу на отрезки и уже проверять для них. Но хотелось бы конечно как проще.
День добрый. Можно попробовать так (тоже по строкам или по столбцам).
1. Ищем первый пиксел с "1".
1.1. Если не нашли, то смещаемся на другую строку/столбец, и далее п.1.
2. Проверяем следующий пиксел на значение:
2.1. Если "1", то ищем далее по строке/столбцу первый "0":
2.1.1. Если нашли, то делаем его началом строки и выполняем п.1
2.1.2. Если не нашли, то смещаемся на другую строку/столбец, и далее п.1.
2.2. Если "0", то запоминаем последний "1" как входной.
3. Ищем далее пиксел с "1".
3.1. Если нашли, то запоминаем его как выходящий и красим все "0" между ним и входным. Далее п.1.
3.2. Если не нашли, то смещаемся на следующую строку/столбец, и далее п.1.
Здравствуйте, Max Lichmanov, Вы писали:
ML>День добрый. Можно попробовать так (тоже по строкам или по столбцам). ML>1. Ищем первый пиксел с "1". ML>1.1. Если не нашли, то смещаемся на другую строку/столбец, и далее п.1. ML>2. Проверяем следующий пиксел на значение: ML>2.1. Если "1", то ищем далее по строке/столбцу первый "0": ML>2.1.1. Если нашли, то делаем его началом строки и выполняем п.1 ML>2.1.2. Если не нашли, то смещаемся на другую строку/столбец, и далее п.1. ML>2.2. Если "0", то запоминаем последний "1" как входной. ML>3. Ищем далее пиксел с "1". ML>3.1. Если нашли, то запоминаем его как выходящий и красим все "0" между ним и входным. Далее п.1. ML>3.2. Если не нашли, то смещаемся на следующую строку/столбец, и далее п.1.
ML>С уважением, ML>Макс Личманов.
Здравствуйте, debjet, Вы писали:
D>Подскажите как залить произвольную замкнутую область, если не известна ни одна точка внутри этой области и область состои не из отрезков, а просто набор точек? Точнее мне хочется узнать можно ли, как-нибудь залить эту область, не находя точки внутри этой области и не разбивая границу области на отрезки?
можно я реализовал
могу дать исходники на Delphi
если ещё нужно пиши мыло
А если приложить еще немножечко умственного мозга, то можно обобщить, считая не отдельные единицы, а непрерывные последовательности из единиц и переключаясь fill/no_fill по ним.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
