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/linesAndSegments.cpp | 89 +++++++++++++++++++++++++++++++++++ 1 file changed, 89 insertions(+) create mode 100644 content/geometry/linesAndSegments.cpp (limited to 'content/geometry/linesAndSegments.cpp') diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp new file mode 100644 index 0000000..1e21cba --- /dev/null +++ b/content/geometry/linesAndSegments.cpp @@ -0,0 +1,89 @@ +// Liegt p auf der Geraden a-b? 2d und 3d +bool pointOnLine(pt a, pt b, pt p) { + return ccw(a, b, p) == 0; +} + +// Test auf Linienschnitt zwischen a-b und c-d. (nicht identisch) +bool lineIntersection(pt a, pt b, pt c, pt d) { + return abs(cross(a - b, c - d)) < EPS; +} + +// Berechnet den Schnittpunkt der Graden a-b und c-d. +// die Graden dürfen nicht parallel sein! +pt lineIntersection2(pt a, pt b, pt c, pt d) { + double x = cross(b - a, d - c); + double y = cross(c - a, d - c); + return a + y/x*(b - a); +} + +// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d +double distToLine(pt a, pt b, pt p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +// Projiziert p auf die Gerade a-b +pt projectToLine(pt a, pt b, pt p) { + return a + (b - a) * dot(p - a, b - a) / norm(b - a); +} + +// sortiert alle Punkte pts auf einer Linie entsprechend dir +void sortLine(pt dir, vector& pts) { // (2d und 3d) + sort(all(pts), [&](pt a, pt b){ + return dot(dir, a) < dot(dir, b); + }); +} + +// Liegt p auf der Strecke a-b? (nutze < für inberhalb) +bool pointOnSegment(pt a, pt b, pt p) { + if (ccw(a, b, p) != 0) return false; + auto dist = norm(a - b); + return norm(a - p) <= dist && norm(b - p) <= dist; +} + +// Entfernung von Punkt p zur Strecke a-b. +double distToSegment(pt a, pt b, pt p) { + if (a == b) return abs(p - a); + if (dot(p - a, b - a) <= 0) return abs(p - a); + if (dot(p - b, b - a) >= 0) return abs(p - b); + return distToLine(a, b, p); +} + +// Test auf Streckenschnitt zwischen a-b und c-d. +bool segmentIntersection(pt a, pt b, pt c, pt d) { + if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) + return pointOnSegment(a,b,c) || + pointOnSegment(a,b,d) || + pointOnSegment(c,d,a) || + pointOnSegment(c,d,b); + return ccw(a, b, c) * ccw(a, b, d) <= 0 && + ccw(c, d, a) * ccw(c, d, b) <= 0; +} + +// Berechnet die Schnittpunkte der Strecken a-b und c-d. +// Enthält entweder keinen Punkt, den einzigen Schnittpunkt +// oder die Endpunkte der Schnittstrecke. +vector 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 (y < -EPS || y-x > EPS || z < -EPS || z-x > EPS) return {}; + if (x > EPS) return {a + y/x*(b - a)}; + vector result; + auto insertUnique = [&](pt p) { + for (auto q : result) if (abs(p - q) < EPS) return; + result.push_back(p); + }; + if (dot(c-a, d-a) < EPS) insertUnique(a); + if (dot(c-b, d-b) < EPS) insertUnique(b); + if (dot(a-c, b-c) < EPS) insertUnique(c); + if (dot(a-d, b-d) < EPS) insertUnique(d); + return result; +} + +// Kürzeste Entfernung zwischen den Strecken a-b und c-d. +double distBetweenSegments(pt a, pt b, pt c, pt d) { + if (segmentIntersection(a, b, c, d)) return 0.0; + return min({distToSegment(a, b, c), distToSegment(a, b, d), + distToSegment(c, d, a), distToSegment(c, d, b)}); +} -- cgit v1.2.3