diff options
Diffstat (limited to 'geometry')
| -rw-r--r-- | geometry/convexHull.cpp | 49 | ||||
| -rw-r--r-- | geometry/formulars.cpp | 27 | ||||
| -rw-r--r-- | geometry/geometry.tex | 5 |
3 files changed, 79 insertions, 2 deletions
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 <algorithm> +#include <iostream> +#include <sstream> +#include <string> +#include <vector> +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<point> convexHull(vector<point> P){ + int n = P.size(), k = 0; + vector<point> 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; +} 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<pt> &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<pt> &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/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} |