From adc1aa01f8fc085ab72df0615cfe70c301922b5f Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:56:08 +0100 Subject: Create convexHull Adding Convex-Hull-Implementation --- geometry/convexHull | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 geometry/convexHull (limited to 'geometry') diff --git a/geometry/convexHull b/geometry/convexHull new file mode 100644 index 0000000..5d6bc16 --- /dev/null +++ b/geometry/convexHull @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include +using namespace std; + +struct point { + double x, y; + point(){} point(double x, double y) : x(x), y(y) {} + bool operator <(const point &p) const { + return x < p.x || (x == p.x && y < p.y); + } +}; + +// 2D cross product. +// Return a positive value, if OAB makes a counter-clockwise turn, +// negative for clockwise turn, and zero if the points are collinear. +double cross(const point &O, const point &A, const point &B){ + double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); + if (fabs(d) < 1e-9) return 0.0; + return d; +} + +// Returns a list of points on the convex hull in counter-clockwise order. +// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test +// Note: the last point in the returned list is the same as the first one. +vector convexHull(vector P){ + int n = P.size(), k = 0; + vector H(2*n); + + // Sort points lexicographically + sort(P.begin(), P.end()); + + // Build lower hull + for (int i = 0; i < n; i++) { + while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + // Build upper hull + for (int i = n-2, t = k+1; i >= 0; i--) { + while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + H.resize(k); + return H; +} -- cgit v1.2.3 From bb5ed48ce293212affa6c911d88220260f413189 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:56:59 +0100 Subject: Adding Convex-Hull-Implementation --- geometry/convexHull.cpp | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 geometry/convexHull.cpp (limited to 'geometry') diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp new file mode 100644 index 0000000..5d6bc16 --- /dev/null +++ b/geometry/convexHull.cpp @@ -0,0 +1,49 @@ +#include +#include +#include +#include +#include +using namespace std; + +struct point { + double x, y; + point(){} point(double x, double y) : x(x), y(y) {} + bool operator <(const point &p) const { + return x < p.x || (x == p.x && y < p.y); + } +}; + +// 2D cross product. +// Return a positive value, if OAB makes a counter-clockwise turn, +// negative for clockwise turn, and zero if the points are collinear. +double cross(const point &O, const point &A, const point &B){ + double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); + if (fabs(d) < 1e-9) return 0.0; + return d; +} + +// Returns a list of points on the convex hull in counter-clockwise order. +// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test +// Note: the last point in the returned list is the same as the first one. +vector convexHull(vector P){ + int n = P.size(), k = 0; + vector H(2*n); + + // Sort points lexicographically + sort(P.begin(), P.end()); + + // Build lower hull + for (int i = 0; i < n; i++) { + while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + // Build upper hull + for (int i = n-2, t = k+1; i >= 0; i--) { + while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; + H[k++] = P[i]; + } + + H.resize(k); + return H; +} -- cgit v1.2.3 From 21d8d8f405048b1d9e4597f0f6fabc45ffdff20f Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:57:15 +0100 Subject: wrong --- geometry/convexHull | 49 ------------------------------------------------- 1 file changed, 49 deletions(-) delete mode 100644 geometry/convexHull (limited to 'geometry') diff --git a/geometry/convexHull b/geometry/convexHull deleted file mode 100644 index 5d6bc16..0000000 --- a/geometry/convexHull +++ /dev/null @@ -1,49 +0,0 @@ -#include -#include -#include -#include -#include -using namespace std; - -struct point { - double x, y; - point(){} point(double x, double y) : x(x), y(y) {} - bool operator <(const point &p) const { - return x < p.x || (x == p.x && y < p.y); - } -}; - -// 2D cross product. -// Return a positive value, if OAB makes a counter-clockwise turn, -// negative for clockwise turn, and zero if the points are collinear. -double cross(const point &O, const point &A, const point &B){ - double d = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); - if (fabs(d) < 1e-9) return 0.0; - return d; -} - -// Returns a list of points on the convex hull in counter-clockwise order. -// Colinear points are not in the convex hull, if you want colinear points in the hull remove "=" in the CCW-Test -// Note: the last point in the returned list is the same as the first one. -vector convexHull(vector P){ - int n = P.size(), k = 0; - vector H(2*n); - - // Sort points lexicographically - sort(P.begin(), P.end()); - - // Build lower hull - for (int i = 0; i < n; i++) { - while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; - H[k++] = P[i]; - } - - // Build upper hull - for (int i = n-2, t = k+1; i >= 0; i--) { - while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0.0) k--; - H[k++] = P[i]; - } - - H.resize(k); - return H; -} -- cgit v1.2.3 From b378c61ee0b60c9176b309b82d5d6fc47ed740b0 Mon Sep 17 00:00:00 2001 From: kittobi1992 Date: Sat, 22 Nov 2014 16:58:03 +0100 Subject: update tex mit convex hull --- geometry/geometry.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'geometry') diff --git a/geometry/geometry.tex b/geometry/geometry.tex index b48a51e..de7b2f6 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -6,5 +6,8 @@ \subsection{Geraden} \lstinputlisting{geometry/lines.cpp} +\subsection{Konvexe Hülle} +\lstinputlisting{geometry/convexHull.cpp} + \subsection{Formeln - \lstinline{std::complex}} -\lstinputlisting{geometry/formulars.cpp} \ No newline at end of file +\lstinputlisting{geometry/formulars.cpp} -- cgit v1.2.3 From 597fd2a7cf8b39c49c890e836102d1c7ab582e99 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 17:51:22 +0100 Subject: bisschen mehr Geometrie --- geometry/formulars.cpp | 27 ++++++++++++++++++++++++++- tcr.pdf | Bin 313603 -> 315778 bytes 2 files changed, 26 insertions(+), 1 deletion(-) (limited to 'geometry') diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp index 6984be9..5369b50 100644 --- a/geometry/formulars.cpp +++ b/geometry/formulars.cpp @@ -55,4 +55,29 @@ bool pointOnLine(pt a, pt b, pt p) { //testet, ob d in der gleichen Ebene liegt wie a, b, und c bool isCoplanar(pt a, pt b, pt c, pt d) { return (b - a) * (c - a) * (d - a) == 0; -} \ No newline at end of file +} +//berechnet den Flaecheninhalt eines Polygons (nicht selbstschneidend) +double areaOfPolygon(vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + double res = 0; int n = polygon.size(); + for (int i = 0; i < (int)polygon.size(); i++) + res += real(polygon[i]) * imag(polygon[(i + 1) % n]) - real(polygon[(i + 1) % n]) * imag(polygon[i]); + return 0.5 * abs(res); +} +//testet, ob sich zwei Rechtecke (p1, p2) und (p3, p4) schneiden (jeweils gegenueberliegende Ecken) +bool rectIntersection(pt p1, pt p2, pt p3, pt p4) { + double minx12 = min(real(p1), real(p2)), maxx12 = max(real(p1), real(p2)); + double minx34 = min(real(p3), real(p4)), maxx34 = max(real(p3), real(p4)); + double miny12 = min(imag(p1), imag(p2)), maxy12 = max(imag(p1), imag(p2)); + double miny34 = min(imag(p3), imag(p4)), maxy34 = max(imag(p3), imag(p4)); + return (maxx12 >= minx34) && (maxx34 >= minx12) && (maxy12 >= miny34) && (maxy34 >= miny12); +} +//testet, ob ein Punkt im Polygon liegt (beliebige Polygone) +bool pointInPolygon(pt p, vector &polygon) { //jeder Eckpunkt nur einmal im Vektor + pt rayEnd = p + pt(1, 1000000); + int counter = 0, n = polygon.size(); + for (int i = 0; i < n; i++) { + pt start = polygon[i], end = polygon[(i + 1) % n]; + if (lineSegmentIntersection(p, rayEnd, start, end)) counter++; + } + return counter & 1; +} diff --git a/tcr.pdf b/tcr.pdf index c735878..e16a3dd 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3