src/2geom/line.cpp

   1 /*
   2  * Infinite Straight Line
   3  *
   4  * Copyright 2008  Marco Cecchetti <mrcekets at gmail.com>
   5  * Nathan Hurst
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it either under the terms of the GNU Lesser General Public
   9  * License version 2.1 as published by the Free Software Foundation
  10  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12  * notice, a recipient may use your version of this file under either
  13  * the MPL or the LGPL.
  14  *
  15  * You should have received a copy of the LGPL along with this library
  16  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  18  * You should have received a copy of the MPL along with this library
  19  * in the file COPYING-MPL-1.1
  20  *
  21  * The contents of this file are subject to the Mozilla Public License
  22  * Version 1.1 (the "License"); you may not use this file except in
  23  * compliance with the License. You may obtain a copy of the License at
  24  * http://www.mozilla.org/MPL/
  25  *
  26  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28  * the specific language governing rights and limitations.
  29  */
  30
  31
  32 #include <2geom/line.h>
  33
  34 #include <algorithm>
  35
  36
  37 namespace Geom
  38 {
  39
  40 namespace detail
  41 {
  42
  43 inline
  44 OptCrossing intersection_impl(Point const& V1, Point const O1,
  45                         Point const& V2, Point const O2 )
  46 {
  47     double detV1V2 = V1[X] * V2[Y] - V2[X] * V1[Y];
  48     if (are_near(detV1V2, 0)) return OptCrossing();
  49
  50     Point B = O2 - O1;
  51     double detBV2 = B[X] * V2[Y] - V2[X] * B[Y];
  52     double detV1B =     B[X] * V1[Y] - V1[X] * B[Y];
  53     double inv_detV1V2 = 1 / detV1V2;
  54
  55     Crossing c;
  56     c.ta = detBV2 * inv_detV1V2;
  57     c.tb = detV1B * inv_detV1V2;
  58 //      std::cerr << "ta = " << solution.ta << std::endl;
  59 //      std::cerr << "tb = " << solution.tb << std::endl;
  60     return OptCrossing(c);
  61 }
  62
  63
  64 OptCrossing intersection_impl(Ray const& r1, Line const& l2, unsigned int i)
  65 {
  66     OptCrossing crossing =
  67         intersection_impl(r1.versor(), r1.origin(),
  68                           l2.versor(), l2.origin() );
  69
  70     if (crossing)
  71     {
  72         if (crossing->ta < 0)
  73         {
  74             return OptCrossing();
  75         }
  76         else
  77         {
  78             if (i != 0)
  79             {
  80                 std::swap(crossing->ta, crossing->tb);
  81             }
  82             return crossing;
  83         }
  84     }
  85     if (are_near(r1.origin(), l2))
  86     {
  87         THROW_INFINITESOLUTIONS();
  88     }
  89     else
  90     {
  91         return OptCrossing();
  92     }
  93 }
  94
  95
  96 OptCrossing intersection_impl( LineSegment const& ls1,
  97                                Line const& l2,
  98                                unsigned int i )
  99 {
 100     OptCrossing crossing =
 101         intersection_impl(ls1.finalPoint() - ls1.initialPoint(),
 102                           ls1.initialPoint(),
 103                           l2.versor(),
 104                           l2.origin() );
 105
 106     if (crossing)
 107     {
 108         if ( crossing->getTime(0) < 0
 109              || crossing->getTime(0) > 1 )
 110         {
 111             return OptCrossing();
 112         }
 113         else
 114         {
 115             if (i != 0)
 116             {
 117                 std::swap((*crossing).ta, (*crossing).tb);
 118             }
 119             return crossing;
 120         }
 121     }
 122     if (are_near(ls1.initialPoint(), l2))
 123     {
 124         THROW_INFINITESOLUTIONS();
 125     }
 126     else
 127     {
 128         return OptCrossing();
 129     }
 130 }
 131
 132
 133 OptCrossing intersection_impl( LineSegment const& ls1,
 134                                Ray const& r2,
 135                                unsigned int i )
 136 {
 137     Point direction = ls1.finalPoint() - ls1.initialPoint();
 138     OptCrossing crossing =
 139         intersection_impl( direction,
 140                            ls1.initialPoint(),
 141                            r2.versor(),
 142                            r2.origin() );
 143
 144     if (crossing)
 145     {
 146         if ( crossing->getTime(0) < 0
 147              || crossing->getTime(0) > 1
 148              || crossing->getTime(1) < 0 )
 149         {
 150             return OptCrossing();
 151         }
 152         else
 153         {
 154             if (i != 0)
 155             {
 156                 std::swap(crossing->ta, crossing->tb);
 157             }
 158             return crossing;
 159         }
 160     }
 161
 162     if ( are_near(r2.origin(), ls1) )
 163     {
 164         bool eqvs = (dot(direction, r2.versor()) > 0);
 165         if ( are_near(ls1.initialPoint(), r2.origin()) && !eqvs  )
 166         {
 167             crossing->ta = crossing->tb = 0;
 168             return crossing;
 169         }
 170         else if ( are_near(ls1.finalPoint(), r2.origin()) && eqvs )
 171         {
 172             if (i == 0)
 173             {
 174                 crossing->ta = 1;
 175                 crossing->tb = 0;
 176             }
 177             else
 178             {
 179                 crossing->ta = 0;
 180                 crossing->tb = 1;
 181             }
 182             return crossing;
 183         }
 184         else
 185         {
 186             THROW_INFINITESOLUTIONS();
 187         }
 188     }
 189     else if ( are_near(ls1.initialPoint(), r2) )
 190     {
 191         THROW_INFINITESOLUTIONS();
 192     }
 193     else
 194     {
 195         OptCrossing no_crossing;
 196         return no_crossing;
 197     }
 198 }
 199
 200 }  // end namespace detail
 201
 202
 203
 204 OptCrossing intersection(Line const& l1, Line const& l2)
 205 {
 206     OptCrossing crossing =
 207         detail::intersection_impl( l1.versor(), l1.origin(),
 208                                    l2.versor(), l2.origin() );
 209     if (crossing)
 210     {
 211         return crossing;
 212     }
 213     if (are_near(l1.origin(), l2))
 214     {
 215         THROW_INFINITESOLUTIONS();
 216     }
 217     else
 218     {
 219         return crossing;
 220     }
 221 }
 222
 223
 224 OptCrossing intersection(Ray const& r1, Ray const& r2)
 225 {
 226     OptCrossing crossing =
 227     detail::intersection_impl( r1.versor(), r1.origin(),
 228                                r2.versor(), r2.origin() );
 229
 230     if (crossing)
 231     {
 232         if ( crossing->ta < 0
 233              || crossing->tb < 0 )
 234         {
 235             OptCrossing no_crossing;
 236             return no_crossing;
 237         }
 238         else
 239         {
 240             return crossing;
 241         }
 242     }
 243
 244     if ( are_near(r1.origin(), r2) || are_near(r2.origin(), r1) )
 245     {
 246         if ( are_near(r1.origin(), r2.origin())
 247              && !are_near(r1.versor(), r2.versor()) )
 248         {
 249             crossing->ta = crossing->tb = 0;
 250             return crossing;
 251         }
 252         else
 253         {
 254             THROW_INFINITESOLUTIONS();
 255         }
 256     }
 257     else
 258     {
 259         OptCrossing no_crossing;
 260         return no_crossing;
 261     }
 262 }
 263
 264
 265 OptCrossing intersection( LineSegment const& ls1, LineSegment const& ls2 )
 266 {
 267     Point direction1 = ls1.finalPoint() - ls1.initialPoint();
 268     Point direction2 = ls2.finalPoint() - ls2.initialPoint();
 269     OptCrossing crossing =
 270         detail::intersection_impl( direction1,
 271                                    ls1.initialPoint(),
 272                                    direction2,
 273                                    ls2.initialPoint() );
 274
 275     if (crossing)
 276     {
 277         if ( crossing->getTime(0) < 0
 278              || crossing->getTime(0) > 1
 279              || crossing->getTime(1) < 0
 280              || crossing->getTime(1) > 1 )
 281         {
 282             OptCrossing no_crossing;
 283             return no_crossing;
 284         }
 285         else
 286         {
 287             return crossing;
 288         }
 289     }
 290
 291     bool eqvs = (dot(direction1, direction2) > 0);
 292     if ( are_near(ls2.initialPoint(), ls1) )
 293     {
 294         if ( are_near(ls1.initialPoint(), ls2.initialPoint()) && !eqvs )
 295         {
 296             crossing->ta = crossing->tb = 0;
 297             return crossing;
 298         }
 299         else if ( are_near(ls1.finalPoint(), ls2.initialPoint()) && eqvs )
 300         {
 301             crossing->ta = 1;
 302             crossing->tb = 0;
 303             return crossing;
 304         }
 305         else
 306         {
 307             THROW_INFINITESOLUTIONS();
 308         }
 309     }
 310     else if ( are_near(ls2.finalPoint(), ls1) )
 311     {
 312         if ( are_near(ls1.finalPoint(), ls2.finalPoint()) && !eqvs )
 313         {
 314             crossing->ta = crossing->tb = 1;
 315             return crossing;
 316         }
 317         else if ( are_near(ls1.initialPoint(), ls2.finalPoint()) && eqvs )
 318         {
 319             crossing->ta = 0;
 320             crossing->tb = 1;
 321             return crossing;
 322         }
 323         else
 324         {
 325             THROW_INFINITESOLUTIONS();
 326         }
 327     }
 328     else
 329     {
 330         OptCrossing no_crossing;
 331         return no_crossing;
 332     }
 333 }
 334
 335
 336
 337 Line make_angle_bisector_line(Line const& l1, Line const& l2)
 338 {
 339     OptCrossing crossing;
 340     try
 341     {
 342         crossing = intersection(l1, l2);
 343     }
 344     catch(InfiniteSolutions e)
 345     {
 346         return l1;
 347     }
 348     if (!crossing)
 349     {
 350         THROW_RANGEERROR("passed lines are parallel");
 351     }
 352     Point O = l1.pointAt(crossing->ta);
 353     Point A = l1.pointAt(crossing->ta + 1);
 354     double angle = angle_between(l1.versor(), l2.versor());
 355     Point B = (angle > 0) ? l2.pointAt(crossing->tb + 1)
 356         : l2.pointAt(crossing->tb - 1);
 357
 358     return make_angle_bisector_line(A, O, B);
 359 }
 360
 361
 362 }  // end namespace Geom
 363
 364
 365
 366 /*
 367   Local Variables:
 368   mode:c++
 369   c-file-style:"stroustrup"
 370   c-file-offsets:((innamespace . 0)(substatement-open . 0))
 371   indent-tabs-mode:nil
 372   c-brace-offset:0
 373   fill-column:99
 374   End:
 375   vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
 376 */