Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.117.152.251] |
|
Сообщ.
#1
,
|
|
|
Ищу (думаю о) алгоритме нахождения всех ям и вершин (локальных) для некоторой поверхности представленной двухмерным массивом величиной высот точек от 0 до 255 (байт в общем)
|
Сообщ.
#2
,
|
|
|
В таком случае придется точно определить, что есть яма и вершина ("распад" высот). Например в массиве
10 10 10 10 10 9 11 10 10 10 10 10 10 10 10 10 можно ли число 9 отнести к яме, а 11 к вершине??? А сам алгоритм можно свести к простому проходу по массиву по строчно и проверкой на ближлежащие высоты. Например для данного случая пройдя по первой строчке мы не заметим различия в высотах. На второй строчке наткнемся на число 9 < всех остальных и предположим, что это искомая "яма". Пройдясь теперь "вверх" и "вниз" по столбцу с 9, найдем, что 9 < и остальных чисел, то есть наше предположение подтвердилось. Другой вариант: Находим во всем массиве среднее значение высот (обычное арифметическое). Получаем своеобразный "уровень (плоскость)" поверхности. И вычитаем его из всех высот. Часть чисел станут отрицательными - "ямы", а часть останется положительными - "вершины". Первый способ приводит к большому количественному анализу, но довольно точен. А второй способ приносит некоторые погрешности в точности определения. Но можно объединить их оба. ;D ;D ;D |
Сообщ.
#3
,
|
|
|
Дадим тогда определения для (локальных) ям и вершин:
Ямой называется точка высота (относительно нуля) которой меньше всех окружающих ее точек (в количестве 8 штук). Вершина это точка высота которой превышает высоту всех окружающих ее (8) точек. Точки на являющиеся ямой или вершиной являются точками склонов. Одним из вариантов склонов могут быть плато - когда высоты у некоторого сообществе окружающих точек равны. |
Сообщ.
#4
,
|
|
|
Действительно самым простым является алгоритм просмотра окружения около определенной точки, и если эта точка имеет наименьшее (наибольшее) значение относительно окружения, то это и есть минимум (максимум).
|
Сообщ.
#5
,
|
|
|
Есть такой алгоритм - нахождение аномальных значений с кокайто базы данных (массив например). Задается степень точности. Он лучше тем, что универсальней, но требует познаний в теории вероятностей.
ЗЫ. Яма и гора - в какой-то степени аномальные значения. |
Сообщ.
#6
,
|
|
|
Математически самый быстый - градиентный спуск, но он только локальные экстремумы ищет.
Стоп... идея пришла - можно применить алгоритм быстрой сортировки и отсортировать массив значений с сохранением ссылок - и вперед. |
Сообщ.
#7
,
|
|
|
А к чему применять сортировку? К вершинам? Так их выделить надо сначала. Простым перебором удалось найти вершины и ямы, но тут новая напасть пришла - надо определять точки перегиба, но не поверхности, а линии, точнее среза поверхности по оси y...
|