Home | History | Annotate | Download | only in Intersection 
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 #include "CurveIntersection.h"
      8 #include "LineUtilities.h"
      9 
     10 bool implicitLine(const _Line& line, double& slope, double& axisIntercept) {
     11     _Point delta;
     12     tangent(line, delta);
     13     bool moreHorizontal = fabs(delta.x) > fabs(delta.y);
     14     if (moreHorizontal) {
     15         slope = delta.y / delta.x;
     16         axisIntercept = line[0].y - slope * line[0].x;
     17     } else {
     18         slope = delta.x / delta.y;
     19         axisIntercept = line[0].x - slope * line[0].y;
     20     }
     21     return moreHorizontal;
     22 }
     23 
     24 int reduceOrder(const _Line& line, _Line& reduced) {
     25     reduced[0] = line[0];
     26     int different = line[0] != line[1];
     27     reduced[1] = line[different];
     28     return 1 + different;
     29 }
     30 
     31 void sub_divide(const _Line& line, double t1, double t2, _Line& dst) {
     32     _Point delta;
     33     tangent(line, delta);
     34     dst[0].x = line[0].x - t1 * delta.x;
     35     dst[0].y = line[0].y - t1 * delta.y;
     36     dst[1].x = line[0].x - t2 * delta.x;
     37     dst[1].y = line[0].y - t2 * delta.y;
     38 }
     39 
     40 // may have this below somewhere else already:
     41 // copying here because I thought it was clever
     42 
     43 // Copyright 2001, softSurfer (www.softsurfer.com)
     44 // This code may be freely used and modified for any purpose
     45 // providing that this copyright notice is included with it.
     46 // SoftSurfer makes no warranty for this code, and cannot be held
     47 // liable for any real or imagined damage resulting from its use.
     48 // Users of this code must verify correctness for their application.
     49 
     50 // Assume that a class is already given for the object:
     51 //    Point with coordinates {float x, y;}
     52 //===================================================================
     53 
     54 // isLeft(): tests if a point is Left|On|Right of an infinite line.
     55 //    Input:  three points P0, P1, and P2
     56 //    Return: >0 for P2 left of the line through P0 and P1
     57 //            =0 for P2 on the line
     58 //            <0 for P2 right of the line
     59 //    See: the January 2001 Algorithm on Area of Triangles
     60 //    return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
     61 double is_left(const _Line& line, const _Point& pt) {
     62     _Vector P0 = line[1] - line[0];
     63     _Vector P2 = pt - line[0];
     64     return P0.cross(P2);
     65 }
     66 
     67 double t_at(const _Line& line, const _Point& pt) {
     68     double dx = line[1].x - line[0].x;
     69     double dy = line[1].y - line[0].y;
     70     if (fabs(dx) > fabs(dy)) {
     71         if (approximately_zero(dx)) {
     72             return 0;
     73         }
     74         return (pt.x - line[0].x) / dx;
     75     }
     76     if (approximately_zero(dy)) {
     77         return 0;
     78     }
     79     return (pt.y - line[0].y) / dy;
     80 }
     81 
     82 static void setMinMax(double x, int flags, double& minX, double& maxX) {
     83     if (minX > x && (flags & (kFindTopMin | kFindBottomMin))) {
     84         minX = x;
     85     }
     86     if (maxX < x && (flags & (kFindTopMax | kFindBottomMax))) {
     87         maxX = x;
     88     }
     89 }
     90 
     91 void x_at(const _Point& p1, const _Point& p2, double top, double bottom,
     92         int flags, double& minX, double& maxX) {
     93     if (AlmostEqualUlps(p1.y, p2.y)) {
     94         // It should be OK to bail early in this case. There's another edge
     95         // which shares this end point which can intersect without failing to
     96         // have a slope ... maybe
     97         return;
     98     }
     99 
    100     // p2.x is always greater than p1.x -- the part of points (p1, p2) are
    101     // moving from the start of the cubic towards its end.
    102     // if p1.y < p2.y, minX can be affected
    103     // if p1.y > p2.y, maxX can be affected
    104     double slope = (p2.x - p1.x) / (p2.y - p1.y);
    105     int topFlags = flags & (kFindTopMin | kFindTopMax);
    106     if (topFlags && ((top <= p1.y && top >= p2.y)
    107             || (top >= p1.y && top <= p2.y))) {
    108         double x = p1.x + (top - p1.y) * slope;
    109         setMinMax(x, topFlags, minX, maxX);
    110     }
    111     int bottomFlags = flags & (kFindBottomMin | kFindBottomMax);
    112     if (bottomFlags && ((bottom <= p1.y && bottom >= p2.y)
    113             || (bottom >= p1.y && bottom <= p2.y))) {
    114         double x = p1.x + (bottom - p1.y) * slope;
    115         setMinMax(x, bottomFlags, minX, maxX);
    116     }
    117 }
    118 
    119 void xy_at_t(const _Line& line, double t, double& x, double& y) {
    120     double one_t = 1 - t;
    121     if (&x) {
    122         x = one_t * line[0].x + t * line[1].x;
    123     }
    124     if (&y) {
    125         y = one_t * line[0].y + t * line[1].y;
    126     }
    127 }
    128 
    129 _Point xy_at_t(const _Line& line, double t) {
    130     double one_t = 1 - t;
    131     _Point result = { one_t * line[0].x + t * line[1].x, one_t * line[0].y + t * line[1].y };
    132     return result;
    133 }
    134