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 "CurveIntersection.h"
      8 #include "CurveUtilities.h"
      9 #include "IntersectionUtilities.h"
     10 
     11 /* Given a cubic, find the convex hull described by the end and control points.
     12    The hull may have 3 or 4 points. Cubics that degenerate into a point or line
     13    are not considered.
     14 
     15    The hull is computed by assuming that three points, if unique and non-linear,
     16    form a triangle. The fourth point may replace one of the first three, may be
     17    discarded if in the triangle or on an edge, or may be inserted between any of
     18    the three to form a convex quadralateral.
     19 
     20    The indices returned in order describe the convex hull.
     21 */
     22 int convex_hull(const Cubic& cubic, char order[4]) {
     23     size_t index;
     24     // find top point
     25     size_t yMin = 0;
     26     for (index = 1; index < 4; ++index) {
     27         if (cubic[yMin].y > cubic[index].y || (cubic[yMin].y == cubic[index].y
     28                 && cubic[yMin].x > cubic[index].x)) {
     29             yMin = index;
     30         }
     31     }
     32     order[0] = yMin;
     33     int midX = -1;
     34     int backupYMin = -1;
     35     for (int pass = 0; pass < 2; ++pass) {
     36         for (index = 0; index < 4; ++index) {
     37             if (index == yMin) {
     38                 continue;
     39             }
     40             // rotate line from (yMin, index) to axis
     41             // see if remaining two points are both above or below
     42             // use this to find mid
     43             int mask = other_two(yMin, index);
     44             int side1 = yMin ^ mask;
     45             int side2 = index ^ mask;
     46             Cubic rotPath;
     47             if (!rotate(cubic, yMin, index, rotPath)) { // ! if cbc[yMin]==cbc[idx]
     48                 order[1] = side1;
     49                 order[2] = side2;
     50                 return 3;
     51             }
     52             int sides = side(rotPath[side1].y - rotPath[yMin].y);
     53             sides ^= side(rotPath[side2].y - rotPath[yMin].y);
     54             if (sides == 2) { // '2' means one remaining point <0, one >0
     55                 if (midX >= 0) {
     56                     printf("%s unexpected mid\n", __FUNCTION__); // there can be only one mid
     57                 }
     58                 midX = index;
     59             } else if (sides == 0) { // '0' means both to one side or the other
     60                 backupYMin = index;
     61             }
     62         }
     63         if (midX >= 0) {
     64             break;
     65         }
     66         if (backupYMin < 0) {
     67             break;
     68         }
     69         yMin = backupYMin;
     70         backupYMin = -1;
     71     }
     72     if (midX < 0) {
     73         midX = yMin ^ 3; // choose any other point
     74     }
     75     int mask = other_two(yMin, midX);
     76     int least = yMin ^ mask;
     77     int most = midX ^ mask;
     78     order[0] = yMin;
     79     order[1] = least;
     80 
     81     // see if mid value is on same side of line (least, most) as yMin
     82     Cubic midPath;
     83     if (!rotate(cubic, least, most, midPath)) { // ! if cbc[least]==cbc[most]
     84         order[2] = midX;
     85         return 3;
     86     }
     87     int midSides = side(midPath[yMin].y - midPath[least].y);
     88     midSides ^= side(midPath[midX].y - midPath[least].y);
     89     if (midSides != 2) {  // if mid point is not between
     90         order[2] = most;
     91         return 3; // result is a triangle
     92     }
     93     order[2] = midX;
     94     order[3] = most;
     95     return 4; // result is a quadralateral
     96 }
     97 
     98 /* Find the convex hull for cubics with the x-axis interval regularly spaced.
     99    Cubics computed as distance functions are formed this way.
    100 
    101    connectTo0[0], connectTo0[1] are the point indices that cubic[0] connects to.
    102    connectTo3[0], connectTo3[1] are the point indices that cubic[3] connects to.
    103 
    104    Returns true if cubic[1] to cubic[2] also forms part of the hull.
    105 */
    106 bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]) {
    107     double projectedY[4];
    108     projectedY[0] = 0;
    109     int index;
    110     for (index = 1; index < 4; ++index) {
    111         projectedY[index] = (cubic[index].y - cubic[0].y) * (3.0 / index);
    112     }
    113     int lower0Index = 1;
    114     int upper0Index = 1;
    115     for (index = 2; index < 4; ++index) {
    116         if (approximately_greater_or_equal(projectedY[lower0Index], projectedY[index])) {
    117             lower0Index = index;
    118         }
    119         if (approximately_lesser_or_equal(projectedY[upper0Index], projectedY[index])) {
    120             upper0Index = index;
    121         }
    122     }
    123     connectTo0[0] = lower0Index;
    124     connectTo0[1] = upper0Index;
    125     for (index = 0; index < 3; ++index) {
    126         projectedY[index] = (cubic[3].y - cubic[index].y) * (3.0 / (3 - index));
    127     }
    128     projectedY[3] = 0;
    129     int lower3Index = 2;
    130     int upper3Index = 2;
    131     for (index = 1; index > -1; --index) {
    132         if (approximately_greater_or_equal(projectedY[lower3Index], projectedY[index])) {
    133             lower3Index = index;
    134         }
    135         if (approximately_lesser_or_equal(projectedY[upper3Index], projectedY[index])) {
    136             upper3Index = index;
    137         }
    138     }
    139     connectTo3[0] = lower3Index;
    140     connectTo3[1] = upper3Index;
    141     return (1 << lower0Index | 1 << upper0Index
    142             | 1 << lower3Index | 1 << upper3Index) == 0x0F;
    143 }
    144