image/lib/src/util/clip_line.dart

/**
 * Clip a line to a rectangle using the Cohen–Sutherland clipping algorithm.
 * [line] is a list of 4 ints <x1, y1, x2, y2>.
 * [rect] is a list of 4 ints <x1, y1, x2, y2>.
 * Results are stored in [line].
 * If [line] falls completely outside of [rect], false is returned, otherwise
 * true is returned.
 */
bool clipLine(List<int> line, List<int> rect) {
  int x0 = line[0];
  int y0 = line[1];
  int x1 = line[2];
  int y1 = line[3];
  int xmin = rect[0];
  int ymin = rect[1];
  int xmax = rect[2];
  int ymax = rect[3];

  const int INSIDE = 0; // 0000
  const int LEFT = 1;   // 0001
  const int RIGHT = 2;  // 0010
  const int BOTTOM = 4; // 0100
  const int TOP = 8;    // 1000

  // Compute the bit code for a point (x, y) using the clip rectangle
  // bounded diagonally by (xmin, ymin), and (xmax, ymax)
  int _computeOutCode(int x, int y) {
    int code = INSIDE; // initialised as being inside of clip window
    if (x < xmin) { // to the left of clip window
      code |= LEFT;
    } else if (x > xmax) { // to the right of clip window
      code |= RIGHT;
    }

    if (y < ymin) { // below the clip window
      code |= BOTTOM;
    } else if (y > ymax) { // above the clip window
      code |= TOP;
    }

    return code;
  }

  // compute outcodes for P0, P1, and whatever point lies outside the clip
  // rectangle
  int outcode0 = _computeOutCode(x0, y0);
  int outcode1 = _computeOutCode(x1, y1);
  bool accept = false;

  while (true) {
    if ((outcode0 | outcode1) == 0) {
      // Bitwise OR is 0. Trivially accept and get out of loop
      accept = true;
      break;
    } else if ((outcode0 & outcode1) != 0) {
      // Bitwise AND is not 0. Trivially reject and get out of loop
      break;
    } else {
      // failed both tests, so calculate the line segment to clip
      // from an outside point to an intersection with clip edge

      // At least one endpoint is outside the clip rectangle; pick it.
      int outcodeOut = outcode0 != 0 ? outcode0 : outcode1;

      int x, y;
      // Now find the intersection point;
      // use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
      if ((outcodeOut & TOP) != 0) {
        // point is above the clip rectangle
        x = x0 + (x1 - x0) * (ymax - y0) ~/ (y1 - y0);
        y = ymax;
      } else if ((outcodeOut & BOTTOM) != 0) {
        // point is below the clip rectangle
        x = x0 + (x1 - x0) * (ymin - y0) ~/ (y1 - y0);
        y = ymin;
      } else if ((outcodeOut & RIGHT) != 0) {
        // point is to the right of clip rectangle
        y = y0 + (y1 - y0) * (xmax - x0) ~/ (x1 - x0);
        x = xmax;
      } else if ((outcodeOut & LEFT) != 0) {
        // point is to the left of clip rectangle
        y = y0 + (y1 - y0) * (xmin - x0) ~/ (x1 - x0);
        x = xmin;
      }

      // Now we move outside point to intersection point to clip
      // and get ready for next pass.
      if (outcodeOut == outcode0) {
        x0 = x;
        y0 = y;
        outcode0 = _computeOutCode(x0, y0);
      } else {
        x1 = x;
        y1 = y;
        outcode1 = _computeOutCode(x1, y1);
      }
    }
  }

  line[0] = x0;
  line[1] = y0;
  line[2] = x1;
  line[3] = y1;

  return accept;
}