diff options
Diffstat (limited to 'content/geometry/polygon.cpp')
| -rw-r--r-- | content/geometry/polygon.cpp | 30 |
1 files changed, 14 insertions, 16 deletions
diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 1332a4a..474ce88 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -2,7 +2,7 @@ // Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. double area(const vector<pt>& poly) { //poly[0] == poly.back() ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) + for (int i = 0; i + 1 < ssize(poly); i++) res += cross(poly[i], poly[i + 1]); return 0.5 * res; } @@ -13,7 +13,7 @@ double area(const vector<pt>& poly) { //poly[0] == poly.back() // selbstschneidenden Polygonen (definitions Sache) ll windingNumber(pt p, const vector<pt>& poly) { ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (real(a) > real(b)) swap(a, b); if (real(a) <= real(p) && real(p) < real(b) && @@ -26,7 +26,7 @@ ll windingNumber(pt p, const vector<pt>& poly) { // check if point is inside polygon (any polygon) bool inside(pt p, const vector<pt>& poly) { bool in = false; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (pointOnSegment(a, b, p)) return false; // border counts? if (real(a) > real(b)) swap(a, b); @@ -40,7 +40,7 @@ bool inside(pt p, const vector<pt>& poly) { // convex hull without duplicates, h[0] != h.back() // apply comments if border counts as inside bool insideConvex(pt p, const vector<pt>& hull) { - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; if (cross(hull[0], hull[r], p) >= 0) return false; // > 0 while (l + 1 < r) { int m = (l + r) / 2; @@ -51,11 +51,9 @@ bool insideConvex(pt p, const vector<pt>& hull) { } void rotateMin(vector<pt>& hull) { - auto mi = min_element(all(hull), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - rotate(hull.begin(), mi, hull.end()); + auto mi = ranges::min_element(hull, {}, + [](pt a) { return pair{real(a), imag(a)}; }); + ranges::rotate(hull, mi); } // convex hulls without duplicates, h[0] != h.back() @@ -67,7 +65,7 @@ vector<pt> minkowski(vector<pt> ps, vector<pt> qs) { ps.push_back(ps[1]); qs.push_back(qs[1]); vector<pt> res; - for (ll i = 0, j = 0; i + 2 < sz(ps) || j + 2 < sz(qs);) { + for (ll i = 0, j = 0; i+2 < ssize(ps) || j+2 < ssize(qs);) { res.push_back(ps[i] + qs[j]); auto c = cross(ps[i + 1] - ps[i], qs[j + 1] - qs[j]); if(c >= 0) i++; @@ -83,22 +81,22 @@ double dist(const vector<pt>& ps, vector<pt> qs) { p.push_back(p[0]); double res = INF; bool intersect = true; - for (ll i = 0; i + 1 < sz(p); i++) { + for (ll i = 0; i + 1 < ssize(p); i++) { intersect &= cross(p[i], p[i+1]) >= 0; res = min(res, distToSegment(p[i], p[i+1], 0)); } return intersect ? 0 : res; } -bool left(pt of, pt p) {return cross(p, of) < 0 || - (cross(p, of) == 0 && dot(p, of) > 0);} +bool left(pt of, pt p) { return cross(p, of) < 0 || + (cross(p, of) == 0 && dot(p, of) > 0); } // convex hulls without duplicates, hull[0] == hull.back() and // hull[0] must be a convex point (with angle < pi) // returns index of corner where dot(dir, corner) is maximized int extremal(const vector<pt>& hull, pt dir) { dir *= pt(0, 1); - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; while (l + 1 < r) { int m = (l + r) / 2; pt dm = hull[m+1]-hull[m]; @@ -110,7 +108,7 @@ int extremal(const vector<pt>& hull, pt dir) { if (cross(dir, dm) < 0) l = m; else r = m; }} - return r % (sz(hull) - 1); + return r % (ssize(hull) - 1); } // convex hulls without duplicates, hull[0] == hull.back() and @@ -126,7 +124,7 @@ vector<int> intersectLine(const vector<pt>& hull, pt a, pt b) { if (cross(hull[endA], a, b) > 0 || cross(hull[endB], a, b) < 0) return {}; - int n = sz(hull) - 1; + int n = ssize(hull) - 1; vector<int> res; for (auto _ : {0, 1}) { int l = endA, r = endB; |