| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Cartesian point / 2D vector and related operations | ||
| 4 | *//* | ||
| 5 | * Authors: | ||
| 6 | * Michael G. Sloan <mgsloan@gmail.com> | ||
| 7 | * Nathan Hurst <njh@njhurst.com> | ||
| 8 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 9 | * | ||
| 10 | * Copyright (C) 2006-2009 Authors | ||
| 11 | * | ||
| 12 | * This library is free software; you can redistribute it and/or | ||
| 13 | * modify it either under the terms of the GNU Lesser General Public | ||
| 14 | * License version 2.1 as published by the Free Software Foundation | ||
| 15 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 16 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 17 | * notice, a recipient may use your version of this file under either | ||
| 18 | * the MPL or the LGPL. | ||
| 19 | * | ||
| 20 | * You should have received a copy of the LGPL along with this library | ||
| 21 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 22 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 23 | * You should have received a copy of the MPL along with this library | ||
| 24 | * in the file COPYING-MPL-1.1 | ||
| 25 | * | ||
| 26 | * The contents of this file are subject to the Mozilla Public License | ||
| 27 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 28 | * compliance with the License. You may obtain a copy of the License at | ||
| 29 | * http://www.mozilla.org/MPL/ | ||
| 30 | * | ||
| 31 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 32 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 33 | * the specific language governing rights and limitations. | ||
| 34 | */ | ||
| 35 | |||
| 36 | #include <assert.h> | ||
| 37 | #include <math.h> | ||
| 38 | #include <2geom/angle.h> | ||
| 39 | #include <2geom/coord.h> | ||
| 40 | #include <2geom/point.h> | ||
| 41 | #include <2geom/transforms.h> | ||
| 42 | |||
| 43 | namespace Geom { | ||
| 44 | |||
| 45 | /** | ||
| 46 | * @class Point | ||
| 47 | * @brief Two-dimensional point that doubles as a vector. | ||
| 48 | * | ||
| 49 | * Points in 2Geom are represented in Cartesian coordinates, e.g. as a pair of numbers | ||
| 50 | * that store the X and Y coordinates. Each point is also a vector in \f$\mathbb{R}^2\f$ | ||
| 51 | * from the origin (point at 0,0) to the stored coordinates, | ||
| 52 | * and has methods implementing several vector operations (like length()). | ||
| 53 | * | ||
| 54 | * @section OpNotePoint Operator note | ||
| 55 | * | ||
| 56 | * Most operators are provided by Boost operator helpers, so they are not visible in this class. | ||
| 57 | * If @a p, @a q, @a r denote points, @a s a floating-point scalar, and @a m a transformation matrix, | ||
| 58 | * then the following operations are available: | ||
| 59 | * @code | ||
| 60 | p += q; p -= q; r = p + q; r = p - q; | ||
| 61 | p *= s; p /= s; q = p * s; q = s * p; q = p / s; | ||
| 62 | p *= m; q = p * m; q = m * p; | ||
| 63 | @endcode | ||
| 64 | * It is possible to left-multiply a point by a matrix, even though mathematically speaking | ||
| 65 | * this is undefined. The result is a point identical to that obtained by right-multiplying. | ||
| 66 | * | ||
| 67 | * @ingroup Primitives */ | ||
| 68 | |||
| 69 | 722499 | Point Point::polar(Coord angle) { | |
| 70 | 722499 | Point ret; | |
| 71 |
1/2✓ Branch 2 taken 722499 times.
✗ Branch 3 not taken.
|
722499 | Coord remainder = Angle(angle).radians0(); |
| 72 |
6/6✓ Branch 1 taken 440803 times.
✓ Branch 2 taken 281696 times.
✓ Branch 4 taken 3 times.
✓ Branch 5 taken 440800 times.
✓ Branch 6 taken 281699 times.
✓ Branch 7 taken 440800 times.
|
722499 | if (are_near(remainder, 0) || are_near(remainder, 2*M_PI)) { |
| 73 | 281699 | ret[X] = 1; | |
| 74 | 281699 | ret[Y] = 0; | |
| 75 |
2/2✓ Branch 1 taken 10248 times.
✓ Branch 2 taken 430552 times.
|
440800 | } else if (are_near(remainder, M_PI/2)) { |
| 76 | 10248 | ret[X] = 0; | |
| 77 | 10248 | ret[Y] = 1; | |
| 78 |
2/2✓ Branch 1 taken 30391 times.
✓ Branch 2 taken 400161 times.
|
430552 | } else if (are_near(remainder, M_PI)) { |
| 79 | 30391 | ret[X] = -1; | |
| 80 | 30391 | ret[Y] = 0; | |
| 81 |
2/2✓ Branch 1 taken 9965 times.
✓ Branch 2 taken 390196 times.
|
400161 | } else if (are_near(remainder, 3*M_PI/2)) { |
| 82 | 9965 | ret[X] = 0; | |
| 83 | 9965 | ret[Y] = -1; | |
| 84 | } else { | ||
| 85 | 390196 | sincos(angle, ret[Y], ret[X]); | |
| 86 | } | ||
| 87 | 722499 | return ret; | |
| 88 | } | ||
| 89 | |||
| 90 | /** @brief Normalize the vector representing the point. | ||
| 91 | * After this method returns, the length of the vector will be 1 (unless both coordinates are | ||
| 92 | * zero - the zero point will be returned then). The function tries to handle infinite | ||
| 93 | * coordinates gracefully. If any of the coordinates are NaN, the function will do nothing. | ||
| 94 | * @post \f$-\epsilon < \left|this\right| - 1 < \epsilon\f$ | ||
| 95 | * @see unit_vector(Geom::Point const &) */ | ||
| 96 | 1555613 | void Point::normalize() { | |
| 97 | 1555613 | double len = hypot(_pt[0], _pt[1]); | |
| 98 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1555613 times.
|
1555613 | if(len == 0) return; |
| 99 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1555613 times.
|
1555613 | if(std::isnan(len)) return; |
| 100 | static double const inf = HUGE_VAL; | ||
| 101 |
1/2✓ Branch 0 taken 1555613 times.
✗ Branch 1 not taken.
|
1555613 | if(len != inf) { |
| 102 | 1555613 | *this /= len; | |
| 103 | } else { | ||
| 104 | ✗ | unsigned n_inf_coords = 0; | |
| 105 | /* Delay updating pt in case neither coord is infinite. */ | ||
| 106 | ✗ | Point tmp; | |
| 107 | ✗ | for ( unsigned i = 0 ; i < 2 ; ++i ) { | |
| 108 | ✗ | if ( _pt[i] == inf ) { | |
| 109 | ✗ | ++n_inf_coords; | |
| 110 | ✗ | tmp[i] = 1.0; | |
| 111 | ✗ | } else if ( _pt[i] == -inf ) { | |
| 112 | ✗ | ++n_inf_coords; | |
| 113 | ✗ | tmp[i] = -1.0; | |
| 114 | } else { | ||
| 115 | ✗ | tmp[i] = 0.0; | |
| 116 | } | ||
| 117 | } | ||
| 118 | ✗ | switch (n_inf_coords) { | |
| 119 | ✗ | case 0: { | |
| 120 | /* Can happen if both coords are near +/-DBL_MAX. */ | ||
| 121 | ✗ | *this /= 4.0; | |
| 122 | ✗ | len = hypot(_pt[0], _pt[1]); | |
| 123 | ✗ | assert(len != inf); | |
| 124 | ✗ | *this /= len; | |
| 125 | ✗ | break; | |
| 126 | } | ||
| 127 | ✗ | case 1: { | |
| 128 | ✗ | *this = tmp; | |
| 129 | ✗ | break; | |
| 130 | } | ||
| 131 | ✗ | case 2: { | |
| 132 | ✗ | *this = tmp * sqrt(0.5); | |
| 133 | ✗ | break; | |
| 134 | } | ||
| 135 | } | ||
| 136 | } | ||
| 137 | } | ||
| 138 | |||
| 139 | /** @brief Compute the first norm (Manhattan distance) of @a p. | ||
| 140 | * This is equal to the sum of absolutes values of the coordinates. | ||
| 141 | * @return \f$|p_X| + |p_Y|\f$ | ||
| 142 | * @relates Point */ | ||
| 143 | ✗ | Coord L1(Point const &p) { | |
| 144 | ✗ | Coord d = 0; | |
| 145 | ✗ | for ( int i = 0 ; i < 2 ; i++ ) { | |
| 146 | ✗ | d += fabs(p[i]); | |
| 147 | } | ||
| 148 | ✗ | return d; | |
| 149 | } | ||
| 150 | |||
| 151 | /** @brief Compute the infinity norm (maximum norm) of @a p. | ||
| 152 | * @return \f$\max(|p_X|, |p_Y|)\f$ | ||
| 153 | * @relates Point */ | ||
| 154 | ✗ | Coord LInfty(Point const &p) { | |
| 155 | ✗ | Coord const a(fabs(p[0])); | |
| 156 | ✗ | Coord const b(fabs(p[1])); | |
| 157 | ✗ | return ( a < b || std::isnan(b) | |
| 158 | ✗ | ? b | |
| 159 | ✗ | : a ); | |
| 160 | } | ||
| 161 | |||
| 162 | /** @brief True if the point has both coordinates zero. | ||
| 163 | * NaNs are treated as not equal to zero. | ||
| 164 | * @relates Point */ | ||
| 165 | 2700000 | bool is_zero(Point const &p) { | |
| 166 |
4/4✓ Branch 1 taken 1458000 times.
✓ Branch 2 taken 1242000 times.
✓ Branch 3 taken 252000 times.
✓ Branch 4 taken 1206000 times.
|
4158000 | return ( p[0] == 0 && |
| 167 | 4158000 | p[1] == 0 ); | |
| 168 | } | ||
| 169 | |||
| 170 | /** @brief True if the point has a length near 1. The are_near() function is used. | ||
| 171 | * @relates Point */ | ||
| 172 | ✗ | bool is_unit_vector(Point const &p, Coord eps) { | |
| 173 | ✗ | return are_near(L2(p), 1.0, eps); | |
| 174 | } | ||
| 175 | /** @brief Return the angle between the point and the +X axis. | ||
| 176 | * @return Angle in \f$(-\pi, \pi]\f$. | ||
| 177 | * @relates Point */ | ||
| 178 | 137569 | Coord atan2(Point const &p) { | |
| 179 | 137569 | return std::atan2(p[Y], p[X]); | |
| 180 | } | ||
| 181 | |||
| 182 | /** @brief Compute the angle between a and b relative to the origin. | ||
| 183 | * The computation is done by projecting b onto the basis defined by a, rot90(a). | ||
| 184 | * @return Angle in \f$(-\pi, \pi]\f$. | ||
| 185 | * @relates Point */ | ||
| 186 | 20766 | Coord angle_between(Point const &a, Point const &b) { | |
| 187 | 20766 | return std::atan2(cross(a,b), dot(a,b)); | |
| 188 | } | ||
| 189 | |||
| 190 | /** @brief Create a normalized version of a point. | ||
| 191 | * This is equivalent to copying the point and calling its normalize() method. | ||
| 192 | * The returned point will be (0,0) if the argument has both coordinates equal to zero. | ||
| 193 | * If any coordinate is NaN, this function will do nothing. | ||
| 194 | * @param a Input point | ||
| 195 | * @return Point on the unit circle in the same direction from origin as a, or the origin | ||
| 196 | * if a has both coordinates equal to zero | ||
| 197 | * @relates Point */ | ||
| 198 | 324000 | Point unit_vector(Point const &a) | |
| 199 | { | ||
| 200 | 324000 | Point ret(a); | |
| 201 |
1/2✓ Branch 1 taken 324000 times.
✗ Branch 2 not taken.
|
324000 | ret.normalize(); |
| 202 | 324000 | return ret; | |
| 203 | } | ||
| 204 | /** @brief Return the "absolute value" of the point's vector. | ||
| 205 | * This is defined in terms of the default lexicographical ordering. If the point is "larger" | ||
| 206 | * that the origin (0, 0), its negation is returned. You can check whether | ||
| 207 | * the points' vectors have the same direction (e.g. lie | ||
| 208 | * on the same line passing through the origin) using | ||
| 209 | * @code abs(a).normalize() == abs(b).normalize() @endcode | ||
| 210 | * To check with some margin of error, use | ||
| 211 | * @code are_near(abs(a).normalize(), abs(b).normalize()) @endcode | ||
| 212 | * Although naively this should take the absolute value of each coordinate, such an operation | ||
| 213 | * is not very useful. | ||
| 214 | * @relates Point */ | ||
| 215 | ✗ | Point abs(Point const &b) | |
| 216 | { | ||
| 217 | ✗ | Point ret; | |
| 218 | ✗ | if (b[Y] < 0.0) { | |
| 219 | ✗ | ret = -b; | |
| 220 | ✗ | } else if (b[Y] == 0.0) { | |
| 221 | ✗ | ret = b[X] < 0.0 ? -b : b; | |
| 222 | } else { | ||
| 223 | ✗ | ret = b; | |
| 224 | } | ||
| 225 | ✗ | return ret; | |
| 226 | } | ||
| 227 | |||
| 228 | /** @brief Transform the point by the specified matrix. */ | ||
| 229 | 3006396 | Point &Point::operator*=(Affine const &m) { | |
| 230 | 3006396 | double x = _pt[X], y = _pt[Y]; | |
| 231 |
2/2✓ Branch 0 taken 6012792 times.
✓ Branch 1 taken 3006396 times.
|
9019188 | for(int i = 0; i < 2; i++) { |
| 232 | 6012792 | _pt[i] = x * m[i] + y * m[i + 2] + m[i + 4]; | |
| 233 | } | ||
| 234 | 3006396 | return *this; | |
| 235 | } | ||
| 236 | |||
| 237 | /** @brief Snap the angle B - A - dir to multiples of \f$2\pi/n\f$. | ||
| 238 | * The 'dir' argument must be normalized (have unit length), otherwise the result | ||
| 239 | * is undefined. | ||
| 240 | * @return Point with the same distance from A as B, with a snapped angle. | ||
| 241 | * @post distance(A, B) == distance(A, result) | ||
| 242 | * @post angle_between(result - A, dir) == \f$2k\pi/n, k \in \mathbb{N}\f$ | ||
| 243 | * @relates Point */ | ||
| 244 | ✗ | Point constrain_angle(Point const &A, Point const &B, unsigned int n, Point const &dir) | |
| 245 | { | ||
| 246 | // for special cases we could perhaps use explicit testing (which might be faster) | ||
| 247 | ✗ | if (n == 0.0) { | |
| 248 | ✗ | return B; | |
| 249 | } | ||
| 250 | ✗ | Point diff(B - A); | |
| 251 | ✗ | double angle = -angle_between(diff, dir); | |
| 252 | ✗ | double k = round(angle * (double)n / (2.0*M_PI)); | |
| 253 | ✗ | return A + dir * Rotate(k * 2.0 * M_PI / (double)n) * L2(diff); | |
| 254 | } | ||
| 255 | |||
| 256 | 100 | std::ostream &operator<<(std::ostream &out, Geom::Point const &p) | |
| 257 | { | ||
| 258 |
1/2✓ Branch 2 taken 100 times.
✗ Branch 3 not taken.
|
200 | return out << "(" << format_coord_nice(p[X]) << ", " |
| 259 |
5/10✓ Branch 3 taken 100 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 100 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 100 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 100 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 100 times.
✗ Branch 18 not taken.
|
300 | << format_coord_nice(p[Y]) << ")"; |
| 260 | } | ||
| 261 | |||
| 262 | } // namespace Geom | ||
| 263 | |||
| 264 | /* | ||
| 265 | Local Variables: | ||
| 266 | mode:c++ | ||
| 267 | c-file-style:"stroustrup" | ||
| 268 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 269 | indent-tabs-mode:nil | ||
| 270 | fill-column:99 | ||
| 271 | End: | ||
| 272 | */ | ||
| 273 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 274 |