quad and conic do not intersect

src/pathops/SkPathOpsQuad.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkIntersections.h"
 #include "SkLineParameters.h"
 #include "SkPathOpsCubic.h"
 #include "SkPathOpsCurve.h"
 #include "SkPathOpsQuad.h"
 
+// from blackpawn.com/texts/pointinpoly
+static bool pointInTriangle(const SkDPoint fPts[3], const SkDPoint& test) {
+    SkDVector v0 = fPts[2] - fPts[0];
+    SkDVector v1 = fPts[1] - fPts[0];
+    SkDVector v2 = test - fPts[0];
+    double dot00 = v0.dot(v0);
+    double dot01 = v0.dot(v1);
+    double dot02 = v0.dot(v2);
+    double dot11 = v1.dot(v1);
+    double dot12 = v1.dot(v2);
+    // Compute barycentric coordinates
+    double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
+    double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+    double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+    // Check if point is in triangle
+    return u >= 0 && v >= 0 && u + v < 1;
+}
+
+static bool matchesEnd(const SkDPoint fPts[3], const SkDPoint& test) {
+    return fPts[0] == test || fPts[2] == test;
+}
+
 /* started with at_most_end_pts_in_common from SkDQuadIntersection.cpp */
 // Do a quick reject by rotating all points relative to a line formed by
 // a pair of one quad's points. If the 2nd quad's points
 // are on the line or on the opposite side from the 1st quad's 'odd man', the
 // curves at most intersect at the endpoints.
 /* if returning true, check contains true if quad's hull collapsed, making the cubic linear
    if returning false, check contains true if the the quad pair have only the end point in common
 */
 bool SkDQuad::hullIntersects(const SkDQuad& q2, bool* isLinear) const {
     bool linear = true;
@@ skipping 14 matching lines @@
             double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
             if (test * sign > 0 && !precisely_zero(test)) {
                 foundOutlier = true;
                 break;
             }
         }
         if (!foundOutlier) {
             return false;
         }
     }
+    if (linear && !matchesEnd(fPts, q2.fPts[0]) && !matchesEnd(fPts, q2.fPts[2])) {
+        // if the end point of the opposite quad is inside the hull that is nearly a line,
+        // then representing the quad as a line may cause the intersection to be missed.
+        // Check to see if the endpoint is in the triangle.
+        if (pointInTriangle(fPts, q2.fPts[0]) || pointInTriangle(fPts, q2.fPts[2])) {
+            linear = false;
+        }
+    }
     *isLinear = linear;
     return true;
 }
 
 bool SkDQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
     return conic.hullIntersects(*this, isLinear);
 }
 
 bool SkDQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
     return cubic.hullIntersects(*this, isLinear);
@@ skipping 294 matching lines @@
  * c =             C
  */
 void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) {
     *a = quad[0];      // a = A
     *b = 2 * quad[2];  // b =     2*B
     *c = quad[4];      // c =             C
     *b -= *c;          // b =     2*B -   C
     *a -= *b;          // a = A - 2*B +   C
     *b -= *c;          // b =     2*B - 2*C
 }