From 8ca4bbf3e4e7be7eb00dc83ed83969c992367a41 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 3 Feb 2023 19:39:14 +0100 Subject: simplified code --- geometry/polygon.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'geometry') diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 3a633af..6465fdb 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -40,13 +40,13 @@ bool inside(pt p, const vector& poly) { // Change line 43 and 49 >= if border counts as inside bool inside(pt p, const vector& hull) { int l = 0, r = sz(hull) - 1; - if (orientation(hull[0], hull[r], p) > 0) return false; + if (cross(hull[0], hull[r], p) > 0) return false; while (l + 1 < r) { int m = (l + r) / 2; - if (orientation(hull[0], hull[m], p) >= 0) l = m; + if (cross(hull[0], hull[m], p) >= 0) l = m; else r = m; } - return orientation(hull[l], hull[r], p) > 0; + return cross(hull[l], hull[r], p) > 0; } void rotateMin(vector& hull) { -- cgit v1.2.3 From c5fa5456eb8a31c5eb8af129bc6f3dc39c54a894 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 4 Feb 2023 13:05:14 +0100 Subject: fix --- geometry/polygon.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'geometry') diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 6465fdb..9dd4f66 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -2,7 +2,7 @@ // Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. double area(const vector& poly) { //poly[0] == poly.back() double res = 0; - for (int i = 0; i + 1 < n; i++) + for (int i = 0; i + 1 < sz(poly); i++) res += cross(poly[i], poly[i + 1]); return 0.5 * res; } @@ -27,7 +27,7 @@ bool inside(pt p, const vector& poly) { bool in = false; for (int i = 0; i + 1 < sz(poly); i++) { pt a = poly[i], b = poly[i + 1]; - if (pointOnLineSegment(a, b, b)) return false; + if (pointOnLineSegment(a, b, p)) return false; if (real(a) > real(b)) swap(a,b); if (real(a) <= real(p) && real(p) < real(b) && cross(p, a, b) < 0) { -- cgit v1.2.3 From 0ac199d769e6ff70aaf6a41d965b5e4c8525b570 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 4 Feb 2023 13:07:19 +0100 Subject: added comment --- geometry/polygon.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'geometry') diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 9dd4f66..23420a1 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -9,6 +9,8 @@ double area(const vector& poly) { //poly[0] == poly.back() // Anzahl drehungen einer Polyline um einen Punkt // p nicht auf rand und poly[0] == poly.back() +// res != 0 or (res & 1) != 0 um inside zu prüfen bei +// selbstschneidenden polygonen (definitions sache) ll windingNumber(pt p, const vector& poly) { ll res = 0; for (int i = 0; i + 1 < sz(poly); i++) { -- cgit v1.2.3 From 63b53894683dc5a9d89ecc4ab45bb25faafd770a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 4 Feb 2023 16:56:22 +0100 Subject: fix --- geometry/formulars.cpp | 6 +++--- geometry/linesAndSegments.cpp | 4 ++-- geometry/polygon.cpp | 4 ++-- 3 files changed, 7 insertions(+), 7 deletions(-) (limited to 'geometry') diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index 855ef1e..37cc4f4 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -21,9 +21,9 @@ double norm(pt a) {return dot(a, a);} double cross(pt a, pt b) {return imag(conj(a) * b);} double cross(pt p, pt a, pt b) {return cross(a - p, b - p);} -// -1 => gegen den Uhrzeigersinn -// 0 => kolliniear -// 1 => im Uhrzeigersinn. +// 1 => c links von a->b +// 0 => a, b und c kolliniear +// -1 => c rechts von a->b int orientation(pt a, pt b, pt c) { double orien = cross(b - a, c - a); return (orien > EPS) - (orien < -EPS); diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp index 3a8ac02..4da35b1 100644 --- a/geometry/linesAndSegments.cpp +++ b/geometry/linesAndSegments.cpp @@ -39,7 +39,7 @@ double distToLine(pt a, pt b, pt p) { // Liegt p auf der Geraden a-b? 2d und 3d bool pointOnLine(pt a, pt b, pt p) { - return orientation(a, b, p) == 0; + return cross(a, b, p) == 0; } // Test auf Linienschnitt zwischen a-b und c-d. @@ -57,7 +57,7 @@ pt lineIntersection(pt p0, pt p1, pt p2, pt p3) { // Liegt p auf der Strecke a-b? bool pointOnLineSegment(pt a, pt b, pt p) { - if (orientation(a, b, p) != 0) return false; + if (cross(a, b, p) != 0) return false; ld dist = norm(a - b); return norm(a - p) <= dist && norm(b - p) <= dist; } diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 23420a1..1620d7c 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -24,7 +24,7 @@ ll windingNumber(pt p, const vector& poly) { } // Testet, ob ein Punkt im Polygon liegt (beliebige Polygone). -// Ändere Zeile 31 falls rand zählt, poly[0] == poly.back() +// Ändere Zeile 32 falls rand zählt, poly[0] == poly.back() bool inside(pt p, const vector& poly) { bool in = false; for (int i = 0; i + 1 < sz(poly); i++) { @@ -39,7 +39,7 @@ bool inside(pt p, const vector& poly) { } // convex hull without duplicates, h[0] == h.back() -// Change line 43 and 49 >= if border counts as inside +// Change line 45 and 51 >= if border counts as inside bool inside(pt p, const vector& hull) { int l = 0, r = sz(hull) - 1; if (cross(hull[0], hull[r], p) > 0) return false; -- cgit v1.2.3