diff options
Diffstat (limited to 'content/geometry')
| -rw-r--r-- | content/geometry/antipodalPoints.cpp | 8 | ||||
| -rw-r--r-- | content/geometry/circle.cpp | 2 | ||||
| -rw-r--r-- | content/geometry/closestPair.cpp | 15 | ||||
| -rw-r--r-- | content/geometry/convexHull.cpp | 22 | ||||
| -rw-r--r-- | content/geometry/delaunay.cpp | 23 | ||||
| -rw-r--r-- | content/geometry/formulas.cpp | 13 | ||||
| -rw-r--r-- | content/geometry/formulas3d.cpp | 16 | ||||
| -rw-r--r-- | content/geometry/geometry.tex | 17 | ||||
| -rw-r--r-- | content/geometry/hpi.cpp | 4 | ||||
| -rw-r--r-- | content/geometry/linesAndSegments.cpp | 6 | ||||
| -rw-r--r-- | content/geometry/polygon.cpp | 30 | ||||
| -rw-r--r-- | content/geometry/segmentIntersection.cpp | 4 | ||||
| -rw-r--r-- | content/geometry/sortAround.cpp | 22 | ||||
| -rw-r--r-- | content/geometry/triangle.cpp | 4 |
14 files changed, 91 insertions, 95 deletions
diff --git a/content/geometry/antipodalPoints.cpp b/content/geometry/antipodalPoints.cpp index 110cc74..b34b175 100644 --- a/content/geometry/antipodalPoints.cpp +++ b/content/geometry/antipodalPoints.cpp @@ -1,12 +1,12 @@ vector<pair<int, int>> antipodalPoints(vector<pt>& h) { - if (sz(h) < 2) return {}; + if (ssize(h) < 2) return {}; vector<pair<int, int>> result; for (int i = 0, j = 1; i < j; i++) { while (true) { result.push_back({i, j}); - if (cross(h[(i + 1) % sz(h)] - h[i], - h[(j + 1) % sz(h)] - h[j]) <= 0) break; - j = (j + 1) % sz(h); + if (cross(h[(i + 1) % ssize(h)] - h[i], + h[(j + 1) % ssize(h)] - h[j]) <= 0) break; + j = (j + 1) % ssize(h); }} return result; } diff --git a/content/geometry/circle.cpp b/content/geometry/circle.cpp index 6789c52..155b55c 100644 --- a/content/geometry/circle.cpp +++ b/content/geometry/circle.cpp @@ -22,7 +22,7 @@ vector<pt> circleRayIntersection(pt center, double r, double c = norm(orig - center) - r * r; double discr = b * b - 4 * a * c; if (discr >= 0) { - //t in [0, 1] => schnitt mit Segment [orig, orig + dir] + //t in [0, 1] => Schnitt mit Segment [orig, orig + dir] double t1 = -(b + sqrt(discr)) / (2 * a); double t2 = -(b - sqrt(discr)) / (2 * a); if (t1 >= 0) result.push_back(t1 * dir + orig); diff --git a/content/geometry/closestPair.cpp b/content/geometry/closestPair.cpp index 9b115f3..bbefa67 100644 --- a/content/geometry/closestPair.cpp +++ b/content/geometry/closestPair.cpp @@ -4,12 +4,11 @@ ll rec(vector<pt>::iterator a, int l, int r) { ll midx = a[m].real(); ll ans = min(rec(a, l, m), rec(a, m, r)); - inplace_merge(a+l, a+m, a+r, [](const pt& x, const pt& y) { - return x.imag() < y.imag(); - }); + ranges::inplace_merge(a+l, a+m, a+r, {}, + [](pt x) { return imag(x); }); pt tmp[8]; - fill(all(tmp), a[l]); + ranges::fill(tmp, a[l]); for (int i = l + 1, next = 0; i < r; i++) { if (ll x = a[i].real() - midx; x * x < ans) { for (pt& p : tmp) ans = min(ans, norm(p - a[i])); @@ -19,9 +18,7 @@ ll rec(vector<pt>::iterator a, int l, int r) { return ans; } -ll shortestDist(vector<pt> a) { // sz(pts) > 1 - sort(all(a), [](const pt& x, const pt& y) { - return x.real() < y.real(); - }); - return rec(a.begin(), 0, sz(a)); +ll shortestDist(vector<pt> a) { // size(pts) > 1 + ranges::sort(a, {}, [](pt x) { return real(x); }); + return rec(a.begin(), 0, ssize(a)); } diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 1173924..03c6343 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -1,18 +1,16 @@ vector<pt> convexHull(vector<pt> pts){ - sort(all(pts), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - pts.erase(unique(all(pts)), pts.end()); + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + pts.erase(begin(ranges::unique(pts)), end(pts)); int k = 0; - vector<pt> h(2 * sz(pts)); - auto half = [&](auto begin, auto end, int t) { - for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--; - h[k++] = *it; + vector<pt> h(2 * ssize(pts)); + auto half = [&](auto &&v, int t) { + for (auto x: v) { + while (k > t && cross(h[k-2], h[k-1], x) <= 0) k--; + h[k++] = x; }}; - half(all(pts), 1); // Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. + half(pts, 1); // Untere Hülle. + half(pts | views::reverse | views::drop(1), k); // Obere Hülle h.resize(k); return h; } diff --git a/content/geometry/delaunay.cpp b/content/geometry/delaunay.cpp index c813892..9ae9061 100644 --- a/content/geometry/delaunay.cpp +++ b/content/geometry/delaunay.cpp @@ -3,7 +3,8 @@ using pt = complex<lll>; constexpr pt INF_PT = pt(2e18, 2e18); -bool circ(pt p, pt a, pt b, pt c) {// p in circle(A,B,C), ABC must be ccw +// p in circle(A,B,C), ABC must be ccw +bool circ(pt p, pt a, pt b, pt c) { return imag((c-b)*conj(p-c)*(a-p)*conj(b-a)) < 0; } @@ -12,10 +13,10 @@ struct QuadEdge { QuadEdge* onext = nullptr; pt orig = INF_PT; bool used = false; - QuadEdge* rev() const {return rot->rot;} - QuadEdge* lnext() const {return rot->rev()->onext->rot;} - QuadEdge* oprev() const {return rot->onext->rot;} - pt dest() const {return rev()->orig;} + QuadEdge* rev() const { return rot->rot; } + QuadEdge* lnext() const { return rot->rev()->onext->rot; } + QuadEdge* oprev() const { return rot->onext->rot; } + pt dest() const { return rev()->orig; } }; deque<QuadEdge> edgeData; @@ -98,12 +99,10 @@ pair<QuadEdge*, QuadEdge*> rec(IT l, IT r) { } vector<pt> delaunay(vector<pt> pts) { - if (sz(pts) <= 2) return {}; - sort(all(pts), [](const pt& a, const pt& b) { - if (real(a) != real(b)) return real(a) < real(b); - return imag(a) < imag(b); - }); - QuadEdge* r = rec(all(pts)).first; + if (ssize(pts) <= 2) return {}; + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + QuadEdge* r = rec(begin(pts), end(pts)).first; vector<QuadEdge*> edges = {r}; while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext; auto add = [&](QuadEdge* e){ @@ -117,7 +116,7 @@ vector<pt> delaunay(vector<pt> pts) { }; add(r); pts.clear(); - for (int i = 0; i < sz(edges); i++) { + for (int i = 0; i < ssize(edges); i++) { if (!edges[i]->used) add(edges[i]); } return pts; diff --git a/content/geometry/formulas.cpp b/content/geometry/formulas.cpp index 5d4e10d..b339451 100644 --- a/content/geometry/formulas.cpp +++ b/content/geometry/formulas.cpp @@ -6,20 +6,17 @@ constexpr double PIU = acos(-1.0l); // PIL < PI < PIU constexpr double PIL = PIU-2e-19l; // Winkel zwischen Punkt und x-Achse in [-PI, PI]. -double angle(pt a) {return arg(a);} +double angle(pt a) { return arg(a); } // rotiert Punkt im Uhrzeigersinn um den Ursprung. -pt rotate(pt a, double theta) {return a * polar(1.0, theta);} +pt rotate(pt a, double theta) { return a * polar(1.0, theta); } // Skalarprodukt. -auto dot(pt a, pt b) {return real(conj(a) * b);} - -// abs()^2.(pre c++20) -auto norm(pt a) {return dot(a, a);} +auto dot(pt a, pt b) { return real(conj(a) * b); } // Kreuzprodukt, 0, falls kollinear. -auto cross(pt a, pt b) {return imag(conj(a) * b);} -auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} +auto cross(pt a, pt b) { return imag(conj(a) * b); } +auto cross(pt p, pt a, pt b) { return cross(a - p, b - p); } // 1 => c links von a->b // 0 => a, b und c kolliniear diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp index 63de2ce..66a4644 100644 --- a/content/geometry/formulas3d.cpp +++ b/content/geometry/formulas3d.cpp @@ -2,20 +2,20 @@ auto operator|(pt3 a, pt3 b) { return a.x * b.x + a.y*b.y + a.z*b.z; } -auto dot(pt3 a, pt3 b) {return a|b;} +auto dot(pt3 a, pt3 b) { return a|b; } // Kreuzprodukt -pt3 operator*(pt3 a, pt3 b) {return {a.y*b.z - a.z*b.y, - a.z*b.x - a.x*b.z, - a.x*b.y - a.y*b.x};} -pt3 cross(pt3 a, pt3 b) {return a*b;} +pt3 operator*(pt3 a, pt3 b) { return {a.y*b.z - a.z*b.y, + a.z*b.x - a.x*b.z, + a.x*b.y - a.y*b.x}; } +pt3 cross(pt3 a, pt3 b) { return a*b; } // Länge von a -double abs(pt3 a) {return sqrt(dot(a, a));} -double abs(pt3 a, pt3 b) {return abs(b - a);} +double abs(pt3 a) { return sqrt(dot(a, a)); } +double abs(pt3 a, pt3 b) { return abs(b - a); } // Mixedprodukt -auto mixed(pt3 a, pt3 b, pt3 c) {return a*b|c;}; +auto mixed(pt3 a, pt3 b, pt3 c) { return a*b|c; } // orientierung von p zu der Ebene durch a, b, c // -1 => gegen den Uhrzeigersinn, diff --git a/content/geometry/geometry.tex b/content/geometry/geometry.tex index 92285c4..9290de4 100644 --- a/content/geometry/geometry.tex +++ b/content/geometry/geometry.tex @@ -7,7 +7,7 @@ \sourcecode{geometry/closestPair.cpp} \end{algorithm} -\begin{algorithm}{Konvexehülle} +\begin{algorithm}{Konvexe Hülle} \begin{methods} \method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)} \end{methods} @@ -18,6 +18,7 @@ \end{itemize} \sourcecode{geometry/convexHull.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Rotating calipers} \begin{methods} @@ -29,6 +30,7 @@ \subsection{Formeln~~--~\texttt{std::complex}} \sourcecode{geometry/formulas.cpp} +\columnbreak \sourcecode{geometry/linesAndSegments.cpp} \sourcecode{geometry/sortAround.cpp} \input{geometry/triangle} @@ -40,7 +42,7 @@ \sourcecode{geometry/formulas3d.cpp} \optional{ - \subsection{3D-Kugeln} + \subsection{3D-Kugeln \opthint} \sourcecode{geometry/spheres.cpp} } @@ -48,15 +50,22 @@ \sourcecode{geometry/hpi.cpp} \end{algorithm} +\begin{algorithm}[optional]{Intersecting Segments} + \begin{methods} + \method{intersect}{finds ids of intersecting segments}{n\*\log(n)} + \end{methods} + \sourcecode{geometry/segmentIntersection.cpp} +\end{algorithm} + \begin{algorithm}[optional]{Delaunay Triangulierung} \begin{methods} \method{delaunay}{berechnet Triangulierung}{n\*\log(n)} \end{methods} - \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Traingulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. + \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Triangulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. \sourcecode{geometry/delaunay.cpp} \end{algorithm} \optional{ -\subsection{Geraden} +\subsection{Geraden \opthint} \sourcecode{geometry/lines.cpp} } diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index 02c71e3..ec27254 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,6 +1,6 @@ constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP -bool left(pt p) {return real(p) < 0 || +bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} struct hp { pt from, to; @@ -11,7 +11,7 @@ struct hp { bool dummy() const {return from == to;} pt dir() const {return dummy() ? to : to - from;} bool operator<(const hp& o) const { - if (left(dir()) != left(o.dir())) + if (left(dir()) != left(o.dir())) return left(dir()) > left(o.dir()); return cross(dir(), o.dir()) > 0; } diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index ddab554..985ee24 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -28,9 +28,7 @@ pt projectToLine(pt a, pt b, pt p) { // sortiert alle Punkte pts auf einer Linie entsprechend dir void sortLine(pt dir, vector<pt>& pts) { // (2d und 3d) - sort(all(pts), [&](pt a, pt b){ - return dot(dir, a) < dot(dir, b); - }); + ranges::sort(pts, {}, [&](pt x) { return dot(dir, x); }); } // Liegt p auf der Strecke a-b? (nutze < für inberhalb) @@ -66,7 +64,7 @@ vector<pt> segmentIntersection2(pt a, pt b, pt c, pt d) { double x = cross(b - a, d - c); double y = cross(c - a, d - c); double z = cross(b - a, a - c); - if (x < 0) {x = -x; y = -y; z = -z;} + if (x < 0) { x = -x; y = -y; z = -z; } if (y < -EPS || y-x > EPS || z < -EPS || z-x > EPS) return {}; if (x > EPS) return {a + y/x*(b - a)}; vector<pt> result; 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; diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index afc01b2..9fdbdb8 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -39,10 +39,10 @@ pair<int, int> intersect(vector<seg>& segs) { events.push_back({s.a, s.id, 1}); events.push_back({s.b, s.id, -1}); } - sort(all(events)); + ranges::sort(events, less{}); set<seg> q; - vector<set<seg>::iterator> where(sz(segs)); + vector<set<seg>::iterator> where(ssize(segs)); for (auto e : events) { int id = e.id; if (e.type > 0) { diff --git a/content/geometry/sortAround.cpp b/content/geometry/sortAround.cpp index 98d17a8..7e9d1de 100644 --- a/content/geometry/sortAround.cpp +++ b/content/geometry/sortAround.cpp @@ -1,11 +1,11 @@ -bool left(pt p) {return real(p) < 0 ||
- (real(p) == 0 && imag(p) < 0);}
-
-// counter clockwise, starting with "11:59"
-void sortAround(pt p, vector<pt>& ps) {
- sort(all(ps), [&](const pt& a, const pt& b){
- if (left(a - p) != left(b - p))
- return left(a - p) > left(b - p);
- return cross(p, a, b) > 0;
- });
-}
+bool left(pt p) { return real(p) < 0 || + (real(p) == 0 && imag(p) < 0); } + +// counter clockwise, starting with "11:59" +void sortAround(pt p, vector<pt>& ps) { + ranges::sort(ps, [&](const pt& a, const pt& b){ + if (left(a - p) != left(b - p)) + return left(a - p) > left(b - p); + return cross(p, a, b) > 0; + }); +} diff --git a/content/geometry/triangle.cpp b/content/geometry/triangle.cpp index 534bb10..eab17f4 100644 --- a/content/geometry/triangle.cpp +++ b/content/geometry/triangle.cpp @@ -1,5 +1,5 @@ // Mittelpunkt des Dreiecks abc. -pt centroid(pt a, pt b, pt c) {return (a + b + c) / 3.0;} +pt centroid(pt a, pt b, pt c) { return (a + b + c) / 3.0; } // Flächeninhalt eines Dreicks bei bekannten Eckpunkten. double area(pt a, pt b, pt c) { @@ -30,7 +30,7 @@ pt circumCenter(pt a, pt b, pt c) { // -1 => p außerhalb Kreis durch a,b,c // 0 => p auf Kreis durch a,b,c // 1 => p im Kreis durch a,b,c -int insideOutCenter(pt a, pt b, pt c, pt p) {// braucht lll +int insideOutCenter(pt a, pt b, pt c, pt p) { // braucht lll return ccw(a,b,c) * sgn(imag((c-b)*conj(p-c)*(a-p)*conj(b-a))); } |