Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Подсчет пятен

Автор: Mephisto 1.10.2003, 15:55

Если кто может помочь алгоритмом, то заходите http://forum.vingrad.ru/index.php?act=ST&f=3&t=12231.

Автор: neutrino 1.10.2003, 17:28

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

Все, что касается алгоритмики, остается в этом форуме.

В твоем случае можно применить алгоритм Дийкстра. Помечать каждое пятно, скажем цифрой -1. И искать следующую точку с цифрой не равной -1 и не равной цифре фона. Например 0. Алгоритм в самом тупом виде может выглядеть так:

цикл I от 0 до (n-1)
цикл J от 0 до (m-1)
p[I,J]=-1 => следующая итерация цикла
p[I,J]=0 => следующая итерация цикла
Диикстра(I,J)
конец по J
конец по I

<Диикстра(целые И, Ж)>
Тут собственно алгоритм Дийкстра, только не нужно нумеровать шаги, а только писать в ячейках -1.

Но он медленно будет работать. Правда его можно хорошенько оптимизировать.

Автор: neutrino 1.10.2003, 17:36

А как картинку в эти цифры преобразовать, это зависит от постановки задачи. Например: какого цвета пятна и т.д.

Автор: Mephisto 1.10.2003, 17:42

Цитата

какого цвета пятна

Спаибо что ответил, но есть небольшая проблема. Ты меня поймешь если зайдешь на мою домашн. страничку и нажмешь ссылку http://grafitchem.narod.ru/Resize_of_Grafit.htm

Автор: stab 2.10.2003, 00:39

и что надо тут (http://grafitchem.narod.ru/Resize_of_Grafit.htm) найти? обведи в фотошопе

Автор: neutrino 2.10.2003, 08:16

Вот настряпал по моему алгоритму программку. Довольно быстро все работает. Я неучел тот момент, что когда я помечаю пятно, второй раз по нему я не прохожу. Теперь все нормально. Для определения пятна я задал такие условия:
1) ячейка должна быть ненулевой
2) значение меньше пяти

Как у тебя там определять относится ли точка к пятну, ты должен знать сам. В этом алгоритме также учтена возможность пятен с общей границей разного цвета. Вот код:

Цитата

#include <iostream.h>
const n=10, m=10;

int P[n][m]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,5,0,0,0,0,0},
{0,1,1,1,5,5,0,0,0,0},
{0,0,1,1,5,5,5,0,0,0},
{0,0,2,2,2,2,5,5,0,0},
{0,0,2,2,2,2,5,5,0,0},
{0,0,9,2,2,5,5,5,5,0},
{0,9,9,9,0,0,3,3,3,0},
{0,9,9,9,0,0,3,3,3,0},
{0,0,9,0,0,0,3,3,3,0}
};
int PCnt=0;

void Dijkstra(int i, int j, int V) {
if (P[i][j]==V) {
P[i][j]=-1;
Dijkstra(i, j-1, V);
Dijkstra(i+1, j, V);
Dijkstra(i, j+1, V);
Dijkstra(i-1, j, V);
}
}

void main() {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (P[i][j]>=5) continue;
if (P[i][j]==0) continue;
if (P[i][j]==-1) continue;
PCnt++;
Dijkstra(i,j,P[i][j]);
}
}
cout<<endl<<PCnt; //Number of pots
}

Автор: neutrino 2.10.2003, 08:23

Картинку посмотрел. Так что там пятна? Черное? Белое?

Возможно эту картинку придется немного поменять для этого алгоритма.

Автор: Mephisto 2.10.2003, 18:00

Цитата

и что надо тут (http://grafitchem.narod.ru/Resize_of_Grafit.htm) найти? обведи в фотошопе

Обьяснения http://forum.vingrad.ru/index.php?act=ST&f=3&t=12231&st=30.

Цитата

Возможно эту картинку придется немного поменять для этого алгоритма.

Может есть какие-либо размышления по поводу упрощения картинки? Я пробовал понижать яркость, так проще её исследовать, но найти границу между двумя выпуклостями становится тяжелее