Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Поиск локального максимума


Автор: Graf Zeppelin 2.10.2004, 18:36
Допустим, есть карта местности, хранящаяся в двумерном массиве. Элементами массива являются высоты. Известно число холмов на карте, надо найти их координаты.

Автор: cardinal 2.10.2004, 19:04
1. Нашел максимальную высоту.
2. Копируешь координаты X и Y всех элементов с данной высотой в другой массив и одновременно удаляешь эти элементы из первого (думаю тот факт, что один из соседних холмов может быть такой же высоты это не проблема, но это думаю от масштаба карты зависит)
3. Находишь минимальный и максимальный X во втором массиве
4. Находишь минимальный и максимальный Y во втором массиве
5. Анализируя эти значения получаешь координаты холма (левый верхний и правый нижний углы)
Цитата(Graf @ 2.10.2004, 17:36)
Известно число холмов на карте

Повторяешь все что написано число холмов раз.

Я торопился и может где-то допустил логическую ошибку...

Автор: dm9 2.10.2004, 21:36
cardinal, ИМХО, ты не прав. Так как после удаления вершины самого высокого холма, останется срез этой вершины, плато, если хочешь biggrin.gif И оно может оказаться самым высоким.

Graf Zeppelin, а посмотреть поведение функции в окрестности нельзя? wink.gif Типа, проверяем элемент (x, y). Если
(x-1, y)
(x+1, y)
(x, y-1)
(x, y+1)
(x-1, y-1)
(x-1, y+1)
(x+1, y-1)
(x+1, y+1)
меньше, то это максимум, сто пудов smile.gif
Только проблема в том, что могут быть не интересующие нас маленькие флуктуации высоты. Наверное, затем и дано число холмов... Тут надо определять площадь, сортировать эти холмы по ней, ещё вопрос - если холм разветвляется вверху на два пика - считать за два, или за один. Надо дать чёткое определение холма... интересная задача. В общем, вопрос к автору вопроса: "каково чёткое определение холма".
Добавлено @ 21:41
cardinal, сорри, я сначала не так понял твой алгоитм. Но сейчас перечитал, понял что я вообще его не понимаю. bored.gif

Автор: Graf Zeppelin 3.10.2004, 10:06
Я изначально хотел сделать "наводнение" и скрывть все постепенно под "водой", пока не отанется n несвязанных областей, но это будет долго :)

Автор: maxim1000 3.10.2004, 10:41
Цитата
Я изначально хотел сделать "наводнение" и скрывть все постепенно под "водой", пока не отанется n несвязанных областей, но это будет долго smile.gif

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

Автор: Graf Zeppelin 3.10.2004, 10:58
Цитата(maxim1000 @ 3.10.2004, 10:41)
а по-моему, не так уж и долго...
уровень воды нужно выбирать бисекцией
для определения количества несвязных областей нужен один проход

Можно чуть поподробнее. Несвязанность обределяется заливкой, а бисекция оценивает > либо <= n. Правильно?

Автор: maxim1000 3.10.2004, 13:45
количество несвязных областей определяется так:
1. смотрим на первую строку: считаем количество непрерывных закрашенных строк - это будет наше количество несвязанных областей (пока, потом будем изменять)
2. смотрим на следующую строку и анализируем ее вместе с предыдущей:
2.1. если две области объединились - уменьшаем их количество на один
2.2. если появилась новая область - увеличиваем количество на один
3. берем следующую строку и переходим на (2)
Добавлено @ 13:46
Цитата
бисекция оценивает > либо <= n. Правильно?

да...

Автор: LuckLess 3.10.2004, 14:22
Цитата(Graf @ 3.10.2004, 10:06)
Я изначально хотел сделать "наводнение" и скрывть все постепенно под "водой", пока не отанется n несвязанных областей, но это будет долго smile.gif

лучше наоборот сразу все скрыть под водой , а потом постепенно опускать уровень воды имхо..

Автор: cardinal 3.10.2004, 22:11
dm9, да, согласен. Это был тупой вариант решения проблемы smile.gif. Немного пораскинув мозгами (помните да анекдот про Штирлица smile.gif) я придумал следующее:

Мы ищем самую высокую точку и засовываем ее в какой-нибудь массив X. От нее мы рекурсивно во все стороны запускаем след. процедуру, которая если высота точки <= самой наибольшей высоты заносит и ее в этот массив X. Таким образом мы вычислим один холм (все точки одного холма). (Если точка рядом с проверяемой выше проверяемой, то это начало другого холма и она не заносится в массив X).
Теперь мы ищем опять наивысшую точку на карте, но уже игнорируя те которые сидят в массиве X. Таким образом мы находим наивысшую точку следующего холма. Точки этого холма мы также занесем в массив X описанным выше образом и в следующий раз (при поиске наивысшей точки третьего холма) мы их тоже проигнорируем.
Так мы вычислим пять холмов и их наивысшие точки и будут координатами холмов.
Позже алгоритм может быть улучшен учитывая, что рядом с наивысшей точкой холма могут быть точки с той же высотой. Тогда нам надо будет высчитать их среднюю координату и она и будет координатой холма.

Вот... Если объяснил фигово, то скажите - я напишу еще раз. Может получится лучше... smile.gif

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)