Home | History | Annotate | Download | only in Intersection 
      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 
      8 #include "CubicUtilities.h"
      9 #include "CurveIntersection.h"
     10 #include "TestUtilities.h"
     11 
     12 void quad_to_cubic(const Quadratic& quad, Cubic& cubic) {
     13     cubic[0] = quad[0];
     14     cubic[1].x = quad[0].x / 3 + quad[1].x * 2 / 3;
     15     cubic[1].y = quad[0].y / 3 + quad[1].y * 2 / 3;
     16     cubic[2].x = quad[2].x / 3 + quad[1].x * 2 / 3;
     17     cubic[2].y = quad[2].y / 3 + quad[1].y * 2 / 3;
     18     cubic[3] = quad[2];
     19 }
     20 
     21 static bool tiny(const Cubic& cubic) {
     22     int index, minX, maxX, minY, maxY;
     23     minX = maxX = minY = maxY = 0;
     24     for (index = 1; index < 4; ++index) {
     25         if (cubic[minX].x > cubic[index].x) {
     26             minX = index;
     27         }
     28         if (cubic[minY].y > cubic[index].y) {
     29             minY = index;
     30         }
     31         if (cubic[maxX].x < cubic[index].x) {
     32             maxX = index;
     33         }
     34         if (cubic[maxY].y < cubic[index].y) {
     35             maxY = index;
     36         }
     37     }
     38     return     approximately_equal(cubic[maxX].x, cubic[minX].x)
     39             && approximately_equal(cubic[maxY].y, cubic[minY].y);
     40 }
     41 
     42 void find_tight_bounds(const Cubic& cubic, _Rect& bounds) {
     43     CubicPair cubicPair;
     44     chop_at(cubic, cubicPair, 0.5);
     45     if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
     46         find_tight_bounds(cubicPair.first(), bounds);
     47     } else {
     48         bounds.add(cubicPair.first()[0]);
     49         bounds.add(cubicPair.first()[3]);
     50     }
     51     if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
     52         find_tight_bounds(cubicPair.second(), bounds);
     53     } else {
     54         bounds.add(cubicPair.second()[0]);
     55         bounds.add(cubicPair.second()[3]);
     56     }
     57 }
     58 
     59 bool controls_inside(const Cubic& cubic) {
     60     return
     61         ((cubic[0].x <= cubic[1].x && cubic[0].x <= cubic[2].x && cubic[1].x <= cubic[3].x && cubic[2].x <= cubic[3].x)
     62      ||  (cubic[0].x >= cubic[1].x && cubic[0].x >= cubic[2].x && cubic[1].x >= cubic[3].x && cubic[2].x >= cubic[3].x))
     63      && ((cubic[0].y <= cubic[1].y && cubic[0].y <= cubic[2].y && cubic[1].y <= cubic[3].y && cubic[2].y <= cubic[3].y)
     64      ||  (cubic[0].y >= cubic[1].y && cubic[0].y >= cubic[2].y && cubic[1].y >= cubic[3].y && cubic[2].x >= cubic[3].y));
     65 }
     66