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#ifndef CurveIntersection_DEFINE
8#define CurveIntersection_DEFINE
9
10#include "DataTypes.h"
11
12class Intersections;
13
14// unit-testable utilities
15double axialIntersect(const Quadratic& q1, const _Point& p, bool vert);
16bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT);
17bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT);
18int convex_hull(const Cubic& cubic, char order[4]);
19bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]);
20bool implicit_matches(const Cubic& cubic1, const Cubic& cubic2);
21bool implicit_matches(const _Line& line1, const _Line& line2);
22bool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps);
23bool implicit_matches(const Quadratic& quad1, const Quadratic& quad2);
24void tangent(const Cubic& cubic, double t, _Point& result);
25void tangent(const _Line& line, _Point& result);
26void tangent(const Quadratic& quad, double t, _Point& result);
27
28// main functions
29enum ReduceOrder_Quadratics {
30    kReduceOrder_NoQuadraticsAllowed,
31    kReduceOrder_QuadraticsAllowed
32};
33enum ReduceOrder_Styles {
34    kReduceOrder_TreatAsStroke,
35    kReduceOrder_TreatAsFill
36};
37int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics ,
38        ReduceOrder_Styles );
39int reduceOrder(const _Line& line, _Line& reduction);
40int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles );
41int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]);
42int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
43        double tRange[3]);
44int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
45        bool flipped, Intersections&);
46int horizontalIntersect(const _Line& line, double left, double right,
47        double y, bool flipped, Intersections& );
48int horizontalIntersect(const Quadratic& quad, double left, double right,
49        double y, double tRange[2]);
50int horizontalIntersect(const Quadratic& quad, double left, double right,
51        double y, bool flipped, Intersections& );
52bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
53// the following flavor uses quadratic approximation instead of convex hulls
54//bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
55// like '2', but iterates on centers instead of possible edges
56bool intersect3(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
57int intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects
58int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& );
59int intersect(const Cubic& cubic, const _Line& line, Intersections& );
60int intersectRay(const Cubic& quad, const _Line& line, Intersections& i);
61bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& );
62int intersect(const Quadratic& quad, const _Line& line, Intersections& );
63// the following flavor uses the implicit form instead of convex hulls
64bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i);
65int intersectRay(const Quadratic& quad, const _Line& line, Intersections& i);
66
67
68bool isLinear(const Quadratic& quad, int startIndex, int endIndex);
69bool isLinear(const Cubic& cubic, int startIndex, int endIndex);
70double leftMostT(const Cubic& , double startT, double endT);
71double leftMostT(const _Line& , double startT, double endT);
72double leftMostT(const Quadratic& , double startT, double endT);
73int verticalIntersect(const Cubic& cubic, double top, double bottom, double x,
74        bool flipped, Intersections& );
75int verticalIntersect(const _Line& line, double top, double bottom, double x,
76        bool flipped, Intersections& );
77int verticalIntersect(const Quadratic& quad, double top, double bottom,
78        double x, bool flipped, Intersections& );
79
80#endif
81