centroid of a (possibly non-convex) polygon, assuming that the coordinates are listed in a clockwise or counterclockwise fashion. Note that the centroid is often known as the "center of gravity" or "center of mass".
| 580 | // counterclockwise fashion. Note that the centroid is often known as |
| 581 | // the "center of gravity" or "center of mass". |
| 582 | PT centroid(vector<PT> &p) { |
| 583 | int n = p.size(); PT c(0, 0); |
| 584 | double sum = 0; |
| 585 | for (int i = 0; i < n; i++) sum += cross(p[i], p[(i + 1) % n]); |
| 586 | double scale = 3.0 * sum; |
| 587 | for (int i = 0; i < n; i++) { |
| 588 | int j = (i + 1) % n; |
| 589 | c = c + (p[i] + p[j]) * cross(p[i], p[j]); |
| 590 | } |
| 591 | return c / scale; |
| 592 | } |
| 593 | // 0 if cw, 1 if ccw |
| 594 | bool get_direction(vector<PT> &p) { |
| 595 | double ans = 0; int n = p.size(); |