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