Re: Центр фигуры

From

Eugene Kilachkoff ()

To

Alexander Kolosov

Date

2002-11-24T22:39:11Z

Area

RU.ALGORITHMS

From: Eugene Kilachkoff <zeus@hippo.ru>

Alexander Kolosov пишет:
> Нужно определить координаты центра фигуры обозначенной единицами.
> Насколько я понял, нужно достроить фигуру до прямоугольника и найти
> пересечение его диагоналей. Какой алгоритм лучше использовать? 
Центры бывают разные. Зависит от задачи. То, что хочешь использовать 
даст тебе центр описывающего прямоугольника. Иногда может потребоваться 
найти центр масс или э-э-э.. не знаю как правильно назвать.. 
"геометрический центр".
В случае описывающего прямоугольника находишь 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)