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

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

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

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

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

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

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

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

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

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

#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 (пересекающихся только по границе).
Тогда центр тяжести фигуры Ф выражается так:

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

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

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

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

Если же многоугольник выпуклый, но вершины перечислены не в порядке обхода, то их придется упорядочить. Сделать это можно, например, отсортировав вершины по углу между положительной полуосью ОХ и вектором (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 в текстовом формате.