:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Многоугольники » Центр тяжести
  Центр тяжести



Павел Егоров
e-mail: XopoSHiy@mail.ru

Понятие "центр тяжести многоугольника" можно интерпретировать тремя различными способами:

  1. Масса находится только в вершинах, причем каждая вершина "весит" одинаково
  2. Масса равномерно распределена по границе многоугольника
  3. Масса равномерно распределена по области, ограниченной многоугольником.

Рассмотрим все три интерпретации в порядке возрастания сложности алгоритма.

1. Масса находится только в вершинах, причем каждая вершина весит одинаково

В этом случае координаты центра тяжести выражаются по формулам:

Xc = (M1*X1 + ... + MN*XN)/M Yc = (M1*Y1 + ... + MN*YN)/M
(Xi, Yi) - координаты i-ой вершины многоугольника,
Mi - масса i-ой вершины.
M - масса всех вершин (M = M1 + ... + MN)

Таким образом для нашего частного случая имеем:

Xc = (X1 + ... + XN)/N Yc = (Y1 + ... + YN)/N,
что никакой сложности в реализации не представляет.

2. Масса равномерно распределена по границе многоугольника

В этом случае масса ребра пропорциональна его длине. Таким образом каждое ребро мы можем заменить на точечную массу (пропорциональную длине ребра). Затем применяя те же формулы для определения центра тяжести получаем:

Xc = (L1*X'1 + L2*X'2 + ... + LN*X'N) / P Yc = (L1*Y'1 + L2*Y'2 + ... + LN*Y'N) / P
(X'i, Y'i) - координаты, середины i-ого ребра.
Li - длина i-ого ребра
P - периметр многоугольника (P = L1 + ... + LN) Обозначим эти формулы (*)

Ниже представлена программа, реализующая описанный алгоритм:

#include <stdio.h>
#include <math.h>

#define MAX 100

int n;
double x[MAX];
double y[MAX];

//  возвращает длину отрезка с координатами (x1,y1)-(x2,y2)
double length(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

void main()
{
	// будем вводить данные из файла
	freopen("input.txt","r",stdin);
	while (scanf("%d",&n)==1)
	{
		for(int j=0; j<n; j++)
			scanf("%lf %lf", &(x[j]), &(y[j]));
		double xc=0, yc=0;
		double P=0;
		for (int i=0; i<n; i++)
		{
			// применяем формулы (*)
			double l = length(x[i],y[i],x[(i+1)%n],y[(i+1)%n]);
			xc += l * (x[i]+x[(i+1)%n]) / 2;
			yc += l * (y[i]+y[(i+1)%n]) / 2;
			P += l;
		}
		xc/=P; 
        yc/=P;
		printf("%lf %lf\n",xc,yc);
	}

}

3. Масса равномерно распределена по области, ограниченной многоугольником.

Этот случай уже не является столь тривиальным, как два предыдущих. Для построения алгоритма понадобится следующий факт:

Предложение 1
Пусть фигура Ф есть объединение двух других фигур Ф1 и Ф2 (пересекающихся только по границе).
Тогда центр тяжести фигуры Ф выражается так:

Xc = (Xc1*S1 + Xc2*S2) / S Yc = (Yc1*S1 + Yc2*S2) / S
(Xc, Yc) - координаты центра тяжести Ф
(Xc1, Yc1) - координаты центра тяжести Ф1
(Xc2, Yc2) - координаты центра тяжести Ф2
S - площадь Ф
S1 - площадь Ф1
S2 - площадь Ф2

(Это утверждение очевидно следует из определения центра тяжести произвольной фигуры и свойства аддитивности интеграла)

Кроме того для треугольника центр тяжести определяется так:

Xc = (X1 + X2 + X3) / 3 Yc = (Y1 + Y2 + Y3) / 3

Разобьем наш многоугольник на треугольники. Для каждого треугольника найдем его центр тяжести (Xci, Yci) и площадь (Si). После этого, согласно Предложению 1, координаты центра тяжести многоугольника можно найти следующим образом:

Xc = (Xc1*S1 + ... + XcN*SM) / S Yc = (Yc1*S1 + ... + YcN*SM) / S
M - количество треугольников, на которые мы разбили многоугольник
S - площадь всего многоугольника (S = S1 + ... + SM)
Обозначим эти формулы (**)

Остается вопрос, как разбить многоугольник на треугольники. Если многоугольник выпуклый, а вершины перечислены в порядке обхода по или против часовой стрелки, то достаточно просто найти одну точку внутри многоугольника (Xm,Ym), а затем разбить многоугольник на N следующих треугольников:

(X1,Y1)-(X2,Y2)-(Xm,Ym)
(X2,Y2)-(X3,Y3)-(Xm,Ym)
......
(XN,YN)-(X1,Y1)-(Xm,Ym)

Если же многоугольник выпуклый, но вершины перечислены не в порядке обхода, то их придется упорядочить. Сделать это можно, например, отсортировав вершины по углу между положительной полуосью ОХ и вектором (Xi-Xm, Yi-Ym).

Невыпуклый многоугольник всегда можно разбить на несколько выпуклых. А затем, применив описанный алгоритм для каждой выпуклой части, и используя Предложение 1, найти центр тяжести всего многоугольника. Задача о разбиении произвольного многоугольника на выпуклые части является самостоятельной задачей, которая рассмотрена в соответствующем разделе. Поэтому представленная ниже реализация алгоритма работает только для выпуклых многоугольников.

Ниже представлен пример реализации описанного алгоритма на языке С для нахождения центра тяжести выпуклого многоугольника, вершины которого перечислены в порядке обхода по или против часовой стрелки:

#include <stdio.h>
#include <math.h>

#define MAX 100

double x[MAX], y[MAX];
int n;

// возвращает площадь треугольника по координатам вершин
// площадь - это половина модуля векторного произведения двух сторон
double square(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return 0.5*fabs((x2-x3)*(y1-y3) - (x1-x3)*(y2-y3));
}

int main(void)
{
	freopen("input.txt","r",stdin);
	while (scanf("%d", &n) == 1) // количество вершин в многоугольнике
	{
	    double xm=0, ym=0;
		for(int i=0; i<n; i++)
		{
			scanf("%lf %lf", &(x[i]), &(y[i]));
			xm+=x[i];
			ym+=y[i];
		}
		xm/=n; ym/=n; // координаты точки внутри многоугольника
		double s = 0;
		double xc=0,yc=0;
		// Шагаем по треугольникам. Их n штук
		for(i=0; i<n; i++)
		{
			// используем полученные формулы (**)
			double s1 =square(xm,ym,x[i],y[i],x[(i+1)%n],y[(i+1)%n]);
			xc+=s1*(xm+x[i]+x[(i+1)%n])/3;
			yc+=s1*(ym+y[i]+y[(i+1)%n])/3;
			s+=s1;
		}
		xc/=s; yc/=s;
		printf("%lf %lf\n", xc, yc);
	}
	return 0;
}

К статье можно скачать исходникиzip в текстовом формате.