From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/geometry/delaunay.cpp | 124 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 124 insertions(+) create mode 100644 content/geometry/delaunay.cpp (limited to 'content/geometry/delaunay.cpp') diff --git a/content/geometry/delaunay.cpp b/content/geometry/delaunay.cpp new file mode 100644 index 0000000..c813892 --- /dev/null +++ b/content/geometry/delaunay.cpp @@ -0,0 +1,124 @@ +using lll = __int128; +using pt = complex; + +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 + return imag((c-b)*conj(p-c)*(a-p)*conj(b-a)) < 0; +} + +struct QuadEdge { + QuadEdge* rot = nullptr; + 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;} +}; + +deque edgeData; + +QuadEdge* makeEdge(pt from, pt to) { + for (int _ : {0,1,2,3}) edgeData.push_back({}); + auto e = edgeData.end() - 4; + for (int j : {0,1,2,3}) e[j].onext = e[j^3].rot = &e[j^(j>>1)]; + e[0].orig = from; + e[1].orig = to; + return &e[0]; +} + +void splice(QuadEdge* a, QuadEdge* b) { + swap(a->onext->rot->onext, b->onext->rot->onext); + swap(a->onext, b->onext); +} + +QuadEdge* connect(QuadEdge* a, QuadEdge* b) { + QuadEdge* e = makeEdge(a->dest(), b->orig); + splice(e, a->lnext()); + splice(e->rev(), b); + return e; +} + +bool valid(QuadEdge* e, QuadEdge* base) { + return cross(e->dest(), base->orig, base->dest()) < 0; +} + +template +QuadEdge* deleteAll(QuadEdge* e, QuadEdge* base) { + if (valid(e, base)) { + while (circ(base->dest(), base->orig, e->dest(), (ccw ? e->onext : e->oprev())->dest())) { + QuadEdge* t = ccw ? e->onext : e->oprev(); + splice(e, e->oprev()); + splice(e->rev(), e->rev()->oprev()); + e = t; + }} + return e; +} + +template +pair rec(IT l, IT r) { + int n = distance(l, r); + if (n <= 3) { + QuadEdge* a = makeEdge(l[0], l[1]); + if (n == 2) return {a, a->rev()}; + QuadEdge* b = makeEdge(l[1], l[2]); + splice(a->rev(), b); + auto side = cross(l[0], l[1], l[2]); + QuadEdge* c = nullptr; + if (side != 0) c = connect(b, a); + if (side >= 0) return {a, b->rev()}; + else return {c->rev(), c}; + } + auto m = l + (n / 2); + auto [ldo, ldi] = rec(l, m); + auto [rdi, rdo] = rec(m, r); + while (true) { + if (cross(rdi->orig, ldi->orig, ldi->dest()) > 0) { + ldi = ldi->lnext(); + } else if (cross(ldi->orig, rdi->orig, rdi->dest()) < 0) { + rdi = rdi->rev()->onext; + } else break; + } + QuadEdge* base = connect(rdi->rev(), ldi); + if (ldi->orig == ldo->orig) ldo = base->rev(); + if (rdi->orig == rdo->orig) rdo = base; + while (true) { + QuadEdge* lcand = deleteAll(base->rev()->onext, base); + QuadEdge* rcand = deleteAll(base->oprev(), base); + if (!valid(lcand, base) && !valid(rcand, base)) break; + if (!valid(lcand, base) || (valid(rcand, base) && + circ(lcand->dest(), lcand->orig, rcand->orig, rcand->dest()))) { + base = connect(rcand, base->rev()); + } else { + base = connect(base->rev(), lcand->rev()); + }} + return {ldo, rdo}; +} + +vector delaunay(vector 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; + vector edges = {r}; + while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext; + auto add = [&](QuadEdge* e){ + QuadEdge* cur = e; + do { + cur->used = true; + pts.push_back(cur->orig); + edges.push_back(cur->rev()); + cur = cur->lnext(); + } while (cur != e); + }; + add(r); + pts.clear(); + for (int i = 0; i < sz(edges); i++) { + if (!edges[i]->used) add(edges[i]); + } + return pts; +} -- cgit v1.2.3