център на тежестта

Концепцията за "центъра на тежестта на полигон" може да се тълкува по три различни начина:

1. Тегло е само върховете, където всеки връх "тежи" еднакво
2. Масата е равномерно разпределена през границата на полигона
3. Масата е равномерно разпределена върху зоната, ограничена от многоъгълника.

Помислете за трите интерпретации по нарастваща сложност на алгоритъма.

1. масата само на върховете, където всеки връх тежат еднакво

В този случай, на центъра на тежестта на координатите се изразяват чрез формулите:

Хе = (M1 * X1 +. + MN * XN) / M Yc = (M1 * Y1 +. + MN * ин) / М

(Xi, Yi) - координати на аз-ти връх на многоъгълника,
Mi - тегло-тото връх.
М - маса на всички върхове (М = М1 + + MN).

По този начин, ние имаме за нашето конкретен случай:

Хе = (X1 +. + XN) / N = Yc (Y1 +. + Ин) / N,

че не съществува трудност при изпълнение не е.

2. масата, равномерно разпределени върху границата на полигона

В този случай ребра тегло пропорционална на неговата дължина. По този начин всеки ръб ние може да бъде заменен с точка маса (пропорционално на дължината на ребрата). След това, използвайки същите формули за определяне на центъра на тежестта се получи

Хе = (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) - координати, означава, че-то ребро.
Li - дължината на аз-ти ребро
P - периметъра на многоъгълника. (Р = L1 + + LN) означават формула (*)

По-долу е програма за прилагане на алгоритъма, описан по-горе:

3. маса се разпределя равномерно над региона, ограничена от многоъгълника.

Този случай вече не е толкова тривиално като предишните две. За да се изгради един алгоритъм нужда следния факт:

Оферта 1
Нека F фигура е на Съюза на другите два F1 и F2 фигури (припокриващи се само на границата).
Тогава центърът на тежестта на фигурата F се изразява, както следва:

Хе = (Xc1 * S1 + xC2 * S2) / S = Yc (Yc1 * S1 + Yc2 * S2) / S

(Хс, Yc) - координатите на центъра на тежестта F
(Xc1, Yc1) - координатите на центъра на тежестта F1
(XC2, Yc2) - координатите на центъра на тежестта F2
S - площ F
S1 - площ F1
S2 - площ F2

(Това е очевидно от определението на центъра на тежестта на произволна форма и свойства на интегралите на добавките)

В допълнение към триъгълник центъра на тежестта се определя, както следва:

Хе = (X1 + X2 + х 3) / 3 = Yc (Y1 + Y2 + Y3) / 3

Ние разделяме нашето полигон в триъгълници. За всеки триъгълник се намери центъра на тежестта (XCI, Yci) и областта (Si). След това, съгласно изречение 1, в центъра на тежестта на координатите многоъгълник може да се намери, както следва:

Хе = (Xc1 * S1 +. + XCN * SM) / S = Yc (Yc1 * S1 +. + YcN * SM) / S

М - броят на триъгълници, които се разделихме полигон
S - площ на многоъгълника (S = S1 + + SM).
Означаваме тези формули (**)

Остава открит въпросът, как да се разбие на полигона в триъгълници. Ако изпъкнал многоъгълник и върховете са изброени в реда на прекосява или обратно на часовниковата стрелка, след това просто да се намери една точка вътре в многоъгълник (Xm, Ym), и след това се разделят на многоъгълника на триъгълници N следните:

Ако е изпъкнал многоъгълник, а върховете не са изброени в низходящ ред по прекосявам, а след това те ще трябва да организират. Това може да стане, например, чрез сортиране върха на ъгъла между положителния половината оста OX и вектора (Xi-XM, Yi-Ym).

Non-изпъкнал многоъгълник винаги могат да бъдат разделени в няколко изпъкнал. След това, с помощта на алгоритъм, описани по-горе за всяка от изпъкнали части и използване Твърдение 1, да се намери на центъра на тежестта на многоъгълника. Проблемът на разлагане на произволен многоъгълник изпъкнали части на независима задача, която се обсъжда в съответната секция. Поради това, изпълнението на алгоритъма, представен по-долу е само за изпъкнал многоъгълник.

По-долу е извадка от изпълнението този алгоритъм в C да се намери центъра на тежестта на изпъкнал многоъгълник, чиито върхове са изброени в низходящ ред по прекосява или обратно на часовниковата стрелка:

На хартия, можете да изтеглите изходния код в обикновен текстов формат.