Как найти центр многоугольника
Перейти к содержимому

Как найти центр многоугольника

  • автор:

Как найти центр многоугольника

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

  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 #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// применяем формулы (*) 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 следующих треугольников:

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

К статье можно в текстовом формате.

Нахождение центра многоугольника

Author24 — интернет-сервис помощи студентам

Найти координаты всех вершин правильного многоугольника, зная координаты центра и радиус описанной окружности.
Дан правильный N-угольник с центром в точке (X, Y) и с радиусом описанной окружности R. Найти.

Вращение вписанного многоугольника вокруг центра окружности
Создать анимацию, позволяющее при нажатии на кнопку «Движение», воспроизводить вращение вписанного.

Нахождение диагоналей выпуклого многоугольника
Произвольный выпуклый многоугольник задан координатами своих вершин на плоскости. Найдите самую.

Нахождение центра тяжести
Найти координаты центра тяжести верхней полусферы x2+y2+z2≤R2, плотность в каждой точке.

Заблокирован

Чтобы найти координаты центра (ну или еще говорят центра тяжести) многоугольника, нужно сложить соответствующие координаты его вершин и разделить на число вершин.

Нельзя — возьмём 10-угольник: квадрат, у которого 6 вершин добавлены на одну сторону. Тогда центр тяжести перетащится к этой стороне

Супер-модератор

Эксперт Pascal/DelphiАвтор FAQ

32838 / 21174 / 8149
Регистрация: 22.10.2011
Сообщений: 36,433
Записей в блоге: 8

Для начала надо разобраться, центр тяжести чего находится. Системы материальных точек (вся масса — только в вершинах многоугольника), центр тяжести каркаса (масса распределена по всем периметру) или центр тяжести всей фигуры (масса распределена по всей площади многоугольника), и в зависимости от этого уже решать задачу.

4043 / 2332 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10

Предлагаю для реалистичности искать центр тяжести композитной пластиковой крышки канализационного люка, неоднородной по плотности и структуре и неравномерно присыпанной снежком!

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Нахождение центра формы
Привет всем! У меня возникла проблема с нахождением центра формы, дело в том что когда у формы в.

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

Нахождение центра области изображения
Написал программу по нахождение центров областей изображения. Увы но контуры областей выделяются.

Нахождение радиуса, диаметра и центра графа
Помогите написать программу для нахождения радиуса, диаметра и центры графа 🙁

Или воспользуйтесь поиском по форуму:

Как вычислить центр многоугольника?

На карте отобразил условный контур и теперь хотел бы в него вывести балун. Создать балун не проблема, не поместить его в центр полигона — проблема.

В математике есть довольно сложные формулы для расчёта центра масс многоугольника, ими я не умею пользоваться. но в яндекс апи есть poly.geometry.getBounds(), который берёт максимально большой контур и находит центр. У меня тоже не получается его применить потому что полигон я создал не стандартным способом( new ymaps.Polygon()), а через map.geoObjects.add(objectManager);

Помогите пожалуйста получить координаты центра полигона.

Если нужно, то вот фиддл, который демонстрирует getBounds().

  • Вопрос задан более трёх лет назад
  • 1009 просмотров

1 комментарий

Простой 1 комментарий

Научный форум dxdy

Нахождение центра произвольного многоугольника

На страницу 1 , 2 , 3 След.

Нахождение центра произвольного многоугольника
05.02.2018, 18:18

Последний раз редактировалось GANJE 05.02.2018, 18:32, всего редактировалось 2 раз(а).

Есть произвольный невыпуклый многоугольник на плоской плоскости, заданный списком вершин, то есть векторов. Я придумала, как приближённо найти у него подходящий центр так, чтобы при вращении вокруг этого центра многоугольник не сильно колбасило. Время линейно зависит от количества вершин. Наверняка есть какие-то более хитрые и заумные алгоритмы, но мой мне нравится простотой. Я его ещё не написала. Итак, вкратце:

1) хватаем любую (первую) вершину и начинаем крутить;
2) для каждой итерации берём ограничивающий прямоугольник и находим его центр (элементарно — пересечение диагоналей);
3) сохраняем каждый предварительный центр относительно каждого поворота;
4) поворачиваем все центры обратно;
5) находим приближённый центр как центр тяжести предварительных центров.

Крутим раз 10-12. Даже на моём слабеньком компьютере все эти синусы-косинусы даже 1000 раз по 10000 (пробовала) вычислялись меньше чем за секунду, а кроме того, можно заранее составить таблицу, и каждый раз их вычислять вообще не придётся.

Чем плох простой центр тяжести?
Предположим, у нас есть многоугольник из 100000000 + 1 вершин. 100000000 вершин лежит близко к стороне правильного треугольника и изображает реки, леса, поля, птичек и кошечек. А 1 вершина находится на противолежащей вершине правильного треугольника. И тогда центр тяжести будет сколь угодно близок к «тяжёлой» стороне треугольника, чем больше нулей возьмём, тем ближе.

Зачем я это объясняю. Я пишу программу, которая будет работать с выкройками, а простейшее представление выкройки — многоугольник. Детали надо покрутить так, чтобы на тех отрезах произвольной формы, что есть у пользователя (он сам должен задать их), осталось как можно меньше неизрасходованной ткани. И соответственно, больше остатков можно было пустить в дело.

Что вы думаете по этому поводу? Думала использовать центр описанной вокруг выпуклого огибающего многоугольника окружности, но если многоугольник по форме будет близок к полуокружности, то центр будет рядом с краем, поэтому крутиться будет некрасиво. А надо чтобы удобно.
Да и ещё «построение минимальной выпуклой оболочки» мне показалось чем-то чудовищным, хотя если вникнуть, может не стоить и выеденного яйца.

Только сейчас сообразила: крутить можно вокруг любой выбранной точки, не только вершины многоугольника, просто я хотела нарисовать ограничивающий прямоугольник для каждого поворота и посмотреть, а для этого удобнее, чтобы центр вращения был как-то ближе к многоугольнику, ну, чтобы он (многоугольник) далеко не убегал.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *