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

Вот такая задача: есть объекты прямоугольной формы в поле 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, извини, но не понял твою идею...