content: /*
   * Copyright (C) 2018 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package android.view.math;
  
  public class Math3DHelper {
  
      private static final float EPSILON = 0.0000001f;
  
      private Math3DHelper() { }
  
      /**
       * Calculates [p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2];
       *
       * @param d - dimension in which the poly is represented (supports 2 or 3D)
       * @return float[]{t2, t, p1} or float[]{Float.NaN}
       */
      public static float[] rayIntersectPoly(float[] poly, int polyLength, float px, float py,
              float dx, float dy, int d) {
          int p1 = polyLength - 1;
          for (int p2 = 0; p2 < polyLength; p2++) {
              float p1x = poly[p1 * d + 0];
              float p1y = poly[p1 * d + 1];
              float p2x = poly[p2 * d + 0];
              float p2y = poly[p2 * d + 1];
              float div = (dx * (p1y - p2y) + dy * (p2x - p1x));
              if (div != 0) {
                  float t = (dx * (p1y - py) + dy * (px - p1x)) / div;
                  if (t >= 0 && t <= 1) {
                      float t2 = (p1x * (py - p2y)
                              + p2x * (p1y - py)
                              + px * (p2y - p1y))
                              / div;
                      if (t2 > 0) {
                          return new float[]{t2, t, p1};
                      }
                  }
              }
              p1 = p2;
          }
          return new float[]{Float.NaN};
      }
  
      public static void centroid2d(float[] poly, int len, float[] ret) {
          float sumx = 0;
          float sumy = 0;
          int p1 = len - 1;
          float area = 0;
          for (int p2 = 0; p2 < len; p2++) {
              float x1 = poly[p1 * 2 + 0];
              float y1 = poly[p1 * 2 + 1];
              float x2 = poly[p2 * 2 + 0];
              float y2 = poly[p2 * 2 + 1];
              float a = (x1 * y2 - x2 * y1);
              sumx += (x1 + x2) * a;
              sumy += (y1 + y2) * a;
              area += a;
              p1 = p2;
          }
          float centroidx = sumx / (3 * area);
          float centroidy = sumy / (3 * area);
          ret[0] = centroidx;
          ret[1] = centroidy;
      }
  
      public static void centroid3d(float[] poly, int len, float[] ret) {
          int n = len - 1;
          double area = 0;
          double cx = 0;
          double cy = 0;
          double cz = 0;
          for (int i = 1; i < n; i++) {
              int k = i + 1;
              float a0 = poly[i * 3 + 0] - poly[0 * 3 + 0];
              float a1 = poly[i * 3 + 1] - poly[0 * 3 + 1];
              float a2 = poly[i * 3 + 2] - poly[0 * 3 + 2];
              float b0 = poly[k * 3 + 0] - poly[0 * 3 + 0];
              float b1 = poly[k * 3 + 1] - poly[0 * 3 + 1];
              float b2 = poly[k * 3 + 2] - poly[0 * 3 + 2];
              float c0 = a1 * b2 - b1 * a2;
              float c1 = a2 * b0 - b2 * a0;
              float c2 = a0 * b1 - b0 * a1;
              double areaOfTriangle = Math.sqrt(c0 * c0 + c1 * c1 + c2 * c2);
              area += areaOfTriangle;
              cx += areaOfTriangle * (poly[i * 3 + 0] + poly[k * 3 + 0] + poly[0 * 3 + 0]);
              cy += areaOfTriangle * (poly[i * 3 + 1] + poly[k * 3 + 1] + poly[0 * 3 + 1]);
              cz += areaOfTriangle * (poly[i * 3 + 2] + poly[k * 3 + 2] + poly[0 * 3 + 2]);
          }
          ret[0] = (float) (cx / (3 * area));
          ret[1] = (float) (cy / (3 * area));
          ret[2] = (float) (cz / (3 * area));
      }
  
      public final static int min(int x1, int x2, int x3) {
          return (x1 > x2) ? ((x2 > x3) ? x3 : x2) : ((x1 > x3) ? x3 : x1);
      }
  
      public final static int max(int x1, int x2, int x3) {
          return (x1 < x2) ? ((x2 < x3) ? x3 : x2) : ((x1 < x3) ? x3 : x1);
      }
  
      private static void xsort(float[] points, int pointsLength) {
          quicksortX(points, 0, pointsLength - 1);
      }
  
      public static int hull(float[] points, int pointsLength, float[] retPoly) {
          xsort(points, pointsLength);
          int n = pointsLength;
          float[] lUpper = new float[n * 2];
          lUpper[0] = points[0];
          lUpper[1] = points[1];
          lUpper[2] = points[2];
          lUpper[3] = points[3];
  
          int lUpperSize = 2;
  
          for (int i = 2; i < n; i++) {
              lUpper[lUpperSize * 2 + 0] = points[i * 2 + 0];
              lUpper[lUpperSize * 2 + 1] = points[i * 2 + 1];
              lUpperSize++;
  
              while (lUpperSize > 2 && !rightTurn(
                      lUpper[(lUpperSize - 3) * 2], lUpper[(lUpperSize - 3) * 2 + 1],
                      lUpper[(lUpperSize - 2) * 2], lUpper[(lUpperSize - 2) * 2 + 1],
                      lUpper[(lUpperSize - 1) * 2], lUpper[(lUpperSize - 1) * 2 + 1])) {
                  // Remove the middle point of the three last
                  lUpper[(lUpperSize - 2) * 2 + 0] = lUpper[(lUpperSize - 1) * 2 + 0];
                  lUpper[(lUpperSize - 2) * 2 + 1] = lUpper[(lUpperSize - 1) * 2 + 1];
                  lUpperSize--;
              }
          }
  
          float[] lLower = new float[n * 2];
          lLower[0] = points[(n - 1) * 2 + 0];
          lLower[1] = points[(n - 1) * 2 + 1];
          lLower[2] = points[(n - 2) * 2 + 0];
          lLower[3] = points[(n - 2) * 2 + 1];
  
          int lLowerSize = 2;
  
          for (int i = n - 3; i >= 0; i--) {
              lLower[lLowerSize * 2 + 0] = points[i * 2 + 0];
              lLower[lLowerSize * 2 + 1] = points[i * 2 + 1];
              lLowerSize++;
  
              while (lLowerSize > 2 && !rightTurn(
                      lLower[(lLowerSize - 3) * 2], lLower[(lLowerSize - 3) * 2 + 1],
                      lLower[(lLowerSize - 2) * 2], lLower[(lLowerSize - 2) * 2 + 1],
                      lLower[(lLowerSize - 1) * 2], lLower[(lLowerSize - 1) * 2 + 1])) {
                  // Remove the middle point of the three last
                  lLower[(lLowerSize - 2) * 2 + 0] = lLower[(lLowerSize - 1) * 2 + 0];
                  lLower[(lLowerSize - 2) * 2 + 1] = lLower[(lLowerSize - 1) * 2 + 1];
                  lLowerSize--;
              }
          }
          int count = 0;
  
          for (int i = 0; i < lUpperSize; i++) {
              retPoly[count * 2 + 0] = lUpper[i * 2 + 0];
              retPoly[count * 2 + 1] = lUpper[i * 2 + 1];
              count++;
          }
  
          for (int i = 1; i < lLowerSize - 1; i++) {
              retPoly[count * 2 + 0] = lLower[i * 2 + 0];
              retPoly[count * 2 + 1] = lLower[i * 2 + 1];
              count++;
          }
  
          return count;
      }
  
      private static boolean rightTurn(float ax, float ay, float bx, float by, float cx, float cy) {
          return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > 0.00001;
      }
  
      /**
       * Calculates the intersection of poly1 with poly2 and puts in poly2
       * @return number of point in poly2
       */
      public static int intersection(
              float[] poly1, int poly1length, float[] poly2, int poly2length) {
          makeClockwise(poly1, poly1length);
          makeClockwise(poly2, poly2length);
          float[] poly = new float[(poly1length * poly2length + 2) * 2];
          int count = 0;
          int pcount = 0;
          for (int i = 0; i < poly1length; i++) {
              if (pointInsidePolygon(poly1[i * 2], poly1[i * 2 + 1], poly2, poly2length)) {
                  poly[count * 2] = poly1[i * 2];
                  poly[count * 2 + 1] = poly1[i * 2 + 1];
                  count++;
                  pcount++;
              }
          }
          int fromP1 = pcount;
          for (int i = 0; i < poly2length; i++) {
              if (pointInsidePolygon(poly2[i * 2], poly2[i * 2 + 1], poly1, poly1length)) {
                  poly[count * 2] = poly2[i * 2];
                  poly[count * 2 + 1] = poly2[i * 2 + 1];
                  count++;
              }
          }
          int fromP2 = count - fromP1;
          if (fromP1 == poly1length) { // use p1
              for (int i = 0; i < poly1length; i++) {
                  poly2[i * 2] = poly1[i * 2];
                  poly2[i * 2 + 1] = poly1[i * 2 + 1];
              }
              return poly1length;
          }
          if (fromP2 == poly2length) { // use p2
              return poly2length;
          }
          float[] intersection = new float[2];
          for (int i = 0; i < poly2length; i++) {
              for (int j = 0; j < poly1length; j++) {
                  int i1_by_2 = i * 2;
                  int i2_by_2 = ((i + 1) % poly2length) * 2;
                  int j1_by_2 = j * 2;
                  int j2_by_2 = ((j + 1) % poly1length) * 2;
                  boolean found = lineIntersection(
                          poly2[i1_by_2], poly2[i1_by_2 + 1],
                          poly2[i2_by_2], poly2[i2_by_2 + 1],
                          poly1[j1_by_2], poly1[j1_by_2 + 1],
                          poly1[j2_by_2], poly1[j2_by_2 + 1], intersection);
                  if (found) {
                      poly[count * 2] = intersection[0];
                      poly[count * 2 + 1] = intersection[1];
                      count++;
                  } else {
                      float dx = poly2[i * 2] - poly1[j * 2];
                      float dy = poly2[i * 2 + 1] - poly1[j * 2 + 1];
  
                      if (dx * dx + dy * dy < 0.01) {
                          poly[count * 2] = poly2[i * 2];
                          poly[count * 2 + 1] = poly2[i * 2 + 1];
                          count++;
                      }
                  }
              }
          }
          if (count == 0) {
              return 0;
          }
          float avgx = 0;
          float avgy = 0;
          for (int i = 0; i < count; i++) {
              avgx += poly[i * 2];
              avgy += poly[i * 2 + 1];
          }
          avgx /= count;
          avgy /= count;
  
          float[] ctr = new float[] { avgx, avgy };
          sort(poly, count, ctr);
          int size = count;
  
          poly2[0] = poly[0];
          poly2[1] = poly[1];
  
          count = 1;
          for (int i = 1; i < size; i++) {
              float dx = poly[i * 2] - poly[(i - 1) * 2];
              float dy = poly[i * 2 + 1] - poly[(i - 1) * 2 + 1];
              if (dx * dx + dy * dy >= 0.01) {
                  poly2[count * 2] = poly[i * 2];
                  poly2[count * 2 + 1] = poly[i * 2 + 1];
                  count++;
              }
          }
          return count;
      }
  
      public static void sort(float[] poly, int polyLength, float[] ctr) {
          quicksortCirc(poly, 0, polyLength - 1, ctr);
      }
  
      public static float angle(float x1, float y1, float[] ctr) {
          return -(float) Math.atan2(x1 - ctr[0], y1 - ctr[1]);
      }
  
      private static void swap(float[] points, int i, int j) {
          float x = points[i * 2];
          float y = points[i * 2 + 1];
          points[i * 2] = points[j * 2];
          points[i * 2 + 1] = points[j * 2 + 1];
          points[j * 2] = x;
          points[j * 2 + 1] = y;
      }
  
      private static void quicksortCirc(float[] points, int low, int high, float[] ctr) {
          int i = low, j = high;
          int p = low + (high - low) / 2;
          float pivot = angle(points[p * 2], points[p * 2 + 1], ctr);
          while (i <= j) {
              while (angle(points[i * 2], points[i * 2 + 1], ctr) < pivot) {
                  i++;
              }
              while (angle(points[j * 2], points[j * 2 + 1], ctr) > pivot) {
                  j--;
              }
  
              if (i <= j) {
                  swap(points, i, j);
                  i++;
                  j--;
              }
          }
          if (low < j) {
              quicksortCirc(points, low, j, ctr);
          }
          if (i < high) {
              quicksortCirc(points, i, high, ctr);
          }
      }
  
      private static void quicksortX(float[] points, int low, int high) {
          int i = low, j = high;
          int p = low + (high - low) / 2;
          float pivot = points[p * 2];
          while (i <= j) {
              while (points[i * 2] < pivot) {
                  i++;
              }
              while (points[j * 2] > pivot) {
                  j--;
              }
  
              if (i <= j) {
                  swap(points, i, j);
                  i++;
                  j--;
              }
          }
          if (low < j) {
              quicksortX(points, low, j);
          }
          if (i < high) {
              quicksortX(points, i, high);
          }
      }
  
      private static boolean pointInsidePolygon(float x, float y, float[] poly, int len) {
          boolean c = false;
          float testx = x;
          float testy = y;
          for (int i = 0, j = len - 1; i < len; j = i++) {
              if (((poly[i * 2 + 1] > testy) != (poly[j * 2 + 1] > testy)) &&
                      (testx < (poly[j * 2] - poly[i * 2]) * (testy - poly[i * 2 + 1])
                              / (poly[j * 2 + 1] - poly[i * 2 + 1]) + poly[i * 2])) {
                  c = !c;
              }
          }
          return c;
      }
  
      private static void makeClockwise(float[] polygon, int len) {
          if (polygon == null || len == 0) {
              return;
          }
          if (!isClockwise(polygon, len)) {
              reverse(polygon, len);
          }
      }
  
      private static boolean isClockwise(float[] polygon, int len) {
          float sum = 0;
          float p1x = polygon[(len - 1) * 2];
          float p1y = polygon[(len - 1) * 2 + 1];
          for (int i = 0; i < len; i++) {
  
              float p2x = polygon[i * 2];
              float p2y = polygon[i * 2 + 1];
              sum += p1x * p2y - p2x * p1y;
              p1x = p2x;
              p1y = p2y;
          }
          return sum < 0;
      }
  
      private static void reverse(float[] polygon, int len) {
          int n = len / 2;
          for (int i = 0; i < n; i++) {
              float tmp0 = polygon[i * 2];
              float tmp1 = polygon[i * 2 + 1];
              int k = len - 1 - i;
              polygon[i * 2] = polygon[k * 2];
              polygon[i * 2 + 1] = polygon[k * 2 + 1];
              polygon[k * 2] = tmp0;
              polygon[k * 2 + 1] = tmp1;
          }
      }
  
      /**
       * Intersects two lines in parametric form.
       */
      private static final boolean lineIntersection(
              float x1, float y1,
              float x2, float y2,
              float x3, float y3,
              float x4, float y4,
              float[] ret) {
  
          float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
          if (d == 0.000f) {
              return false;
          }
  
          float dx = (x1 * y2 - y1 * x2);
          float dy = (x3 * y4 - y3 * x4);
          float x = (dx * (x3 - x4) - (x1 - x2) * dy) / d;
          float y = (dx * (y3 - y4) - (y1 - y2) * dy) / d;
  
          if (((x - x1) * (x - x2) > EPSILON)
                  || ((x - x3) * (x - x4) > EPSILON)
                  || ((y - y1) * (y - y2) > EPSILON)
                  || ((y - y3) * (y - y4) > EPSILON)) {
  
              return false;
          }
          ret[0] = x;
          ret[1] = y;
          return true;
      }
  
      /**
       * Imagine a donut shaped image and trying to create triangles from its centroid (like
       * cutting a pie). This function performs such action (and also edge-case triangle strips
       * generation) then returns the resulting triangle strips.
       *
       * @param retstrips - the resulting triangle strips
       */
      public static void donutPie2(float[] penumbra, int penumbraLength,
              float[] umbra, int umbraLength, int rays, int layers, float strength,
              float[] retstrips) {
          int rings = layers + 1;
  
          double step = Math.PI * 2 / rays;
          float[] retxy = new float[2];
          centroid2d(umbra, umbraLength, retxy);
          float cx = retxy[0];
          float cy = retxy[1];
  
          float[] t1 = new float[rays];
          float[] t2 = new float[rays];
  
          for (int i = 0; i < rays; i++) {
              float dx = (float) Math.sin(Math.PI / 4 + step * i);
              float dy = (float) Math.cos(Math.PI / 4 + step * i);
              t2[i] = rayIntersectPoly(umbra, umbraLength, cx, cy, dx, dy, 2)[0];
              t1[i] = rayIntersectPoly(penumbra, penumbraLength, cx, cy, dx, dy, 2)[0];
          }
  
          int p = 0;
          // Calc the vertex
          for (int r = 0; r < layers; r++) {
              int startp = p;
              for (int i = 0; i < rays; i++) {
                  float dx = (float) Math.sin(Math.PI / 4 + step * i);
                  float dy = (float) Math.cos(Math.PI / 4 + step * i);
  
                  for (int j = r; j < (r + 2); j++) {
                      float jf = j / (float) (rings - 1);
                      float t = t1[i] + jf * (t2[i] - t1[i]);
                      float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2;
  
                      retstrips[p * 3] = dx * t + cx;
                      retstrips[p * 3 + 1] = dy * t + cy;
                      retstrips[p * 3 + 2] = jf * op * strength;
  
                      p++;
                  }
              }
              retstrips[p * 3] = retstrips[startp * 3];
              retstrips[p * 3 + 1] = retstrips[startp * 3 + 1];
              retstrips[p * 3 + 2] = retstrips[startp * 3 + 2];
              p++;
              startp++;
              retstrips[p * 3] = retstrips[startp * 3];
              retstrips[p * 3 + 1] = retstrips[startp * 3 + 1];
              retstrips[p * 3 + 2] = retstrips[startp * 3 + 2];
              p++;
          }
          int oldp = p - 1;
          retstrips[p * 3] = retstrips[oldp * 3];
          retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1];
          retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2];
          p+=2;
  
          oldp = p;
          for (int k = 0; k < rays; k++) {
              int i = k / 2;
              if ((k & 1) == 1) { // traverse the inside in a zig zag pattern
                  // for strips
                  i = rays - i - 1;
              }
              float dx = (float) Math.sin(Math.PI / 4 + step * i);
              float dy = (float) Math.cos(Math.PI / 4 + step * i);
  
              float jf = 1;
  
              float t = t1[i] + jf * (t2[i] - t1[i]);
              float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2;
  
              retstrips[p * 3] = dx * t + cx;
              retstrips[p * 3 + 1] = dy * t + cy;
              retstrips[p * 3 + 2] = jf * op * strength;
              p++;
          }
          p = oldp - 1;
          retstrips[p * 3] = retstrips[oldp * 3];
          retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1];
          retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2];
      }
  
      /**
       * @return Rect bound of flattened (ignoring z). LTRB
       * @param dimension - 2D or 3D
       */
      public static float[] flatBound(float[] poly, int dimension) {
          int polySize = poly.length/dimension;
          float left = poly[0];
          float right = poly[0];
          float top = poly[1];
          float bottom = poly[1];
  
          for (int i = 0; i < polySize; i++) {
              float x = poly[i * dimension + 0];
              float y = poly[i * dimension + 1];
  
              if (left > x) {
                  left = x;
              } else if (right < x) {
                  right = x;
              }
  
              if (top > y) {
                  top = y;
              } else if (bottom < y) {
                  bottom = y;
              }
          }
          return new float[]{left, top, right, bottom};
      }
  
      /**
       * Translate the polygon to x and y
       * @param dimension in what dimension is polygon represented (supports 2 or 3D).
       */
      public static void translate(float[] poly, float translateX, float translateY, int dimension) {
          int polySize = poly.length/dimension;
  
          for (int i = 0; i < polySize; i++) {
              poly[i * dimension + 0] += translateX;
              poly[i * dimension + 1] += translateY;
          }
      }
  
  }
  
  