| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Все ямы и вершины поверхности |
| Автор: adasoft 07.09.02, 12:50 |
| Ищу (думаю о) алгоритме нахождения всех ям и вершин (локальных) для некоторой поверхности представленной двухмерным массивом величиной высот точек от 0 до 255 (байт в общем) |
| Автор: GrAnd 08.09.02, 11:08 |
| В таком случае придется точно определить, что есть яма и вершина ("распад" высот). Например в массиве 10 10 10 10 10 9 11 10 10 10 10 10 10 10 10 10 можно ли число 9 отнести к яме, а 11 к вершине??? А сам алгоритм можно свести к простому проходу по массиву по строчно и проверкой на ближлежащие высоты. Например для данного случая пройдя по первой строчке мы не заметим различия в высотах. На второй строчке наткнемся на число 9 < всех остальных и предположим, что это искомая "яма". Пройдясь теперь "вверх" и "вниз" по столбцу с 9, найдем, что 9 < и остальных чисел, то есть наше предположение подтвердилось. Другой вариант: Находим во всем массиве среднее значение высот (обычное арифметическое). Получаем своеобразный "уровень (плоскость)" поверхности. И вычитаем его из всех высот. Часть чисел станут отрицательными - "ямы", а часть останется положительными - "вершины". Первый способ приводит к большому количественному анализу, но довольно точен. А второй способ приносит некоторые погрешности в точности определения. Но можно объединить их оба. ;D ;D ;D |
| Автор: adasoft 08.09.02, 12:39 |
| Дадим тогда определения для (локальных) ям и вершин: Ямой называется точка высота (относительно нуля) которой меньше всех окружающих ее точек (в количестве 8 штук). Вершина это точка высота которой превышает высоту всех окружающих ее (8) точек. Точки на являющиеся ямой или вершиной являются точками склонов. Одним из вариантов склонов могут быть плато - когда высоты у некоторого сообществе окружающих точек равны. |
| Автор: adasoft 09.09.02, 07:40 |
| Действительно самым простым является алгоритм просмотра окружения около определенной точки, и если эта точка имеет наименьшее (наибольшее) значение относительно окружения, то это и есть минимум (максимум). |
| Автор: Sanya 09.09.02, 11:58 |
| Есть такой алгоритм - нахождение аномальных значений с кокайто базы данных (массив например). Задается степень точности. Он лучше тем, что универсальней, но требует познаний в теории вероятностей. ЗЫ. Яма и гора - в какой-то степени аномальные значения. |
| Автор: Konstantin_N 10.09.02, 14:00 |
| Математически самый быстый - градиентный спуск, но он только локальные экстремумы ищет. Стоп... идея пришла - можно применить алгоритм быстрой сортировки и отсортировать массив значений с сохранением ссылок - и вперед. |
| Автор: adasoft 10.09.02, 14:38 |
| А к чему применять сортировку? К вершинам? Так их выделить надо сначала. Простым перебором удалось найти вершины и ямы, но тут новая напасть пришла - надо определять точки перегиба, но не поверхности, а линии, точнее среза поверхности по оси y... |