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