| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Infinite straight line | ||
| 4 | *//* | ||
| 5 | * Authors: | ||
| 6 | * Marco Cecchetti <mrcekets at gmail.com> | ||
| 7 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 8 | * Copyright 2008-2011 Authors | ||
| 9 | * | ||
| 10 | * This library is free software; you can redistribute it and/or | ||
| 11 | * modify it either under the terms of the GNU Lesser General Public | ||
| 12 | * License version 2.1 as published by the Free Software Foundation | ||
| 13 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 14 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 15 | * notice, a recipient may use your version of this file under either | ||
| 16 | * the MPL or the LGPL. | ||
| 17 | * | ||
| 18 | * You should have received a copy of the LGPL along with this library | ||
| 19 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 20 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 21 | * You should have received a copy of the MPL along with this library | ||
| 22 | * in the file COPYING-MPL-1.1 | ||
| 23 | * | ||
| 24 | * The contents of this file are subject to the Mozilla Public License | ||
| 25 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 26 | * compliance with the License. You may obtain a copy of the License at | ||
| 27 | * http://www.mozilla.org/MPL/ | ||
| 28 | * | ||
| 29 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 30 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 31 | * the specific language governing rights and limitations. | ||
| 32 | */ | ||
| 33 | |||
| 34 | #ifndef LIB2GEOM_SEEN_LINE_H | ||
| 35 | #define LIB2GEOM_SEEN_LINE_H | ||
| 36 | |||
| 37 | #include <cmath> | ||
| 38 | #include <optional> | ||
| 39 | #include <2geom/bezier-curve.h> // for LineSegment | ||
| 40 | #include <2geom/rect.h> | ||
| 41 | #include <2geom/crossing.h> | ||
| 42 | #include <2geom/exception.h> | ||
| 43 | #include <2geom/ray.h> | ||
| 44 | #include <2geom/angle.h> | ||
| 45 | #include <2geom/intersection.h> | ||
| 46 | |||
| 47 | namespace Geom | ||
| 48 | { | ||
| 49 | |||
| 50 | // class docs in cpp file | ||
| 51 | class Line | ||
| 52 | : boost::equality_comparable< Line > | ||
| 53 | { | ||
| 54 | private: | ||
| 55 | Point _initial; | ||
| 56 | Point _final; | ||
| 57 | public: | ||
| 58 | /// @name Creating lines. | ||
| 59 | /// @{ | ||
| 60 | /** @brief Create a default horizontal line. | ||
| 61 | * Creates a line with unit speed going in +X direction. */ | ||
| 62 | 773 | Line() | |
| 63 | 773 | : _initial(0,0), _final(1,0) | |
| 64 | 773 | {} | |
| 65 | /** @brief Create a line with the specified inclination. | ||
| 66 | * @param origin One of the points on the line | ||
| 67 | * @param angle Angle of the line in mathematical convention */ | ||
| 68 | ✗ | Line(Point const &origin, Coord angle) | |
| 69 | ✗ | : _initial(origin) | |
| 70 | { | ||
| 71 | ✗ | Point v; | |
| 72 | ✗ | sincos(angle, v[Y], v[X]); | |
| 73 | ✗ | _final = _initial + v; | |
| 74 | ✗ | } | |
| 75 | |||
| 76 | /** @brief Create a line going through two points. | ||
| 77 | * The first point will be at time 0, while the second one | ||
| 78 | * will be at time 1. | ||
| 79 | * @param a Initial point | ||
| 80 | * @param b First point */ | ||
| 81 | 20805 | Line(Point const &a, Point const &b) | |
| 82 | 20805 | : _initial(a) | |
| 83 | 20805 | , _final(b) | |
| 84 | 20805 | {} | |
| 85 | |||
| 86 | /** @brief Create a line based on the coefficients of its equation. | ||
| 87 | @see Line::setCoefficients() */ | ||
| 88 | ✗ | Line(double a, double b, double c) { | |
| 89 | ✗ | setCoefficients(a, b, c); | |
| 90 | ✗ | } | |
| 91 | |||
| 92 | /// Create a line by extending a line segment. | ||
| 93 | 50014 | explicit Line(LineSegment const &seg) | |
| 94 | 50014 | : _initial(seg.initialPoint()) | |
| 95 | 50014 | , _final(seg.finalPoint()) | |
| 96 | 50014 | {} | |
| 97 | |||
| 98 | /// Create a line by extending a ray. | ||
| 99 | ✗ | explicit Line(Ray const &r) | |
| 100 | ✗ | : _initial(r.origin()) | |
| 101 | ✗ | , _final(r.origin() + r.vector()) | |
| 102 | ✗ | {} | |
| 103 | |||
| 104 | /// Create a line normal to a vector at a specified distance from origin. | ||
| 105 | static Line from_normal_distance(Point const &n, Coord c) { | ||
| 106 | Point start = c * n.normalized(); | ||
| 107 | Line l(start, start + rot90(n)); | ||
| 108 | return l; | ||
| 109 | } | ||
| 110 | /** @brief Create a line from origin and unit vector. | ||
| 111 | * Note that each line direction has two possible unit vectors. | ||
| 112 | * @param o Point through which the line will pass | ||
| 113 | * @param v Unit vector of the line's direction */ | ||
| 114 | ✗ | static Line from_origin_and_vector(Point const &o, Point const &v) { | |
| 115 | ✗ | Line l(o, o + v); | |
| 116 | ✗ | return l; | |
| 117 | } | ||
| 118 | |||
| 119 | Line* duplicate() const { | ||
| 120 | return new Line(*this); | ||
| 121 | } | ||
| 122 | /// @} | ||
| 123 | |||
| 124 | /// @name Retrieve and set the line's parameters. | ||
| 125 | /// @{ | ||
| 126 | |||
| 127 | /// Get the line's origin point. | ||
| 128 | ✗ | Point origin() const { return _initial; } | |
| 129 | /** @brief Get the line's raw direction vector. | ||
| 130 | * The length of the retrieved vector is equal to the length of a segment parametrized by | ||
| 131 | * a time interval of length 1. */ | ||
| 132 | 147025 | Point vector() const { return _final - _initial; } | |
| 133 | /** @brief Get the line's normalized direction vector. | ||
| 134 | * The retrieved vector is normalized to unit length. */ | ||
| 135 | ✗ | Point versor() const { return (_final - _initial).normalized(); } | |
| 136 | /// Angle the line makes with the X axis, in mathematical convention. | ||
| 137 | ✗ | Coord angle() const { | |
| 138 | ✗ | Point d = _final - _initial; | |
| 139 | ✗ | double a = std::atan2(d[Y], d[X]); | |
| 140 | ✗ | if (a < 0) a += M_PI; | |
| 141 | ✗ | if (a == M_PI) a = 0; | |
| 142 | ✗ | return a; | |
| 143 | } | ||
| 144 | |||
| 145 | /** @brief Set the point at zero time. | ||
| 146 | * The orientation remains unchanged, modulo numeric errors during addition. */ | ||
| 147 | void setOrigin(Point const &p) { | ||
| 148 | Point d = p - _initial; | ||
| 149 | _initial = p; | ||
| 150 | _final += d; | ||
| 151 | } | ||
| 152 | /** @brief Set the speed of the line. | ||
| 153 | * Origin remains unchanged. */ | ||
| 154 | void setVector(Point const &v) { | ||
| 155 | _final = _initial + v; | ||
| 156 | } | ||
| 157 | |||
| 158 | /** @brief Set the angle the line makes with the X axis. | ||
| 159 | * Origin remains unchanged. */ | ||
| 160 | void setAngle(Coord angle) { | ||
| 161 | Point v; | ||
| 162 | sincos(angle, v[Y], v[X]); | ||
| 163 | v *= distance(_initial, _final); | ||
| 164 | _final = _initial + v; | ||
| 165 | } | ||
| 166 | |||
| 167 | /// Set a line based on two points it should pass through. | ||
| 168 | ✗ | void setPoints(Point const &a, Point const &b) { | |
| 169 | ✗ | _initial = a; | |
| 170 | ✗ | _final = b; | |
| 171 | ✗ | } | |
| 172 | |||
| 173 | /** @brief Set the coefficients of the line equation. | ||
| 174 | * The line equation is: \f$ax + by = c\f$. Points that satisfy the equation | ||
| 175 | * are on the line. */ | ||
| 176 | void setCoefficients(double a, double b, double c); | ||
| 177 | |||
| 178 | /** @brief Get the coefficients of the line equation as a vector. | ||
| 179 | * @return STL vector @a v such that @a v[0] contains \f$a\f$, @a v[1] contains \f$b\f$, | ||
| 180 | * and @a v[2] contains \f$c\f$. */ | ||
| 181 | std::vector<double> coefficients() const; | ||
| 182 | |||
| 183 | /// Get the coefficients of the line equation by reference. | ||
| 184 | void coefficients(Coord &a, Coord &b, Coord &c) const; | ||
| 185 | |||
| 186 | /** @brief Check if the line has more than one point. | ||
| 187 | * A degenerate line can be created if the line is created from a line equation | ||
| 188 | * that has no solutions. | ||
| 189 | * @return True if the line has no points or exactly one point */ | ||
| 190 | 40079 | bool isDegenerate() const { | |
| 191 | 40079 | return _initial == _final; | |
| 192 | } | ||
| 193 | /// Check if the line is horizontal (y is constant). | ||
| 194 | bool isHorizontal() const { | ||
| 195 | return _initial[Y] == _final[Y]; | ||
| 196 | } | ||
| 197 | /// Check if the line is vertical (x is constant). | ||
| 198 | bool isVertical() const { | ||
| 199 | return _initial[X] == _final[X]; | ||
| 200 | } | ||
| 201 | |||
| 202 | /** @brief Reparametrize the line so that it has unit speed. | ||
| 203 | * Note that the direction of the line may also change. */ | ||
| 204 | 773 | void normalize() { | |
| 205 | // this helps with the nasty case of a line that starts somewhere far | ||
| 206 | // and ends very close to the origin | ||
| 207 |
2/2✓ Branch 2 taken 276 times.
✓ Branch 3 taken 497 times.
|
773 | if (L2sq(_final) < L2sq(_initial)) { |
| 208 | 276 | std::swap(_initial, _final); | |
| 209 | } | ||
| 210 | 773 | Point v = _final - _initial; | |
| 211 |
1/2✓ Branch 1 taken 773 times.
✗ Branch 2 not taken.
|
773 | v.normalize(); |
| 212 | 773 | _final = _initial + v; | |
| 213 | 773 | } | |
| 214 | /** @brief Return a new line reparametrized for unit speed. */ | ||
| 215 | Line normalized() const { | ||
| 216 | Point v = _final - _initial; | ||
| 217 | v.normalize(); | ||
| 218 | Line ret(_initial, _initial + v); | ||
| 219 | return ret; | ||
| 220 | } | ||
| 221 | /// @} | ||
| 222 | |||
| 223 | /// @name Evaluate the line as a function. | ||
| 224 | ///@{ | ||
| 225 | 60040 | Point initialPoint() const { | |
| 226 | 60040 | return _initial; | |
| 227 | } | ||
| 228 | 20030 | Point finalPoint() const { | |
| 229 | 20030 | return _final; | |
| 230 | } | ||
| 231 | 20035 | Point pointAt(Coord t) const { | |
| 232 | 20035 | return lerp(t, _initial, _final);; | |
| 233 | } | ||
| 234 | |||
| 235 | ✗ | Coord valueAt(Coord t, Dim2 d) const { | |
| 236 | ✗ | return lerp(t, _initial[d], _final[d]); | |
| 237 | } | ||
| 238 | |||
| 239 | Coord timeAt(Point const &p) const; | ||
| 240 | |||
| 241 | /** @brief Get a time value corresponding to a projection of a point on the line. | ||
| 242 | * @param p Arbitrary point. | ||
| 243 | * @return Time value corresponding to a point closest to @c p. */ | ||
| 244 | ✗ | Coord timeAtProjection(Point const& p) const { | |
| 245 | ✗ | if ( isDegenerate() ) return 0; | |
| 246 | ✗ | Point v = vector(); | |
| 247 | ✗ | return dot(p - _initial, v) / dot(v, v); | |
| 248 | } | ||
| 249 | |||
| 250 | /** @brief Find a point on the line closest to the query point. | ||
| 251 | * This is an alias for timeAtProjection(). */ | ||
| 252 | ✗ | Coord nearestTime(Point const &p) const { | |
| 253 | ✗ | return timeAtProjection(p); | |
| 254 | } | ||
| 255 | |||
| 256 | std::vector<Coord> roots(Coord v, Dim2 d) const; | ||
| 257 | Coord root(Coord v, Dim2 d) const; | ||
| 258 | /// @} | ||
| 259 | |||
| 260 | /// @name Create other objects based on this line. | ||
| 261 | /// @{ | ||
| 262 | ✗ | void reverse() { | |
| 263 | ✗ | std::swap(_final, _initial); | |
| 264 | ✗ | } | |
| 265 | /** @brief Create a line containing the same points, but in opposite direction. | ||
| 266 | * @return Line \f$g\f$ such that \f$g(t) = f(1-t)\f$ */ | ||
| 267 | Line reversed() const { | ||
| 268 | Line result(_final, _initial); | ||
| 269 | return result; | ||
| 270 | } | ||
| 271 | |||
| 272 | /** @brief Same as segment(), but allocate the line segment dynamically. */ | ||
| 273 | // TODO remove this? | ||
| 274 | Curve* portion(Coord f, Coord t) const { | ||
| 275 | LineSegment* seg = new LineSegment(pointAt(f), pointAt(t)); | ||
| 276 | return seg; | ||
| 277 | } | ||
| 278 | |||
| 279 | /** @brief Create a segment of this line. | ||
| 280 | * @param f Time value for the initial point of the segment | ||
| 281 | * @param t Time value for the final point of the segment | ||
| 282 | * @return Created line segment */ | ||
| 283 | ✗ | LineSegment segment(Coord f, Coord t) const { | |
| 284 | ✗ | return LineSegment(pointAt(f), pointAt(t)); | |
| 285 | } | ||
| 286 | |||
| 287 | /// Return the portion of the line that is inside the given rectangle | ||
| 288 | std::optional<LineSegment> clip(Rect const &r) const; | ||
| 289 | |||
| 290 | /** @brief Create a ray starting at the specified time value. | ||
| 291 | * The created ray will go in the direction of the line's vector (in the direction | ||
| 292 | * of increasing time values). | ||
| 293 | * @param t Time value where the ray should start | ||
| 294 | * @return Ray starting at t and going in the direction of the vector */ | ||
| 295 | Ray ray(Coord t) { | ||
| 296 | Ray result; | ||
| 297 | result.setOrigin(pointAt(t)); | ||
| 298 | result.setVector(vector()); | ||
| 299 | return result; | ||
| 300 | } | ||
| 301 | |||
| 302 | /** @brief Create a derivative of the line. | ||
| 303 | * The new line will always be degenerate. Its origin will be equal to this | ||
| 304 | * line's vector. */ | ||
| 305 | ✗ | Line derivative() const { | |
| 306 | ✗ | Point v = vector(); | |
| 307 | ✗ | Line result(v, v); | |
| 308 | ✗ | return result; | |
| 309 | } | ||
| 310 | |||
| 311 | /// Create a line transformed by an affine transformation. | ||
| 312 | ✗ | Line transformed(Affine const& m) const { | |
| 313 | ✗ | Line l(_initial * m, _final * m); | |
| 314 | ✗ | return l; | |
| 315 | } | ||
| 316 | |||
| 317 | /** @brief Get a unit vector normal to the line. | ||
| 318 | * If Y grows upwards, then this is the left normal. If Y grows downwards, | ||
| 319 | * then this is the right normal. */ | ||
| 320 | ✗ | Point normal() const { | |
| 321 | ✗ | return rot90(vector()).normalized(); | |
| 322 | } | ||
| 323 | |||
| 324 | // what does this do? | ||
| 325 | ✗ | Point normalAndDist(double & dist) const { | |
| 326 | ✗ | Point n = normal(); | |
| 327 | ✗ | dist = -dot(n, _initial); | |
| 328 | ✗ | return n; | |
| 329 | } | ||
| 330 | |||
| 331 | /// Compute an affine matrix representing a reflection about the line. | ||
| 332 | Affine reflection() const { | ||
| 333 | Point v = versor(); | ||
| 334 | Coord x2 = v[X]*v[X], y2 = v[Y]*v[Y], xy = v[X]*v[Y]; | ||
| 335 | Affine m(x2-y2, 2.*xy, | ||
| 336 | 2.*xy, y2-x2, | ||
| 337 | _initial[X], _initial[Y]); | ||
| 338 | m = Translate(-_initial) * m; | ||
| 339 | return m; | ||
| 340 | } | ||
| 341 | |||
| 342 | /** @brief Compute an affine which transforms all points on the line to zero X or Y coordinate. | ||
| 343 | * This operation is useful in reducing intersection problems to root-finding problems. | ||
| 344 | * There are many affines which do this transformation. This function returns one that | ||
| 345 | * preserves angles, areas and distances - a rotation combined with a translation, and | ||
| 346 | * additionally moves the initial point of the line to (0,0). This way it works without | ||
| 347 | * problems even for lines perpendicular to the target, though may in some cases have | ||
| 348 | * lower precision than e.g. a shear transform. | ||
| 349 | * @param d Which coordinate of points on the line should be zero after the transformation */ | ||
| 350 | 20024 | Affine rotationToZero(Dim2 d) const { | |
| 351 |
1/2✓ Branch 2 taken 20024 times.
✗ Branch 3 not taken.
|
20024 | Point v = vector(); |
| 352 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 20024 times.
|
20024 | if (d == X) { |
| 353 | ✗ | std::swap(v[X], v[Y]); | |
| 354 | } else { | ||
| 355 | 20024 | v[Y] = -v[Y]; | |
| 356 | } | ||
| 357 |
2/4✓ Branch 2 taken 20024 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 20024 times.
✗ Branch 10 not taken.
|
20024 | Affine m = Translate(-_initial) * Rotate(v); |
| 358 | 40048 | return m; | |
| 359 | } | ||
| 360 | /** @brief Compute a rotation affine which transforms the line to one of the axes. | ||
| 361 | * @param d Which line should be the axis */ | ||
| 362 | Affine rotationToAxis(Dim2 d) const { | ||
| 363 | Affine m = rotationToZero(other_dimension(d)); | ||
| 364 | return m; | ||
| 365 | } | ||
| 366 | |||
| 367 | Affine transformTo(Line const &other) const; | ||
| 368 | /// @} | ||
| 369 | |||
| 370 | std::vector<ShapeIntersection> intersect(Line const &other) const; | ||
| 371 | std::vector<ShapeIntersection> intersect(Ray const &r) const; | ||
| 372 | std::vector<ShapeIntersection> intersect(LineSegment const &ls) const; | ||
| 373 | |||
| 374 | template <typename T> | ||
| 375 | Line &operator*=(T const &tr) { | ||
| 376 | BOOST_CONCEPT_ASSERT((TransformConcept<T>)); | ||
| 377 | _initial *= tr; | ||
| 378 | _final *= tr; | ||
| 379 | return *this; | ||
| 380 | } | ||
| 381 | |||
| 382 | bool operator==(Line const &other) const { | ||
| 383 | if (distance(pointAt(nearestTime(other._initial)), other._initial) != 0) return false; | ||
| 384 | if (distance(pointAt(nearestTime(other._final)), other._final) != 0) return false; | ||
| 385 | return true; | ||
| 386 | } | ||
| 387 | |||
| 388 | template <typename T> | ||
| 389 | friend Line operator*(Line const &l, T const &tr) { | ||
| 390 | BOOST_CONCEPT_ASSERT((TransformConcept<T>)); | ||
| 391 | Line result(l); | ||
| 392 | result *= tr; | ||
| 393 | return result; | ||
| 394 | } | ||
| 395 | }; // end class Line | ||
| 396 | |||
| 397 | /** @brief Removes intersections outside of the unit interval. | ||
| 398 | * A helper used to implement line segment intersections. | ||
| 399 | * @param xs Line intersections | ||
| 400 | * @param a Whether the first time value has to be in the unit interval | ||
| 401 | * @param b Whether the second time value has to be in the unit interval | ||
| 402 | * @return Appropriately filtered intersections */ | ||
| 403 | void filter_line_segment_intersections(std::vector<ShapeIntersection> &xs, bool a=false, bool b=true); | ||
| 404 | void filter_ray_intersections(std::vector<ShapeIntersection> &xs, bool a=false, bool b=true); | ||
| 405 | |||
| 406 | /// @brief Compute distance from point to line. | ||
| 407 | /// @relates Line | ||
| 408 | inline | ||
| 409 | ✗ | double distance(Point const &p, Line const &line) | |
| 410 | { | ||
| 411 | ✗ | if (line.isDegenerate()) { | |
| 412 | ✗ | return ::Geom::distance(p, line.initialPoint()); | |
| 413 | } else { | ||
| 414 | ✗ | Coord t = line.nearestTime(p); | |
| 415 | ✗ | return ::Geom::distance(line.pointAt(t), p); | |
| 416 | } | ||
| 417 | } | ||
| 418 | |||
| 419 | inline | ||
| 420 | ✗ | bool are_near(Point const &p, Line const &line, double eps = EPSILON) | |
| 421 | { | ||
| 422 | ✗ | return are_near(distance(p, line), 0, eps); | |
| 423 | } | ||
| 424 | |||
| 425 | inline | ||
| 426 | bool are_parallel(Line const &l1, Line const &l2, double eps = EPSILON) | ||
| 427 | { | ||
| 428 | return are_near(cross(l1.vector(), l2.vector()), 0, eps); | ||
| 429 | } | ||
| 430 | |||
| 431 | /** @brief Test whether two lines are approximately the same. | ||
| 432 | * This tests for being parallel and the origin of one line being close to the other, | ||
| 433 | * so it tests whether the images of the lines are similar, not whether the same time values | ||
| 434 | * correspond to similar points. For example a line from (1,1) to (2,2) and a line from | ||
| 435 | * (-1,-1) to (0,0) will be the same, because their images match, even though there is | ||
| 436 | * no time value for which the lines give similar points. | ||
| 437 | * @relates Line */ | ||
| 438 | inline | ||
| 439 | bool are_same(Line const &l1, Line const &l2, double eps = EPSILON) | ||
| 440 | { | ||
| 441 | return are_parallel(l1, l2, eps) && are_near(l1.origin(), l2, eps); | ||
| 442 | } | ||
| 443 | |||
| 444 | /// Test whether two lines are perpendicular. | ||
| 445 | /// @relates Line | ||
| 446 | inline | ||
| 447 | bool are_orthogonal(Line const &l1, Line const &l2, double eps = EPSILON) | ||
| 448 | { | ||
| 449 | return are_near(dot(l1.vector(), l2.vector()), 0, eps); | ||
| 450 | } | ||
| 451 | |||
| 452 | // evaluate the angle between l1 and l2 rotating l1 in cw direction | ||
| 453 | // until it overlaps l2 | ||
| 454 | // the returned value is an angle in the interval [0, PI[ | ||
| 455 | inline | ||
| 456 | double angle_between(Line const& l1, Line const& l2) | ||
| 457 | { | ||
| 458 | double angle = angle_between(l1.vector(), l2.vector()); | ||
| 459 | if (angle < 0) angle += M_PI; | ||
| 460 | if (angle == M_PI) angle = 0; | ||
| 461 | return angle; | ||
| 462 | } | ||
| 463 | |||
| 464 | inline | ||
| 465 | ✗ | double distance(Point const &p, LineSegment const &seg) | |
| 466 | { | ||
| 467 | ✗ | double t = seg.nearestTime(p); | |
| 468 | ✗ | return distance(p, seg.pointAt(t)); | |
| 469 | } | ||
| 470 | |||
| 471 | inline | ||
| 472 | ✗ | bool are_near(Point const &p, LineSegment const &seg, double eps = EPSILON) | |
| 473 | { | ||
| 474 | ✗ | return are_near(distance(p, seg), 0, eps); | |
| 475 | } | ||
| 476 | |||
| 477 | // build a line passing by _point and orthogonal to _line | ||
| 478 | inline | ||
| 479 | ✗ | Line make_orthogonal_line(Point const &p, Line const &line) | |
| 480 | { | ||
| 481 | ✗ | Point d = line.vector().cw(); | |
| 482 | ✗ | Line l(p, p + d); | |
| 483 | ✗ | return l; | |
| 484 | } | ||
| 485 | |||
| 486 | // build a line passing by _point and parallel to _line | ||
| 487 | inline | ||
| 488 | Line make_parallel_line(Point const &p, Line const &line) | ||
| 489 | { | ||
| 490 | Line result(line); | ||
| 491 | result.setOrigin(p); | ||
| 492 | return result; | ||
| 493 | } | ||
| 494 | |||
| 495 | // build a line passing by the middle point of _segment and orthogonal to it. | ||
| 496 | inline | ||
| 497 | ✗ | Line make_bisector_line(LineSegment const& _segment) | |
| 498 | { | ||
| 499 | ✗ | return make_orthogonal_line( middle_point(_segment), Line(_segment) ); | |
| 500 | } | ||
| 501 | |||
| 502 | // build the bisector line of the angle between ray(O,A) and ray(O,B) | ||
| 503 | inline | ||
| 504 | ✗ | Line make_angle_bisector_line(Point const &A, Point const &O, Point const &B) | |
| 505 | { | ||
| 506 | ✗ | AngleInterval ival(Angle(A-O), Angle(B-O)); | |
| 507 | ✗ | Angle bisect = ival.angleAt(0.5); | |
| 508 | ✗ | return Line(O, bisect); | |
| 509 | } | ||
| 510 | |||
| 511 | // prj(P) = rot(v, Point( rot(-v, P-O)[X], 0 )) + O | ||
| 512 | inline | ||
| 513 | Point projection(Point const &p, Line const &line) | ||
| 514 | { | ||
| 515 | return line.pointAt(line.nearestTime(p)); | ||
| 516 | } | ||
| 517 | |||
| 518 | inline | ||
| 519 | LineSegment projection(LineSegment const &seg, Line const &line) | ||
| 520 | { | ||
| 521 | return line.segment(line.nearestTime(seg.initialPoint()), | ||
| 522 | line.nearestTime(seg.finalPoint())); | ||
| 523 | } | ||
| 524 | |||
| 525 | inline | ||
| 526 | ✗ | std::optional<LineSegment> clip(Line const &l, Rect const &r) { | |
| 527 | ✗ | return l.clip(r); | |
| 528 | } | ||
| 529 | |||
| 530 | |||
| 531 | namespace detail | ||
| 532 | { | ||
| 533 | |||
| 534 | OptCrossing intersection_impl(Ray const& r1, Line const& l2, unsigned int i); | ||
| 535 | OptCrossing intersection_impl( LineSegment const& ls1, | ||
| 536 | Line const& l2, | ||
| 537 | unsigned int i ); | ||
| 538 | OptCrossing intersection_impl( LineSegment const& ls1, | ||
| 539 | Ray const& r2, | ||
| 540 | unsigned int i ); | ||
| 541 | } | ||
| 542 | |||
| 543 | |||
| 544 | inline | ||
| 545 | ✗ | OptCrossing intersection(Ray const& r1, Line const& l2) | |
| 546 | { | ||
| 547 | ✗ | return detail::intersection_impl(r1, l2, 0); | |
| 548 | |||
| 549 | } | ||
| 550 | |||
| 551 | inline | ||
| 552 | ✗ | OptCrossing intersection(Line const& l1, Ray const& r2) | |
| 553 | { | ||
| 554 | ✗ | return detail::intersection_impl(r2, l1, 1); | |
| 555 | } | ||
| 556 | |||
| 557 | inline | ||
| 558 | OptCrossing intersection(LineSegment const& ls1, Line const& l2) | ||
| 559 | { | ||
| 560 | return detail::intersection_impl(ls1, l2, 0); | ||
| 561 | } | ||
| 562 | |||
| 563 | inline | ||
| 564 | OptCrossing intersection(Line const& l1, LineSegment const& ls2) | ||
| 565 | { | ||
| 566 | return detail::intersection_impl(ls2, l1, 1); | ||
| 567 | } | ||
| 568 | |||
| 569 | inline | ||
| 570 | OptCrossing intersection(LineSegment const& ls1, Ray const& r2) | ||
| 571 | { | ||
| 572 | return detail::intersection_impl(ls1, r2, 0); | ||
| 573 | |||
| 574 | } | ||
| 575 | |||
| 576 | inline | ||
| 577 | OptCrossing intersection(Ray const& r1, LineSegment const& ls2) | ||
| 578 | { | ||
| 579 | return detail::intersection_impl(ls2, r1, 1); | ||
| 580 | } | ||
| 581 | |||
| 582 | |||
| 583 | OptCrossing intersection(Line const& l1, Line const& l2); | ||
| 584 | |||
| 585 | OptCrossing intersection(Ray const& r1, Ray const& r2); | ||
| 586 | |||
| 587 | OptCrossing intersection(LineSegment const& ls1, LineSegment const& ls2); | ||
| 588 | |||
| 589 | |||
| 590 | } // end namespace Geom | ||
| 591 | |||
| 592 | |||
| 593 | #endif // LIB2GEOM_SEEN_LINE_H | ||
| 594 | |||
| 595 | |||
| 596 | /* | ||
| 597 | Local Variables: | ||
| 598 | mode:c++ | ||
| 599 | c-file-style:"stroustrup" | ||
| 600 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 601 | indent-tabs-mode:nil | ||
| 602 | fill-column:99 | ||
| 603 | End: | ||
| 604 | */ | ||
| 605 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 606 |