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
10bool 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
24int 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
31void 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));
61double 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
67double 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
82static 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
91void 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
119void 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