geometry/point.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <complex> | ||
| 4 | #include <tuple> | ||
| 5 | #include <istream> | ||
| 6 | #include <ostream> | ||
| 7 | #include <numeric> | ||
| 8 | |||
| 9 | namespace wala { | ||
| 10 | |||
| 11 | template <typename T, typename AreaT=T> struct Point { | ||
| 12 | public: | ||
| 13 | T x, y; | ||
| 14 | 3331997 | Point() : x(0), y(0) {} | |
| 15 | 130742101 | Point(T x_, T y_) : x(x_), y(y_) {} | |
| 16 | ✗ | template <typename U, typename V> explicit Point(const Point<U, V>& p) : x(p.x), y(p.y) {} | |
| 17 | ✗ | Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {} | |
| 18 | ✗ | Point(const std::complex<T>& p) : x(real(p)), y(imag(p)) {} | |
| 19 | ✗ | explicit operator std::pair<T, T> () const { return std::pair<T, T>(x, y); } | |
| 20 | ✗ | explicit operator std::complex<T> () const { return std::complex<T>(x, y); } | |
| 21 | ✗ | auto as_pair() const { return std::pair<T, T>(*this); } | |
| 22 | ✗ | auto as_complex() const { return std::complex<T>(*this); } | |
| 23 | |||
| 24 | ✗ | friend std::ostream& operator << (std::ostream& o, const Point& p) { return o << '(' << p.x << ',' << p.y << ')'; } | |
| 25 | 3331997 | friend std::istream& operator >> (std::istream& i, Point& p) { return i >> p.x >> p.y; } | |
| 26 |
8/8✓ Branch 2 → 3 taken 4640300 times.
✓ Branch 2 → 4 taken 60730740 times.
✓ Branch 3 → 4 taken 87 times.
✓ Branch 3 → 5 taken 4640213 times.
✓ Branch 5 → 6 taken 4638812 times.
✓ Branch 5 → 7 taken 60732228 times.
✓ Branch 6 → 7 taken 73 times.
✓ Branch 6 → 8 taken 4638739 times.
|
126101867 | friend bool operator == (const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; } |
| 27 | ✗ | friend bool operator != (const Point& a, const Point& b) { return !(a==b); } | |
| 28 | |||
| 29 | ✗ | Point operator + () const { return Point(+x, +y); } | |
| 30 | ✗ | Point operator - () const { return Point(-x, -y); } | |
| 31 | |||
| 32 | ✗ | Point& operator += (const Point& p) { x += p.x, y += p.y; return *this; } | |
| 33 | ✗ | Point& operator -= (const Point& p) { x -= p.x, y -= p.y; return *this; } | |
| 34 | ✗ | Point& operator *= (const T& t) { x *= t, y *= t; return *this; } | |
| 35 | ✗ | Point& operator /= (const T& t) { x /= t, y /= t; return *this; } | |
| 36 | |||
| 37 | ✗ | friend Point operator + (const Point& a, const Point& b) { return Point(a.x+b.x, a.y+b.y); } | |
| 38 | ✗ | friend Point operator - (const Point& a, const Point& b) { return Point(a.x-b.x, a.y-b.y); } | |
| 39 | ✗ | friend Point operator * (const Point& a, const T& t) { return Point(a.x*t, a.y*t); } | |
| 40 | ✗ | friend Point operator * (const T& t ,const Point& a) { return Point(t*a.x, t*a.y); } | |
| 41 | ✗ | friend Point operator / (const Point& a, const T& t) { return Point(a.x/t, a.y/t); } | |
| 42 | |||
| 43 | ✗ | AreaT dist2() const { return AreaT(x) * AreaT(x) + AreaT(y) * AreaT(y); } | |
| 44 | ✗ | auto dist() const { return std::sqrt(dist2()); } | |
| 45 | ✗ | Point unit() const { return *this / this->dist(); } | |
| 46 | ✗ | auto angle() const { return std::atan2(y, x); } | |
| 47 | |||
| 48 | ✗ | T int_norm() const { return std::gcd(x,y); } | |
| 49 | ✗ | Point int_unit() const { if (!x && !y) return *this; return *this / this->int_norm(); } | |
| 50 | |||
| 51 | // Convenient free-functions, mostly for generic interop | ||
| 52 | ✗ | friend auto norm(const Point& a) { return a.dist2(); } | |
| 53 | ✗ | friend auto abs(const Point& a) { return a.dist(); } | |
| 54 | ✗ | friend auto unit(const Point& a) { return a.unit(); } | |
| 55 | ✗ | friend auto arg(const Point& a) { return a.angle(); } | |
| 56 | ✗ | friend auto int_norm(const Point& a) { return a.int_norm(); } | |
| 57 | ✗ | friend auto int_unit(const Point& a) { return a.int_unit(); } | |
| 58 | |||
| 59 | ✗ | Point perp_cw() const { return Point(y, -x); } | |
| 60 | ✗ | Point perp_ccw() const { return Point(-y, x); } | |
| 61 | |||
| 62 | 18497507 | friend AreaT dot(const Point& a, const Point& b) { return AreaT(a.x) * AreaT(b.x) + AreaT(a.y) * AreaT(b.y); } | |
| 63 | 193085463 | friend AreaT cross(const Point& a, const Point& b) { return AreaT(a.x) * AreaT(b.y) - AreaT(a.y) * AreaT(b.x); } | |
| 64 | ✗ | friend AreaT cross3(const Point& a, const Point& b, const Point& c) { return cross(b-a, c-a); } | |
| 65 | |||
| 66 | // Complex numbers and rotation | ||
| 67 | ✗ | friend Point conj(const Point& a) { return Point(a.x, -a.y); } | |
| 68 | |||
| 69 | // Returns conj(a) * b | ||
| 70 | ✗ | friend Point dot_cross(const Point& a, const Point& b) { return Point(dot(a, b), cross(a, b)); } | |
| 71 | ✗ | friend Point cmul(const Point& a, const Point& b) { return dot_cross(conj(a), b); } | |
| 72 | ✗ | friend Point cdiv(const Point& a, const Point& b) { return dot_cross(b, a) / b.dist2(); } | |
| 73 | |||
| 74 | // Must be a unit vector; otherwise multiplies the result by abs(u) | ||
| 75 | ✗ | Point rotate(const Point& u) const { return dot_cross(conj(u), *this); } | |
| 76 | ✗ | Point unrotate(const Point& u) const { return dot_cross(u, *this); } | |
| 77 | |||
| 78 | ✗ | friend bool lex_less(const Point& a, const Point& b) { | |
| 79 | ✗ | return std::tie(a.x, a.y) < std::tie(b.x, b.y); | |
| 80 | } | ||
| 81 | |||
| 82 | ✗ | friend bool same_dir(const Point& a, const Point& b) { return cross(a,b) == 0 && dot(a,b) > 0; } | |
| 83 | |||
| 84 | // check if 180 <= s..t < 360 | ||
| 85 |
2/2✓ Branch 2 → 3 taken 112244573 times.
✓ Branch 2 → 4 taken 18497507 times.
|
130742080 | friend bool is_reflex(const Point& a, const Point& b) { auto c = cross(a,b); return c ? (c < 0) : (dot(a, b) < 0); } |
| 86 | |||
| 87 | // operator < (s,t) for angles in [base,base+2pi) | ||
| 88 | ✗ | friend bool angle_less_from(const Point& base, const Point& s, const Point& t) { | |
| 89 | ✗ | int r = is_reflex(base, s) - is_reflex(base, t); | |
| 90 | ✗ | return r ? (r < 0) : (0 < cross(s, t)); | |
| 91 | } | ||
| 92 | // operator < (s,t) for angles in (base,base+2pi] | ||
| 93 | 65371040 | friend bool angle_less_upto(const Point& base, const Point& s, const Point& t) { | |
| 94 | 65371040 | int r = is_reflex(t, base) - is_reflex(s, base); | |
| 95 |
2/2✓ Branch 2 → 3 taken 3027657 times.
✓ Branch 2 → 4 taken 62343383 times.
|
65371040 | return r ? (r < 0) : (0 < cross(s, t)); |
| 96 | } | ||
| 97 | |||
| 98 | ✗ | friend auto angle_cmp_from(const Point& base) { | |
| 99 | ✗ | return [base](const Point& s, const Point& t) { return angle_less_from(base, s, t); }; | |
| 100 | } | ||
| 101 | 21 | friend auto angle_cmp_upto(const Point& base) { | |
| 102 | 65371040 | return [base](const Point& s, const Point& t) { return angle_less_upto(base, s, t); }; | |
| 103 | } | ||
| 104 | ✗ | friend auto angle_cmp_center_from(const Point& center, const Point& dir) { | |
| 105 | ✗ | return [center, dir](const Point& s, const Point& t) -> bool { return angle_less_from(dir, s-center, t-center); }; | |
| 106 | } | ||
| 107 | ✗ | friend auto angle_cmp_center_upto(const Point& center, const Point& dir) { | |
| 108 | ✗ | return [center, dir](const Point& s, const Point& t) -> bool { return angle_less_upto(dir, s-center, t-center); }; | |
| 109 | } | ||
| 110 | |||
| 111 | // is p in [s,t] taken ccw? 1/0/-1 for in/border/out | ||
| 112 | ✗ | friend int angle_between(const Point& s, const Point& t, const Point& p) { | |
| 113 | ✗ | if (same_dir(p, s) || same_dir(p, t)) return 0; | |
| 114 | ✗ | return angle_less_from(s, p, t) ? 1 : -1; | |
| 115 | } | ||
| 116 | }; | ||
| 117 | |||
| 118 | } // namespace wala | ||
| 119 |