Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Вычислительная геометрия / Работа с многоугольниками /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Центр тяжести - Программирование от RIN.RU
Центр тяжести

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


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

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

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




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


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


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

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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь