|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eugene Kilachkoff 2:5020/400 24 Nov 2002 23:39:11
To : Alexander Kolosov
Subject : Re: Центр фигуры
--------------------------------------------------------------------------------
Alexander Kolosov пишет:
> Hужно определить координаты центра фигуры обозначенной единицами.
> Hасколько я понял, нужно достроить фигуру до прямоугольника и найти
> пересечение его диагоналей. Какой алгоритм лучше использовать?
Центры бывают разные. Зависит от задачи. То, что хочешь использовать
даст тебе центр описывающего прямоугольника. Иногда может потребоваться
найти центр масс или э-э-э.. не знаю как правильно назвать..
"геометрический центр".
В случае описывающего прямоугольника находишь max и min колонку и строку
в которой еще есть единички. Потом xcenter=(xmax+xmin)/2,
ycenter=(ymax+ymin)/2.
Центр масс считается так (sx,sy - размеры матрицы):
cx=cy=0;
for(i=0;i<sy;i++)
for(j=0;j<sx;j++)
{
cx+=j*m[i][j];
cy+=i*m[i][j];
}
cx/=sx*(sx+1)/2;
cy/=sy*(sy+1)/2;
Если тебе нужно найти "геометрический центр", то все массы нужно считать
за единицу, отсутствие ее за 0. Иными словами:
if ( m[i][j]>0 ) cx+1;
Вот на такой фигуре все три алгоритма дадут разный результат (нули
заменены точками для наглядности):
............................
..933333333333333333333333..
..9B222.....................
..91111.C.....A.............
..91111.....................
..9111111111111111111111111.
............................
A - результат первого алгоритма, B - второго, C -третьего.
--- ifmail v.2.15dev5
* Origin: home (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
