Понятие "центр тяжести многоугольника" можно интерпретировать тремя различными способами: Масса находится только в вершинах, причем каждая вершина "весит" одинаково Масса равномерно распределена по границе многоугольника Масса равномерно распределена по области, ограниченной многоугольником. Рассмотрим все три интерпретации в порядке возрастания сложности алгоритма. Масса находится только в вершинах, причем каждая вершина весит одинаково В этом случае координаты центра тяжести выражаются по формулам: 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, что никакой сложности в реализации не представляет. Масса равномерно распределена по границе многоугольника В этом случае масса ребра пропорциональна его длине. Таким образом каждое ребро мы можем заменить на точечную массу (пропорциональную длине ребра). Затем применяя те же формулы для определения центра тяжести получаем: 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 #include #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 scanf("%lf %lf", &(x[j]), &(y[j])); double xc=0, yc=0; double P=0; for (int i=0; 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); } } Масса равномерно распределена по области, ограниченной многоугольником. Этот случай уже не является столь тривиальным, как два предыдущих. Для построения алгоритма понадобится следующий факт: Предложение 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 #include #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 { 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 { // используем полученные формулы (**) 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; }  8  Комментарии к статье  8 8  Обсудить в чате