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 "CurveUtilities.h" 9#include "Extrema.h" 10 11static int isBoundedByEndPoints(double a, double b, double c, double d) 12{ 13 return between(a, b, d) && between(a, c, d); 14} 15 16double leftMostT(const Cubic& cubic, double startT, double endT) { 17 double leftTs[2]; 18 _Point pt[2]; 19 int results = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, leftTs); 20 int best = -1; 21 for (int index = 0; index < results; ++index) { 22 if (startT > leftTs[index] || leftTs[index] > endT) { 23 continue; 24 } 25 if (best < 0) { 26 best = index; 27 continue; 28 } 29 xy_at_t(cubic, leftTs[0], pt[0].x, pt[0].y); 30 xy_at_t(cubic, leftTs[1], pt[1].x, pt[1].y); 31 if (pt[0].x > pt[1].x) { 32 best = 1; 33 } 34 } 35 if (best >= 0) { 36 return leftTs[best]; 37 } 38 xy_at_t(cubic, startT, pt[0].x, pt[0].y); 39 xy_at_t(cubic, endT, pt[1].x, pt[1].y); 40 return pt[0].x <= pt[1].x ? startT : endT; 41} 42 43void _Rect::setBounds(const Cubic& cubic) { 44 set(cubic[0]); 45 add(cubic[3]); 46 double tValues[4]; 47 int roots = 0; 48 if (!isBoundedByEndPoints(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x)) { 49 roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues); 50 } 51 if (!isBoundedByEndPoints(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y)) { 52 roots += findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, &tValues[roots]); 53 } 54 for (int x = 0; x < roots; ++x) { 55 _Point result; 56 xy_at_t(cubic, tValues[x], result.x, result.y); 57 add(result); 58 } 59} 60 61void _Rect::setRawBounds(const Cubic& cubic) { 62 set(cubic[0]); 63 for (int x = 1; x < 4; ++x) { 64 add(cubic[x]); 65 } 66} 67