Приветствую!

Вот такая задача: есть объекты прямоугольной формы в поле N на M. Нужно сделать из них как-бы плоскогорья. Т.е. обрисовать сначала одной линией (в 1 пиксель) каждый объект, потом еще одной линией и т.д. Каждая линия соответствует высоте, причем чем линия ближе к границе объекта, тем больше высота, которую она определяет. Ниже привел иллюстрацию к заданию.

Вот так выглядят объекты:



А вот такую карту надо сделать. Тут более светлый цвет соответствует низкой высоте и наоборот.



Как за более-менее небольшое время создать такую карту?

neutrino
Оптимизировать преобразование Хафа.

Наверное, это я широко шагнул...........
Посмотри тут, правда там про неленейные поверхности, но смысл тот же.

Это сообщение отредактировал(а) ~FoX~ - 18.7.2005, 14:27

Цитата

Посмотри тут,

neutrino
Странно..........
Первая ссылка -

Цитата

на Арбузе Компьютерные вести онлайн

Это сообщение отредактировал(а) ~FoX~ - 18.7.2005, 14:45

Мне кажется, все намного проще.
Каждая клетка (с координатами x,y) имеет свою высоту...
Соответственно, нужно заполнить двумерный массив.
Высоты объектов, как я понимаю, одинаковые (да и необязательно это).
Дальше просто - определили точку с необходимой высотой, начинаем от нее "рисовать"...

Или я неправильно понял условия?

~FoX~ Спасибо, но тот алгоритм не очень подходит для моей задачи. До первого поста я его обмозговал и понял, что это самое наивное решение. Дело в том, что я немного переврал с иллюстрацией. Там поля, которые белые тоже имеют разные высоты (в соответствии от расстояния до объектов, естественно). Другими словами, у пузырьков в той статье есть "конец" - это когда цвет полностью переходит в черный и расчет для настоящего пузырька прекращается. У меня же такого конца нет, и поэтому сложность будет как там помножить на кол-во объектов, а это слишком много.
Добавлено @ 17:45
"Конец" = конечный радиус пузырька (приим. авт. ред.)
Добавлено @ 17:46
Alex101, мне почему-то кажется, что твоя идея идентична той, что в статье (см. ответ Фокса). Если это так, то см. ответ для Фокса, если нет - поясни свое решение.

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

Код

const int XSize=100; const int YSize=100; double Gauss(double x,double y) {   return exp(-(x*x+y*y)/2);//вообще-то надо еще множитель, чтобы это плотность была, но в нашем случае важна только форма, да и в центре значение не изменится... } void Smooth(double **source,double **destination) //предполагается, что вся память выделена как надо и в destination все нули {   for(int sx=0;sx<XSize;sx++)     for(int sy=0;sy<YSize;sy++)       for(int dx=0;dx<XSize;dx++)         for(int dy=0;dy<YSize;dy++)           destination[dx][dy]+=source[sx][sy]*Gauss(sx-dx,sy-dy); }

Это сообщение отредактировал(а) maxim1000 - 19.7.2005, 18:42

neutrino, а у тебя карта дискретная? (одна клетка - это одна высота?)
В каком виде представлены исходные данные?

Alex101, да.

Цитата(neutrino @ 20.7.2005, 09:49)

да.

А исходные данные как представлены?

Можно попробовать вот что...
"Зацепляешь" первый объект и начинаешь "обрисовывать" его (при этом другие объекты не трогаешь).
"Зацепляешь" следующий объект и делаешь вот что:
если поле белое, то, в зависимости от расстояния, закрашиваешь клетку
иначе сравниваешь цвет, которым надо закрасить для текущего объекта с уже закрашенным цветом.
Если новый цвет "выше", то закрашиваешь, иначе оставляешь.

Алгоритм и его реализация зависят от максимальных значений N и M.

Это сообщение отредактировал(а) Alex101 - 20.7.2005, 10:14

Alex101
Ну вот и прооптимизировали Хафа

Интересно, а объекты именно прямоугольной (правильной) формы?

Цитата(Alex101 @ 20.7.2005, 10:12)

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

Да!
При выборе уже второго объекта, как я понимаю, все поле уже будет закрашено.
Так что надо сравнивать...

Цитата

Ну вот и прооптимизировали Хафа

Ну, в этой задаче распознавать ничего не надо, объекты, как я понимаю, заданы однозначно (цветом, допустим).

Привет!

Alex101
Боюсь показаться назойливым, но все же: я именно о таком алгоритме и подумал. У него сложность: м*н*(кол-во объектов). Видимо быстрее нельзя... Ладно, вопрос, наверное стоит снять...


~FoX~

Цитата

Интересно, а объекты именно прямоугольной (правильной) формы?

Да.

maxim1000, извини, но не понял твою идею...

Цитата(neutrino @ 20.7.2005, 11:03)

maxim1000, извини, но не понял твою идею...

ну представим, что вместо каждой точки у нас холмик
можно посмотреть на этот процесс и так:
1. представляем рисунок в виде суммы "единичных" рисунков - т.е. имеющих только одну закрашенную точку
2. заменяем в каждом рисунке эту закрашенную точку на тот самых холмик
3. в качестве результата берем сумму таких измененных рисунков
а вообще - это обычная цифровая фильтрация, только в 2d
попробуй поискать - в Интернете наверняка найдется
у Alex101'а, насколько я понял то же самое, только вместо + max...

Цитата

Боюсь показаться назойливым, но все же: я именно о таком алгоритме и подумал. У него сложность: м*н*(кол-во объектов). Видимо быстрее нельзя...

скорее всего не получится: для определения цвета каждой точки надо знать некоторую информацию обо всех объектах (хотя бы для того, чтобы не принимать их во внимание)

Цитата(neutrino @ 20.7.2005, 14:03)

maxim1000, извини, но не понял твою идею...

Все просто - "чем выше категория, тем меньше вероятность"......
Но ИМХО выйгрышь получиться только при достаточно больших объемах изначальных данных.

Добавлено @ 14:02
Ой.....не посмотрел, что вторая страница есть

Цитата(neutrino @ 20.7.2005, 13:03)

У него сложность: м*н*(кол-во объектов). Видимо быстрее нельзя...

Не, скорее всего, N*M*V (V - количество градаций высот).
Какая идея...

Текущий цвет - (черный-1).
Цвет точки - черный.
Делаем цикл по высоте (от большей к меньшей).
Видим точку и, если можно, то закрашиваем соседние с ней текущим цветом.
Меняем цвет точки (текущий).

Это сообщение отредактировал(а) Alex101 - 20.7.2005, 14:41

Спасибо всем участникам дисскуссии. Я немного подумаю, потом скажу, что сделаю.

А не проще будет , отдельно посчитать высоты для каждого холмика, а потом сложит все холмики на одном поле???

Цитата(Romikgy @ 22.7.2005, 09:04)

отдельно посчитать высоты для каждого холмика, а потом сложит все холмики на одном поле???

Нет, по сравнению с моей идеей сложнее.