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