CurveIntersection.h revision 235f56a92f6eb6accbb243e11b3c45e3798f38f2
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); 18void chop_at(const Cubic& src, CubicPair& dst, double t); 19void chop_at(const Quadratic& src, QuadraticPair& dst, double t); 20int convex_hull(const Cubic& cubic, char order[4]); 21bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]); 22bool implicit_matches(const Cubic& cubic1, const Cubic& cubic2); 23bool implicit_matches(const _Line& line1, const _Line& line2); 24bool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps); 25bool implicit_matches(const Quadratic& quad1, const Quadratic& quad2); 26void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst); 27void sub_divide(const _Line& src, double t1, double t2, _Line& dst); 28void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst); 29void tangent(const Cubic& cubic, double t, _Point& result); 30void tangent(const _Line& line, _Point& result); 31void tangent(const Quadratic& quad, double t, _Point& result); 32 33// main functions 34enum ReduceOrder_Flags { 35 kReduceOrder_NoQuadraticsAllowed, 36 kReduceOrder_QuadraticsAllowed 37}; 38int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags ); 39int reduceOrder(const _Line& line, _Line& reduction); 40int reduceOrder(const Quadratic& quad, Quadratic& reduction); 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& ); 53int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]); 54bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& ); 55int intersect(const Quadratic& quad, const _Line& line, Intersections& ); 56// the following flavor uses the implicit form instead of convex hulls 57bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i); 58int intersectRay(const Quadratic& quad, const _Line& line, Intersections& i); 59 60 61bool isLinear(const Quadratic& quad, int startIndex, int endIndex); 62bool isLinear(const Cubic& cubic, int startIndex, int endIndex); 63double leftMostT(const Cubic& , double startT, double endT); 64double leftMostT(const _Line& , double startT, double endT); 65double leftMostT(const Quadratic& , double startT, double endT); 66int verticalIntersect(const Cubic& cubic, double top, double bottom, double x, 67 bool flipped, Intersections& ); 68int verticalIntersect(const _Line& line, double top, double bottom, double x, 69 bool flipped, Intersections& ); 70int verticalIntersect(const Quadratic& quad, double top, double bottom, 71 double x, bool flipped, Intersections& ); 72 73#endif 74