centrul de greutate
Conceptul de „centrul de greutate al unui poligon“ poate fi interpretat în trei moduri diferite:
- Greutatea este doar la nodurile, în care fiecare vârf „cântărește“ în mod egal
- Masa este distribuită uniform pe conturul poligonului
- Masa este distribuită uniform pe suprafața delimitată de poligon.
Luați în considerare toate cele trei interpretări, în ordinea crescătoare a complexității algoritmului.
1. Masa este doar la nodurile, în care fiecare nod cântărește în mod egal
În acest caz, centrul coordonatelor gravimetrice sunt exprimate prin formulele:
Xc = (M1 * X1 +. + MN * XN) / M Yc = (M1 * Y1 +. + MN * YN) / M
(Xi, Yi) - coordonatele nodului i-lea al poligonului,
Mi - greutate de vârf i-lea.
M - masa tuturor nodurilor (M = M1 + + MN.)
Astfel, avem pentru cazul nostru special:
Xc = (X1 +. + XN) / N Yc = (Y1 +. + YN) / N,
că nu există nici o dificultate în punerea în aplicare nu este.
2. Masa distribuită uniform pe conturul poligonului
În acest caz, greutatea coaste proporțională cu lungimea sa. Astfel, fiecare muchie putem fi înlocuită cu o masă punct (proporțională cu lungimea coastelor). Apoi, folosind aceleași formule pentru determinarea centrului de greutate se obține
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) - coordonate, înseamnă coaste i-lea.
Li - lungimea nervurii i-lea
P - perimetrul poligonului (. P = L1 + + LN) denota formula (*)
Mai jos este un program de punere în aplicare a algoritmului descris mai sus:
3. Masa este uniform distribuit în zona delimitată de poligon.
Acest caz nu mai este atât de banal ca cele doua anterioare. Pentru a construi un algoritm nevoie de următorul fapt:
Oferta 1
Fie F figura este unirea dintre celelalte două figuri F1 și F2 (suprapunere numai la frontieră).
Apoi, centrul de greutate al figurii F este exprimată după cum urmează:
Xc = (XC1 * S1 + S2 XC2 *) / S Yc = (Yc1 * S1 + S2 Yc2 *) / S
(Xc, Yc) - coordonatele centrului de greutate F
(XC1, Yc1) - coordonatele centrului de greutate F1
(XC2, Yc2) - coordonatele centrului de greutate F2
S - Zona F
S1 - F1 zona
S2 - zona F2
(Acest lucru este evident din definiția centrului de greutate al unei forme arbitrare și proprietățile integralele aditiv)
În plus față de centrul de greutate al triunghiului este definit după cum urmează:
Xc = (X1 + X2 + X3) / 3 Yc = (Y1 + Y2 + Y3) / 3
Impartim poligon nostru în triunghiuri. Pentru fiecare triunghi a găsi centrul de greutate (XCI, YCI) și zona (Si). După aceea, potrivit propoziției 1, centrul de gravitate al coordonatelor poligonale pot fi găsite după cum urmează:
Xc = (XC1 * S1 +. + XCN * SM) / S Yc = (Yc1 * S1 +. + YcN * SM) / S
M - numărul de triunghiuri, pe care ne-am împărțit poligon
S - suprafața totală a poligonului (S = S1 + + SM.)
Notăm aceste formule (**)
Întrebarea rămâne, cum se sparge poligon în triunghiuri. Dacă un poligon convex iar nodurile sunt listate în ordinea parcurgeri sau contra acelor de ceasornic, apoi pur și simplu găsi un singur punct în interiorul poligonului (Xm, Ym) și apoi împărțiți poligon în triunghiuri N următoarele:
În cazul în care un poligon convex, dar vârfurile nu sunt enumerate în ordinea parcurgeri, atunci ei vor trebui să organizeze. Acest lucru se poate face, de exemplu, prin sortarea vârful unghiului dintre jumătatea axei pozitive OX și vectorul (Xi-Xm, Yi-Ym).
poligoane non-convexe pot fi întotdeauna defalcate în mai multe convexe. Apoi, folosind algoritmul descris mai sus pentru fiecare dintre porțiunile convexe și folosind propoziția 1, pentru a găsi centrul de greutate al poligonului. Problema descompunerii a unei porțiuni de poligon convex arbitrar o sarcină independentă care este discutată în secțiunea relevantă. Prin urmare, punerea în aplicare a algoritmului prezentat mai jos este doar pentru poligon convex.
Mai jos este o implementare de probă a acestui algoritm în C pentru a găsi centrul de greutate al unui poligon convex ale cărui noduri sunt enumerate în ordinea parcurgeri sau contra-sensul acelor de ceasornic:
Pe hârtie, puteți descărca zip sursă în format text simplu.