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 #include "DataTypes.h"
      8 
      9 // Sources
     10 // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
     11 // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
     12 
     13 // This turns a line segment into a parameterized line, of the form
     14 // ax + by + c = 0
     15 // When a^2 + b^2 == 1, the line is normalized.
     16 // The distance to the line for (x, y) is d(x,y) = ax + by + c
     17 //
     18 // Note that the distances below are not necessarily normalized. To get the true
     19 // distance, it's necessary to either call normalize() after xxxEndPoints(), or
     20 // divide the result of xxxDistance() by sqrt(normalSquared())
     21 
     22 class LineParameters {
     23 public:
     24     void cubicEndPoints(const Cubic& pts) {
     25         cubicEndPoints(pts, 0, 3);
     26     }
     27 
     28     void cubicEndPoints(const Cubic& pts, int s, int e) {
     29         a = approximately_pin(pts[s].y - pts[e].y);
     30         b = approximately_pin(pts[e].x - pts[s].x);
     31         c = pts[s].x * pts[e].y - pts[e].x * pts[s].y;
     32     }
     33 
     34     void lineEndPoints(const _Line& pts) {
     35         a = approximately_pin(pts[0].y - pts[1].y);
     36         b = approximately_pin(pts[1].x - pts[0].x);
     37         c = pts[0].x * pts[1].y - pts[1].x * pts[0].y;
     38     }
     39 
     40     void quadEndPoints(const Quadratic& pts) {
     41         quadEndPoints(pts, 0, 2);
     42     }
     43 
     44     void quadEndPoints(const Quadratic& pts, int s, int e) {
     45         a = approximately_pin(pts[s].y - pts[e].y);
     46         b = approximately_pin(pts[e].x - pts[s].x);
     47         c = pts[s].x * pts[e].y - pts[e].x * pts[s].y;
     48     }
     49 
     50     double normalSquared() const {
     51         return a * a + b * b;
     52     }
     53 
     54     bool normalize() {
     55         double normal = sqrt(normalSquared());
     56         if (approximately_zero(normal)) {
     57             a = b = c = 0;
     58             return false;
     59         }
     60         double reciprocal = 1 / normal;
     61         a *= reciprocal;
     62         b *= reciprocal;
     63         c *= reciprocal;
     64         return true;
     65     }
     66 
     67     void cubicDistanceY(const Cubic& pts, Cubic& distance) const {
     68         double oneThird = 1 / 3.0;
     69         for (int index = 0; index < 4; ++index) {
     70             distance[index].x = index * oneThird;
     71             distance[index].y = a * pts[index].x + b * pts[index].y + c;
     72         }
     73     }
     74 
     75     void quadDistanceY(const Quadratic& pts, Quadratic& distance) const {
     76         double oneHalf = 1 / 2.0;
     77         for (int index = 0; index < 3; ++index) {
     78             distance[index].x = index * oneHalf;
     79             distance[index].y = a * pts[index].x + b * pts[index].y + c;
     80         }
     81     }
     82 
     83     double controlPtDistance(const Cubic& pts, int index) const {
     84         SkASSERT(index == 1 || index == 2);
     85         return a * pts[index].x + b * pts[index].y + c;
     86     }
     87 
     88     double controlPtDistance(const Quadratic& pts) const {
     89         return a * pts[1].x + b * pts[1].y + c;
     90     }
     91 
     92     double pointDistance(const _Point& pt) const {
     93         return a * pt.x + b * pt.y + c;
     94     }
     95 
     96     double dx() const {
     97         return b;
     98     }
     99 
    100     double dy() const {
    101         return -a;
    102     }
    103 
    104 private:
    105     double a;
    106     double b;
    107     double c;
    108 };
    109