| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** @file | ||
| 2 | * @brief Cartesian point / 2D vector and related operations | ||
| 3 | *//* | ||
| 4 | * Authors: | ||
| 5 | * Michael G. Sloan <mgsloan@gmail.com> | ||
| 6 | * Nathan Hurst <njh@njhurst.com> | ||
| 7 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 8 | * | ||
| 9 | * Copyright (C) 2006-2009 Authors | ||
| 10 | * | ||
| 11 | * This library is free software; you can redistribute it and/or | ||
| 12 | * modify it either under the terms of the GNU Lesser General Public | ||
| 13 | * License version 2.1 as published by the Free Software Foundation | ||
| 14 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 15 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 16 | * notice, a recipient may use your version of this file under either | ||
| 17 | * the MPL or the LGPL. | ||
| 18 | * | ||
| 19 | * You should have received a copy of the LGPL along with this library | ||
| 20 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 21 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 22 | * You should have received a copy of the MPL along with this library | ||
| 23 | * in the file COPYING-MPL-1.1 | ||
| 24 | * | ||
| 25 | * The contents of this file are subject to the Mozilla Public License | ||
| 26 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 27 | * compliance with the License. You may obtain a copy of the License at | ||
| 28 | * http://www.mozilla.org/MPL/ | ||
| 29 | * | ||
| 30 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 31 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 32 | * the specific language governing rights and limitations. | ||
| 33 | */ | ||
| 34 | |||
| 35 | #ifndef LIB2GEOM_SEEN_POINT_H | ||
| 36 | #define LIB2GEOM_SEEN_POINT_H | ||
| 37 | |||
| 38 | #include <cassert> | ||
| 39 | #include <iostream> | ||
| 40 | #include <iterator> | ||
| 41 | #include <tuple> | ||
| 42 | #include <boost/functional/hash.hpp> | ||
| 43 | #include <boost/operators.hpp> | ||
| 44 | #include <2geom/forward.h> | ||
| 45 | #include <2geom/coord.h> | ||
| 46 | #include <2geom/int-point.h> | ||
| 47 | #include <2geom/math-utils.h> | ||
| 48 | #include <2geom/utils.h> | ||
| 49 | |||
| 50 | namespace Geom { | ||
| 51 | |||
| 52 | class Point | ||
| 53 | : boost::additive< Point | ||
| 54 | , boost::totally_ordered< Point | ||
| 55 | , boost::multiplicative< Point, Coord | ||
| 56 | , boost::multiplicative< Point | ||
| 57 | , boost::multiplicative< Point, IntPoint | ||
| 58 | , MultipliableNoncommutative< Point, Affine | ||
| 59 | , MultipliableNoncommutative< Point, Translate | ||
| 60 | , MultipliableNoncommutative< Point, Rotate | ||
| 61 | , MultipliableNoncommutative< Point, Scale | ||
| 62 | , MultipliableNoncommutative< Point, HShear | ||
| 63 | , MultipliableNoncommutative< Point, VShear | ||
| 64 | , MultipliableNoncommutative< Point, Zoom | ||
| 65 | >>>>>>>>>>>> // base class chaining, see documentation for Boost.Operator | ||
| 66 | { | ||
| 67 | Coord _pt[2] = { 0, 0 }; | ||
| 68 | public: | ||
| 69 | using D1Value = Coord; | ||
| 70 | using D1Reference = Coord &; | ||
| 71 | using D1ConstReference = Coord const &; | ||
| 72 | |||
| 73 | /// @name Create points | ||
| 74 | /// @{ | ||
| 75 | /** Construct a point at the origin. */ | ||
| 76 | 6709890 | constexpr Point() = default; | |
| 77 | /** Construct a point from its coordinates. */ | ||
| 78 | 5327826 | constexpr Point(Coord x, Coord y) | |
| 79 | 5327826 | : _pt{ x, y } | |
| 80 | 5327826 | {} | |
| 81 | /** Construct from integer point. */ | ||
| 82 | constexpr Point(IntPoint const &p) | ||
| 83 | : Point(p[X], p[Y]) | ||
| 84 | {} | ||
| 85 | /** @brief Construct a point from its polar coordinates. | ||
| 86 | * The angle is specified in radians, in the mathematical convention (increasing | ||
| 87 | * counter-clockwise from +X). */ | ||
| 88 | static Point polar(Coord angle, Coord radius) { | ||
| 89 | return polar(angle) * radius; | ||
| 90 | } | ||
| 91 | /** @brief Construct an unit vector from its angle. | ||
| 92 | * The angle is specified in radians, in the mathematical convention (increasing | ||
| 93 | * counter-clockwise from +X). */ | ||
| 94 | static Point polar(Coord angle); | ||
| 95 | /// @} | ||
| 96 | |||
| 97 | /// @name Access the coordinates of a point | ||
| 98 | /// @{ | ||
| 99 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 8092860 times.
|
8092860 | Coord operator[](unsigned i) const { assert(i < 2); return _pt[i]; } |
| 100 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 15184452 times.
|
15184452 | Coord &operator[](unsigned i) { assert(i < 2); return _pt[i]; } |
| 101 | 241450088 | constexpr Coord operator[](Dim2 d) const noexcept { return _pt[d]; } | |
| 102 | 748539 | constexpr Coord &operator[](Dim2 d) noexcept { return _pt[d]; } | |
| 103 | |||
| 104 | 216 | constexpr Coord x() const noexcept { return _pt[X]; } | |
| 105 | 3 | constexpr Coord &x() noexcept { return _pt[X]; } | |
| 106 | 80 | constexpr Coord y() const noexcept { return _pt[Y]; } | |
| 107 | 102 | constexpr Coord &y() noexcept { return _pt[Y]; } | |
| 108 | |||
| 109 | // Structured binding support | ||
| 110 | template <size_t I> constexpr Coord get() const { static_assert(I < 2); return _pt[I]; } | ||
| 111 | template <size_t I> constexpr Coord &get() { static_assert(I < 2); return _pt[I]; } | ||
| 112 | /// @} | ||
| 113 | |||
| 114 | /// @name Vector operations | ||
| 115 | /// @{ | ||
| 116 | /** @brief Compute the distance from origin. | ||
| 117 | * @return Length of the vector from origin to this point */ | ||
| 118 | 10566246 | Coord length() const { return std::hypot(_pt[X], _pt[Y]); } | |
| 119 | 2388 | constexpr Coord lengthSq() const { return _pt[X] * _pt[X] + _pt[Y] * _pt[Y]; } | |
| 120 | void normalize(); | ||
| 121 | 20128 | Point normalized() const { | |
| 122 | 20128 | auto ret = *this; | |
| 123 |
1/2✓ Branch 1 taken 20128 times.
✗ Branch 2 not taken.
|
20128 | ret.normalize(); |
| 124 | 20128 | return ret; | |
| 125 | } | ||
| 126 | |||
| 127 | /** @brief Return a point like this point but rotated -90 degrees. | ||
| 128 | * If the y axis grows downwards and the x axis grows to the | ||
| 129 | * right, then this is 90 degrees counter-clockwise. */ | ||
| 130 | ✗ | constexpr Point ccw() const { | |
| 131 | ✗ | return Point(_pt[Y], -_pt[X]); | |
| 132 | } | ||
| 133 | |||
| 134 | /** @brief Return a point like this point but rotated +90 degrees. | ||
| 135 | * If the y axis grows downwards and the x axis grows to the | ||
| 136 | * right, then this is 90 degrees clockwise. */ | ||
| 137 | 27487 | constexpr Point cw() const { | |
| 138 | 27487 | return Point(-_pt[Y], _pt[X]); | |
| 139 | } | ||
| 140 | /// @} | ||
| 141 | |||
| 142 | /// @name Vector-like arithmetic operations | ||
| 143 | /// @{ | ||
| 144 | 603178 | constexpr Point operator-() const { | |
| 145 | 603178 | return Point(-_pt[X], -_pt[Y]); | |
| 146 | } | ||
| 147 | 64328421 | constexpr Point &operator+=(Point const &o) { | |
| 148 | 64328421 | _pt[X] += o._pt[X]; | |
| 149 | 64328421 | _pt[Y] += o._pt[Y]; | |
| 150 | 64328421 | return *this; | |
| 151 | } | ||
| 152 | 53191665 | constexpr Point &operator-=(Point const &o) { | |
| 153 | 53191665 | _pt[X] -= o._pt[X]; | |
| 154 | 53191665 | _pt[Y] -= o._pt[Y]; | |
| 155 | 53191665 | return *this; | |
| 156 | } | ||
| 157 | 130560333 | constexpr Point &operator*=(Coord s) { | |
| 158 |
2/2✓ Branch 0 taken 261120666 times.
✓ Branch 1 taken 130560333 times.
|
391680999 | for (auto &i : _pt) i *= s; |
| 159 | 130560333 | return *this; | |
| 160 | } | ||
| 161 | constexpr Point &operator*=(Point const &o) { | ||
| 162 | _pt[X] *= o._pt[X]; | ||
| 163 | _pt[Y] *= o._pt[Y]; | ||
| 164 | return *this; | ||
| 165 | } | ||
| 166 | constexpr Point &operator*=(IntPoint const &o) { | ||
| 167 | _pt[X] *= o.x(); | ||
| 168 | _pt[Y] *= o.y(); | ||
| 169 | return *this; | ||
| 170 | } | ||
| 171 | 1595586 | constexpr Point &operator/=(Coord s) { | |
| 172 |
2/2✓ Branch 0 taken 3191172 times.
✓ Branch 1 taken 1595586 times.
|
4786758 | for (auto &i : _pt) i /= s; |
| 173 | 1595586 | return *this; | |
| 174 | } | ||
| 175 | constexpr Point &operator/=(Point const &o) { | ||
| 176 | _pt[X] /= o._pt[X]; | ||
| 177 | _pt[Y] /= o._pt[Y]; | ||
| 178 | return *this; | ||
| 179 | } | ||
| 180 | constexpr Point &operator/=(IntPoint const &o) { | ||
| 181 | _pt[X] /= o.x(); | ||
| 182 | _pt[Y] /= o.y(); | ||
| 183 | return *this; | ||
| 184 | } | ||
| 185 | /// @} | ||
| 186 | |||
| 187 | /// @name Affine transformations | ||
| 188 | /// @{ | ||
| 189 | Point &operator*=(Affine const &m); | ||
| 190 | // implemented in transforms.cpp | ||
| 191 | Point &operator*=(Translate const &t); | ||
| 192 | Point &operator*=(Scale const &s); | ||
| 193 | Point &operator*=(Rotate const &r); | ||
| 194 | Point &operator*=(HShear const &s); | ||
| 195 | Point &operator*=(VShear const &s); | ||
| 196 | Point &operator*=(Zoom const &z); | ||
| 197 | /// @} | ||
| 198 | |||
| 199 | /// @name Conversion to integer points | ||
| 200 | /// @{ | ||
| 201 | /** @brief Round to nearest integer coordinates. */ | ||
| 202 | ✗ | IntPoint round() const { | |
| 203 | ✗ | return IntPoint(::round(_pt[X]), ::round(_pt[Y])); | |
| 204 | } | ||
| 205 | /** @brief Round coordinates downwards. */ | ||
| 206 | IntPoint floor() const { | ||
| 207 | return IntPoint(::floor(_pt[X]), ::floor(_pt[Y])); | ||
| 208 | } | ||
| 209 | /** @brief Round coordinates upwards. */ | ||
| 210 | IntPoint ceil() const { | ||
| 211 | return IntPoint(::ceil(_pt[X]), ::ceil(_pt[Y])); | ||
| 212 | } | ||
| 213 | /// @} | ||
| 214 | |||
| 215 | /// @name Various utilities | ||
| 216 | /// @{ | ||
| 217 | /** @brief Check whether both coordinates are finite. */ | ||
| 218 | bool isFinite() const { | ||
| 219 | for (auto i : _pt) { | ||
| 220 | if (!std::isfinite(i)) { | ||
| 221 | return false; | ||
| 222 | } | ||
| 223 | } | ||
| 224 | return true; | ||
| 225 | } | ||
| 226 | /** @brief Check whether both coordinates are zero. */ | ||
| 227 | 760200 | constexpr bool isZero() const { | |
| 228 |
3/4✓ Branch 0 taken 150107 times.
✓ Branch 1 taken 610093 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 150107 times.
|
760200 | return _pt[X] == 0 && _pt[Y] == 0; |
| 229 | } | ||
| 230 | /** @brief Check whether the length of the vector is close to 1. */ | ||
| 231 | bool isNormalized(Coord eps = EPSILON) const { | ||
| 232 | return are_near(length(), 1.0, eps); | ||
| 233 | } | ||
| 234 | /** @brief Equality operator. | ||
| 235 | * This tests for exact identity (as opposed to are_near()). Note that due to numerical | ||
| 236 | * errors, this test might return false even if the points should be identical. */ | ||
| 237 | 5104743 | constexpr bool operator==(Point const &p) const { | |
| 238 |
4/4✓ Branch 1 taken 4343264 times.
✓ Branch 2 taken 761479 times.
✓ Branch 4 taken 3875199 times.
✓ Branch 5 taken 468065 times.
|
5104743 | return _pt[X] == p[X] && _pt[Y] == p[Y]; |
| 239 | } | ||
| 240 | /** @brief Lexicographical ordering for points. | ||
| 241 | * Y coordinate is regarded as more significant. When sorting according to this | ||
| 242 | * ordering, the points will be sorted according to the Y coordinate, and within | ||
| 243 | * points with the same Y coordinate according to the X coordinate. */ | ||
| 244 | ✗ | constexpr bool operator<(Point const &p) const { | |
| 245 | ✗ | return _pt[Y] < p[Y] || (_pt[Y] == p[Y] && _pt[X] < p[X]); | |
| 246 | } | ||
| 247 | /// @} | ||
| 248 | |||
| 249 | /** @brief Lexicographical ordering functor. | ||
| 250 | * @param d The dimension with higher significance */ | ||
| 251 | template <Dim2 DIM> struct LexLess; | ||
| 252 | template <Dim2 DIM> struct LexGreater; | ||
| 253 | //template <Dim2 DIM, typename First = std::less<Coord>, typename Second = std::less<Coord> > LexOrder; | ||
| 254 | /** @brief Lexicographical ordering functor with runtime dimension. */ | ||
| 255 | struct LexLessRt { | ||
| 256 | LexLessRt(Dim2 d) : dim(d) {} | ||
| 257 | inline bool operator()(Point const &a, Point const &b) const; | ||
| 258 | private: | ||
| 259 | Dim2 dim; | ||
| 260 | }; | ||
| 261 | struct LexGreaterRt { | ||
| 262 | LexGreaterRt(Dim2 d) : dim(d) {} | ||
| 263 | inline bool operator()(Point const &a, Point const &b) const; | ||
| 264 | private: | ||
| 265 | Dim2 dim; | ||
| 266 | }; | ||
| 267 | }; | ||
| 268 | |||
| 269 | /** @brief Output operator for points. | ||
| 270 | * Prints out the coordinates. | ||
| 271 | * @relates Point */ | ||
| 272 | std::ostream &operator<<(std::ostream &out, Point const &p); | ||
| 273 | |||
| 274 | template<> struct Point::LexLess<X> { | ||
| 275 | typedef std::less<Coord> Primary; | ||
| 276 | typedef std::less<Coord> Secondary; | ||
| 277 | typedef std::less<Coord> XOrder; | ||
| 278 | typedef std::less<Coord> YOrder; | ||
| 279 | 10021 | bool operator()(Point const &a, Point const &b) const { | |
| 280 |
6/6✓ Branch 2 taken 7382 times.
✓ Branch 3 taken 2639 times.
✓ Branch 6 taken 511 times.
✓ Branch 7 taken 6871 times.
✓ Branch 10 taken 281 times.
✓ Branch 11 taken 230 times.
|
10021 | return a[X] < b[X] || (a[X] == b[X] && a[Y] < b[Y]); |
| 281 | } | ||
| 282 | }; | ||
| 283 | template<> struct Point::LexLess<Y> { | ||
| 284 | typedef std::less<Coord> Primary; | ||
| 285 | typedef std::less<Coord> Secondary; | ||
| 286 | typedef std::less<Coord> XOrder; | ||
| 287 | typedef std::less<Coord> YOrder; | ||
| 288 | bool operator()(Point const &a, Point const &b) const { | ||
| 289 | return a[Y] < b[Y] || (a[Y] == b[Y] && a[X] < b[X]); | ||
| 290 | } | ||
| 291 | }; | ||
| 292 | template<> struct Point::LexGreater<X> { | ||
| 293 | typedef std::greater<Coord> Primary; | ||
| 294 | typedef std::greater<Coord> Secondary; | ||
| 295 | typedef std::greater<Coord> XOrder; | ||
| 296 | typedef std::greater<Coord> YOrder; | ||
| 297 | 2824 | bool operator()(Point const &a, Point const &b) const { | |
| 298 |
6/6✓ Branch 2 taken 1431 times.
✓ Branch 3 taken 1393 times.
✓ Branch 6 taken 363 times.
✓ Branch 7 taken 1068 times.
✓ Branch 10 taken 133 times.
✓ Branch 11 taken 230 times.
|
2824 | return a[X] > b[X] || (a[X] == b[X] && a[Y] > b[Y]); |
| 299 | } | ||
| 300 | }; | ||
| 301 | template<> struct Point::LexGreater<Y> { | ||
| 302 | typedef std::greater<Coord> Primary; | ||
| 303 | typedef std::greater<Coord> Secondary; | ||
| 304 | typedef std::greater<Coord> XOrder; | ||
| 305 | typedef std::greater<Coord> YOrder; | ||
| 306 | bool operator()(Point const &a, Point const &b) const { | ||
| 307 | return a[Y] > b[Y] || (a[Y] == b[Y] && a[X] > b[X]); | ||
| 308 | } | ||
| 309 | }; | ||
| 310 | inline bool Point::LexLessRt::operator()(Point const &a, Point const &b) const { | ||
| 311 | return dim ? Point::LexLess<Y>()(a, b) : Point::LexLess<X>()(a, b); | ||
| 312 | } | ||
| 313 | inline bool Point::LexGreaterRt::operator()(Point const &a, Point const &b) const { | ||
| 314 | return dim ? Point::LexGreater<Y>()(a, b) : Point::LexGreater<X>()(a, b); | ||
| 315 | } | ||
| 316 | |||
| 317 | /** @brief Compute the second (Euclidean) norm of @a p. | ||
| 318 | * This corresponds to the length of @a p. The result will not overflow even if | ||
| 319 | * \f$p_X^2 + p_Y^2\f$ is larger that the maximum value that can be stored | ||
| 320 | * in a <code>double</code>. | ||
| 321 | * @return \f$\sqrt{p_X^2 + p_Y^2}\f$ | ||
| 322 | * @relates Point */ | ||
| 323 | 4 | inline Coord L2(Point const &p) { | |
| 324 | 4 | return p.length(); | |
| 325 | } | ||
| 326 | |||
| 327 | /** @brief Compute the square of the Euclidean norm of @a p. | ||
| 328 | * Warning: this can overflow where L2 won't. | ||
| 329 | * @return \f$p_X^2 + p_Y^2\f$ | ||
| 330 | * @relates Point */ | ||
| 331 | 1845 | constexpr Coord L2sq(Point const &p) { | |
| 332 | 1845 | return p.lengthSq(); | |
| 333 | } | ||
| 334 | |||
| 335 | /** @brief Returns p * Geom::rotate_degrees(90), but more efficient. | ||
| 336 | * | ||
| 337 | * Angle direction in 2Geom: If you use the traditional mathematics convention that y | ||
| 338 | * increases upwards, then positive angles are anticlockwise as per the mathematics convention. If | ||
| 339 | * you take the common non-mathematical convention that y increases downwards, then positive angles | ||
| 340 | * are clockwise, as is common outside of mathematics. | ||
| 341 | * | ||
| 342 | * There is no function to rotate by -90 degrees: use -rot90(p) instead. | ||
| 343 | * @relates Point */ | ||
| 344 | 36000 | constexpr Point rot90(Point const &p) { | |
| 345 | 36000 | return Point(-p[Y], p[X]); | |
| 346 | } | ||
| 347 | |||
| 348 | /** @brief Linear interpolation between two points. | ||
| 349 | * @param t Time value | ||
| 350 | * @param a First point | ||
| 351 | * @param b Second point | ||
| 352 | * @return Point on a line between a and b. The ratio of its distance from a | ||
| 353 | * and the distance between a and b will be equal to t. | ||
| 354 | * @relates Point */ | ||
| 355 | 142123 | inline Point lerp(Coord t, Point const &a, Point const &b) { | |
| 356 | 142123 | return (1 - t) * a + t * b; | |
| 357 | } | ||
| 358 | |||
| 359 | /** @brief Return a point halfway between the specified ones. | ||
| 360 | * @relates Point */ | ||
| 361 | 91867 | inline Point middle_point(Point const &p1, Point const &p2) { | |
| 362 | 91867 | return lerp(0.5, p1, p2); | |
| 363 | } | ||
| 364 | |||
| 365 | /** @brief Compute the dot product of a and b. | ||
| 366 | * Dot product can be interpreted as a measure of how parallel the vectors are. | ||
| 367 | * For perpendicular vectors, it is zero. For parallel ones, its absolute value is highest, | ||
| 368 | * and the sign depends on whether they point in the same direction (+) or opposite ones (-). | ||
| 369 | * @return \f$a \cdot b = a_X b_X + a_Y b_Y\f$. | ||
| 370 | * @relates Point */ | ||
| 371 | 55287253 | constexpr Coord dot(Point const &a, Point const &b) { | |
| 372 | 55287253 | return a[X] * b[X] + a[Y] * b[Y]; | |
| 373 | } | ||
| 374 | |||
| 375 | /** @brief Compute the 2D cross product. | ||
| 376 | * This is also known as "perp dot product". It will be zero for parallel vectors, | ||
| 377 | * and the absolute value will be highest for perpendicular vectors. | ||
| 378 | * @return \f$a \times b = a_X b_Y - a_Y b_X\f$. | ||
| 379 | * @relates Point*/ | ||
| 380 | 1074145 | constexpr Coord cross(Point const &a, Point const &b) | |
| 381 | { | ||
| 382 | // equivalent implementation: | ||
| 383 | // return dot(a, b.ccw()); | ||
| 384 | 1074145 | return a[X] * b[Y] - a[Y] * b[X]; | |
| 385 | } | ||
| 386 | |||
| 387 | /// Compute the (Euclidean) distance between points. | ||
| 388 | /// @relates Point | ||
| 389 | 10696124 | inline Coord distance(Point const &a, Point const &b) { | |
| 390 | 10696124 | return (a - b).length(); | |
| 391 | } | ||
| 392 | |||
| 393 | /// Compute the square of the distance between points. | ||
| 394 | /// @relates Point | ||
| 395 | 158 | inline Coord distanceSq(Point const &a, Point const &b) { | |
| 396 | 158 | return L2sq(a - b); | |
| 397 | } | ||
| 398 | |||
| 399 | //IMPL: NearConcept | ||
| 400 | /// Test whether two points are no further apart than some threshold. | ||
| 401 | /// @relates Point | ||
| 402 | ✗ | inline bool are_near(Point const &a, Point const &b, double eps = EPSILON) { | |
| 403 | // do not use an unqualified calls to distance before the empty | ||
| 404 | // specialization of iterator_traits is defined - see end of file | ||
| 405 | ✗ | return are_near((a - b).length(), 0, eps); | |
| 406 | } | ||
| 407 | |||
| 408 | /// Test whether the relative distance between two points is less than some threshold. | ||
| 409 | 30074 | inline bool are_near_rel(Point const &a, Point const &b, double eps = EPSILON) { | |
| 410 | 30074 | return (a - b).length() <= eps * (a.length() + b.length()) / 2; | |
| 411 | } | ||
| 412 | |||
| 413 | /// Test whether three points lie approximately on the same line. | ||
| 414 | /// @relates Point | ||
| 415 | ✗ | inline bool are_collinear(Point const &p1, Point const &p2, Point const &p3, | |
| 416 | double eps = EPSILON) | ||
| 417 | { | ||
| 418 | ✗ | return are_near(cross(p1, p2) + cross(p2, p3) + cross(p3, p1), 0, eps); | |
| 419 | } | ||
| 420 | |||
| 421 | Point unit_vector(Point const &a); | ||
| 422 | Coord L1(Point const &p); | ||
| 423 | Coord LInfty(Point const &p); | ||
| 424 | bool is_zero(Point const &p); | ||
| 425 | bool is_unit_vector(Point const &p, Coord eps = EPSILON); | ||
| 426 | double atan2(Point const &p); | ||
| 427 | double angle_between(Point const &a, Point const &b); | ||
| 428 | Point abs(Point const &b); | ||
| 429 | Point constrain_angle(Point const &A, Point const &B, unsigned n = 4, Point const &dir = {1, 0}); | ||
| 430 | |||
| 431 | } // namespace Geom | ||
| 432 | |||
| 433 | // This is required to fix a bug in GCC 4.3.3 (and probably others) that causes the compiler | ||
| 434 | // to try to instantiate the iterator_traits template and fail. Probably it thinks that Point | ||
| 435 | // is an iterator and tries to use std::distance instead of Geom::distance. | ||
| 436 | namespace std { | ||
| 437 | template <> class iterator_traits<Geom::Point> {}; | ||
| 438 | } | ||
| 439 | |||
| 440 | // Structured binding support | ||
| 441 | template <> struct std::tuple_size<Geom::Point> : std::integral_constant<size_t, 2> {}; | ||
| 442 | template <size_t I> struct std::tuple_element<I, Geom::Point> { using type = Geom::Coord; }; | ||
| 443 | |||
| 444 | // Hash support | ||
| 445 | template <> struct std::hash<Geom::Point> | ||
| 446 | { | ||
| 447 | size_t operator()(Geom::Point const &p) const noexcept { | ||
| 448 | size_t hash = 0; | ||
| 449 | boost::hash_combine(hash, p.x()); | ||
| 450 | boost::hash_combine(hash, p.y()); | ||
| 451 | return hash; | ||
| 452 | } | ||
| 453 | }; | ||
| 454 | |||
| 455 | #endif // LIB2GEOM_SEEN_POINT_H | ||
| 456 | |||
| 457 | /* | ||
| 458 | Local Variables: | ||
| 459 | mode:c++ | ||
| 460 | c-file-style:"stroustrup" | ||
| 461 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 462 | indent-tabs-mode:nil | ||
| 463 | fill-column:99 | ||
| 464 | End: | ||
| 465 | */ | ||
| 466 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 467 |