Посмотри http://www.arbuz.uz/y_kv_k.html, правда там про неленейные поверхности, но смысл тот же.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > "Физическая карта". обрисовка линий высоты. |
| Автор: neutrino 18.7.2005, 11:39 |
| Приветствую! Вот такая задача: есть объекты прямоугольной формы в поле N на M. Нужно сделать из них как-бы плоскогорья. Т.е. обрисовать сначала одной линией (в 1 пиксель) каждый объект, потом еще одной линией и т.д. Каждая линия соответствует высоте, причем чем линия ближе к границе объекта, тем больше высота, которую она определяет. Ниже привел иллюстрацию к заданию. Вот так выглядят объекты: http://neutrino.pochta.ru/Mapalg/first.jpg А вот такую карту надо сделать. Тут более светлый цвет соответствует низкой высоте и наоборот. http://neutrino.pochta.ru/Mapalg/second.jpg Как за более-менее небольшое время создать такую карту? |
| Автор: ~FoX~ 18.7.2005, 13:27 |
| neutrino Оптимизировать преобразование Хафа. |
| Автор: ~FoX~ 18.7.2005, 14:26 |
| Наверное, это я широко шагнул........... Посмотри http://www.arbuz.uz/y_kv_k.html, правда там про неленейные поверхности, но смысл тот же. |
| Автор: neutrino 18.7.2005, 14:35 | ||
|
| Автор: ~FoX~ 18.7.2005, 14:44 | ||
| neutrino Странно..........  http://www.yandex.ru/yandsearch?stype=www&nl=0&text=%EF%E5%ED%E0+%EF%F3%E7%FB%F0%E8+VB -
|
| Автор: Alex101 19.7.2005, 10:51 |
| Мне кажется, все намного проще. Каждая клетка (с координатами x,y) имеет свою высоту... Соответственно, нужно заполнить двумерный массив. Высоты объектов, как я понимаю, одинаковые (да и необязательно это). Дальше просто - определили точку с необходимой высотой, начинаем от нее "рисовать"... Или я неправильно понял условия? |
| Автор: neutrino 19.7.2005, 17:43 |
| ~FoX~ Спасибо, но тот алгоритм не очень подходит для моей задачи. До первого поста я его обмозговал и понял, что это самое наивное решение. Дело в том, что я немного переврал с иллюстрацией. Там поля, которые белые тоже имеют разные высоты (в соответствии от расстояния до объектов, естественно). Другими словами, у пузырьков в той статье есть "конец" - это когда цвет полностью переходит в черный и расчет для настоящего пузырька прекращается. У меня же такого конца нет, и поэтому сложность будет как там помножить на кол-во объектов, а это слишком много. Добавлено @ 17:45 "Конец" = конечный радиус пузырька (приим. авт. ред.) Добавлено @ 17:46 Alex101, мне почему-то кажется, что твоя идея идентична той, что в статье (см. ответ Фокса). Если это так, то см. ответ для Фокса, если нет - поясни свое решение. |
| Автор: maxim1000 19.7.2005, 18:37 | ||
| можно применить линейный фильтр например берем гауссовское распределение (просто оно хорошо выглядит, а вообще можно другое какое-нибудь) дискретизуем его с нужной дискретностью (т.е. вычисляем значения в точке) и применяем этот фильтр... Добавлено @ 18:42 в коде это может выглядеть, например, так:
|
| Автор: Alex101 20.7.2005, 09:42 |
| neutrino, а у тебя карта дискретная? (одна клетка - это одна высота?) В каком виде представлены исходные данные? |
| Автор: neutrino 20.7.2005, 09:49 |
| Alex101, да. |
| Автор: Alex101 20.7.2005, 09:53 | ||
 А исходные данные как представлены? |
| Автор: Alex101 20.7.2005, 10:12 |
| Можно попробовать вот что... "Зацепляешь" первый объект и начинаешь "обрисовывать" его (при этом другие объекты не трогаешь). "Зацепляешь" следующий объект и делаешь вот что: если поле белое, то, в зависимости от расстояния, закрашиваешь клетку иначе сравниваешь цвет, которым надо закрасить для текущего объекта с уже закрашенным цветом. Если новый цвет "выше", то закрашиваешь, иначе оставляешь. Алгоритм и его реализация зависят от максимальных значений N и M. |
| Автор: ~FoX~ 20.7.2005, 10:27 |
| Alex101 Ну вот и прооптимизировали Хафа Интересно, а объекты именно прямоугольной (правильной) формы? |
| Автор: Alex101 20.7.2005, 10:34 | ||||
Да! При выборе уже второго объекта, как я понимаю, все поле уже будет закрашено. Так что надо сравнивать...
Ну, в этой задаче распознавать ничего не надо, объекты, как я понимаю, заданы однозначно (цветом, допустим). |
| Автор: neutrino 20.7.2005, 13:03 | ||
| Привет! Alex101 Боюсь показаться назойливым, но все же: я именно о таком алгоритме и подумал. У него сложность: м*н*(кол-во объектов). Видимо быстрее нельзя... Ладно, вопрос, наверное стоит снять... ~FoX~
Да. maxim1000, извини, но не понял твою идею... |
| Автор: maxim1000 20.7.2005, 13:24 | ||||
ну представим, что вместо каждой точки у нас холмик можно посмотреть на этот процесс и так: 1. представляем рисунок в виде суммы "единичных" рисунков - т.е. имеющих только одну закрашенную точку 2. заменяем в каждом рисунке эту закрашенную точку на тот самых холмик 3. в качестве результата берем сумму таких измененных рисунков а вообще - это обычная цифровая фильтрация, только в 2d попробуй поискать - в Интернете наверняка найдется у Alex101'а, насколько я понял то же самое, только вместо + max...
скорее всего не получится: для определения цвета каждой точки надо знать некоторую информацию обо всех объектах (хотя бы для того, чтобы не принимать их во внимание) |
| Автор: ~FoX~ 20.7.2005, 14:01 | ||
Все просто - "чем выше категория, тем меньше вероятность"...... Но ИМХО выйгрышь получиться только при достаточно больших объемах изначальных данных. Добавлено @ 14:02 Ой.....не посмотрел, что вторая страница есть |
| Автор: Alex101 20.7.2005, 14:40 | ||
Не, скорее всего, N*M*V (V - количество градаций высот). Какая идея... Текущий цвет - (черный-1). Цвет точки - черный. Делаем цикл по высоте (от большей к меньшей). Видим точку и, если можно, то закрашиваем соседние с ней текущим цветом. Меняем цвет точки (текущий). |
| Автор: neutrino 20.7.2005, 21:44 |
| Спасибо всем участникам дисскуссии. Я немного подумаю, потом скажу, что сделаю. |
| Автор: Romikgy 22.7.2005, 09:04 |
| А не проще будет , отдельно посчитать высоты для каждого холмика, а потом сложит все холмики на одном поле??? |
| Автор: Alex101 22.7.2005, 10:19 | ||
Нет, по сравнению с моей идеей сложнее. |