com/android/layoutlib/bridge/util/CachedPathIteratorFactory.java - platform/prebuilts/fullsdk/sources/android-29 - Git at Google

 /*
  * Copyright (C) 2015 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 com.android.layoutlib.bridge.util;

 import android.annotation.NonNull;

 import java.awt.geom.CubicCurve2D;
 import java.awt.geom.PathIterator;
 import java.awt.geom.Point2D;
 import java.awt.geom.QuadCurve2D;
 import java.util.ArrayList;

 import com.google.android.collect.Lists;

 /**
  * Class that returns iterators for a given path. These iterators are lightweight and can be reused
  * multiple times to iterate over the path.
  */
 public class CachedPathIteratorFactory {
     /*
      * A few conventions used in the code:
      * Coordinates or coords arrays store segment coordinates. They use the same format as
      * PathIterator#currentSegment coordinates array.
      * float arrays store always points where the first element is X and the second is Y.
      */

     // This governs how accurate the approximation of the Path is.
     private static final float PRECISION = 0.002f;

     private final int mWindingRule;
     private final int[] mTypes;
     private final float[][] mCoordinates;
     private final float[] mSegmentsLength;
     private final float mTotalLength;

     public CachedPathIteratorFactory(@NonNull PathIterator iterator) {
         mWindingRule = iterator.getWindingRule();

         ArrayList<Integer> typesArray = Lists.newArrayList();
         ArrayList<float[]> pointsArray = Lists.newArrayList();
         float[] points = new float[6];
         while (!iterator.isDone()) {
             int type = iterator.currentSegment(points);
             int nPoints = getNumberOfPoints(type) * 2; // 2 coordinates per point

             typesArray.add(type);
             float[] itemPoints = new float[nPoints];
             System.arraycopy(points, 0, itemPoints, 0, nPoints);
             pointsArray.add(itemPoints);
             iterator.next();
         }

         mTypes = new int[typesArray.size()];
         mCoordinates = new float[mTypes.length][];
         for (int i = 0; i < typesArray.size(); i++) {
             mTypes[i] = typesArray.get(i);
             mCoordinates[i] = pointsArray.get(i);
         }

         // Do measurement
         mSegmentsLength = new float[mTypes.length];

         // Curves that we can reuse to estimate segments length
         CubicCurve2D.Float cubicCurve = new CubicCurve2D.Float();
         QuadCurve2D.Float quadCurve = new QuadCurve2D.Float();
         float lastX = 0;
         float lastY = 0;
         float totalLength = 0;
         for (int i = 0; i < mTypes.length; i++) {
             switch (mTypes[i]) {
                 case PathIterator.SEG_CUBICTO:
                     cubicCurve.setCurve(lastX, lastY,
                             mCoordinates[i][0], mCoordinates[i][1], mCoordinates[i][2],
                             mCoordinates[i][3], lastX = mCoordinates[i][4],
                             lastY = mCoordinates[i][5]);
                     mSegmentsLength[i] =
                             getFlatPathLength(cubicCurve.getPathIterator(null, PRECISION));
                     break;
                 case PathIterator.SEG_QUADTO:
                     quadCurve.setCurve(lastX, lastY, mCoordinates[i][0], mCoordinates[i][1],
                             lastX = mCoordinates[i][2], lastY = mCoordinates[i][3]);
                     mSegmentsLength[i] =
                             getFlatPathLength(quadCurve.getPathIterator(null, PRECISION));
                     break;
                 case PathIterator.SEG_CLOSE:
                     mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY,
                             lastX = mCoordinates[0][0],
                             lastY = mCoordinates[0][1]);
                     mCoordinates[i] = new float[2];
                     // We convert a SEG_CLOSE segment to a SEG_LINETO so we do not have to worry
                     // about this special case in the rest of the code.
                     mTypes[i] = PathIterator.SEG_LINETO;
                     mCoordinates[i][0] = mCoordinates[0][0];
                     mCoordinates[i][1] = mCoordinates[0][1];
                     break;
                 case PathIterator.SEG_MOVETO:
                     mSegmentsLength[i] = 0;
                     lastX = mCoordinates[i][0];
                     lastY = mCoordinates[i][1];
                     break;
                 case PathIterator.SEG_LINETO:
                     mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, mCoordinates[i][0],
                             mCoordinates[i][1]);
                     lastX = mCoordinates[i][0];
                     lastY = mCoordinates[i][1];
                 default:
             }
             totalLength += mSegmentsLength[i];
         }

         mTotalLength = totalLength;
     }

     private static void quadCurveSegment(float[] coords, float t0, float t1) {
         // Calculate X and Y at 0.5 (We'll use this to reconstruct the control point later)
         float mt = t0 + (t1 - t0) / 2;
         float mu = 1 - mt;
         float mx = mu * mu * coords[0] + 2 * mu * mt * coords[2] + mt * mt * coords[4];
         float my = mu * mu * coords[1] + 2 * mu * mt * coords[3] + mt * mt * coords[5];

         float u0 = 1 - t0;
         float u1 = 1 - t1;

         // coords at t0
         coords[0] = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
         coords[1] = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;

         // coords at t1
         coords[4] = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
         coords[5] = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;

         // estimated control point at t'=0.5
         coords[2] = 2 * mx - coords[0] / 2 - coords[4] / 2;
         coords[3] = 2 * my - coords[1] / 2 - coords[5] / 2;
     }

     private static void cubicCurveSegment(float[] coords, float t0, float t1) {
         // http://stackoverflow.com/questions/11703283/cubic-bezier-curve-segment
         float u0 = 1 - t0;
         float u1 = 1 - t1;

         // Calculate the points at t0 and t1 for the quadratic curves formed by (P0, P1, P2) and
         // (P1, P2, P3)
         float qxa = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
         float qxb = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
         float qxc = coords[2] * u0 * u0 + coords[4] * 2 * t0 * u0 + coords[6] * t0 * t0;
         float qxd = coords[2] * u1 * u1 + coords[4] * 2 * t1 * u1 + coords[6] * t1 * t1;

         float qya = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;
         float qyb = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;
         float qyc = coords[3] * u0 * u0 + coords[5] * 2 * t0 * u0 + coords[7] * t0 * t0;
         float qyd = coords[3] * u1 * u1 + coords[5] * 2 * t1 * u1 + coords[7] * t1 * t1;

         // Linear interpolation
         coords[0] = qxa * u0 + qxc * t0;
         coords[1] = qya * u0 + qyc * t0;

         coords[2] = qxa * u1 + qxc * t1;
         coords[3] = qya * u1 + qyc * t1;

         coords[4] = qxb * u0 + qxd * t0;
         coords[5] = qyb * u0 + qyd * t0;

         coords[6] = qxb * u1 + qxd * t1;
         coords[7] = qyb * u1 + qyd * t1;
     }

     /**
      * Returns the end point of a given segment
      *
      * @param type the segment type
      * @param coords the segment coordinates array
      * @param point the return array where the point will be stored
      */
     private static void getShapeEndPoint(int type, @NonNull float[] coords, @NonNull float[]
             point) {
         // start index of the end point for the segment type
         int pointIndex = (getNumberOfPoints(type) - 1) * 2;
         point[0] = coords[pointIndex];
         point[1] = coords[pointIndex + 1];
     }

     /**
      * Returns the number of points stored in a coordinates array for the given segment type.
      */
     private static int getNumberOfPoints(int segmentType) {
         switch (segmentType) {
             case PathIterator.SEG_QUADTO:
                 return 2;
             case PathIterator.SEG_CUBICTO:
                 return 3;
             case PathIterator.SEG_CLOSE:
                 return 0;
             default:
                 return 1;
         }
     }

     /**
      * Returns the estimated length of a flat path. If the passed path is not flat (i.e. contains a
      * segment that is not {@link PathIterator#SEG_CLOSE}, {@link PathIterator#SEG_MOVETO} or {@link
      * PathIterator#SEG_LINETO} this method will fail.
      */
     private static float getFlatPathLength(@NonNull PathIterator iterator) {
         float segment[] = new float[6];
         float totalLength = 0;
         float[] previousPoint = new float[2];
         boolean isFirstPoint = true;

         while (!iterator.isDone()) {
             int type = iterator.currentSegment(segment);
             assert type == PathIterator.SEG_LINETO || type == PathIterator.SEG_CLOSE || type ==
                     PathIterator.SEG_MOVETO;

             // MoveTo shouldn't affect the length
             if (!isFirstPoint && type != PathIterator.SEG_MOVETO) {
                 totalLength += Point2D.distance(previousPoint[0], previousPoint[1], segment[0],
                         segment[1]);
             } else {
                 isFirstPoint = false;
             }
             previousPoint[0] = segment[0];
             previousPoint[1] = segment[1];
             iterator.next();
         }

         return totalLength;
     }

     /**
      * Returns the estimated position along a path of the given length.
      */
     private void getPointAtLength(int type, @NonNull float[] coords, float lastX, float
             lastY, float t, @NonNull float[] point) {
         if (type == PathIterator.SEG_LINETO) {
             point[0] = lastX + (coords[0] - lastX) * t;
             point[1] = lastY + (coords[1] - lastY) * t;
             // Return here, since we do not need a shape to estimate
             return;
         }

         float[] curve = new float[8];
         int lastPointIndex = (getNumberOfPoints(type) - 1) * 2;

         System.arraycopy(coords, 0, curve, 2, coords.length);
         curve[0] = lastX;
         curve[1] = lastY;
         if (type == PathIterator.SEG_CUBICTO) {
             cubicCurveSegment(curve, 0f, t);
         } else {
             quadCurveSegment(curve, 0f, t);
         }

         point[0] = curve[2 + lastPointIndex];
         point[1] = curve[2 + lastPointIndex + 1];
     }

     public CachedPathIterator iterator() {
         return new CachedPathIterator();
     }

     /**
      * Class that allows us to iterate over a path multiple times
      */
     public class CachedPathIterator implements PathIterator {
         private int mNextIndex;

         /**
          * Current segment type.
          *
          * @see PathIterator
          */
         private int mCurrentType;

         /**
          * Stores the coordinates array of the current segment. The number of points stored depends
          * on the segment type.
          *
          * @see PathIterator
          */
         private float[] mCurrentCoords = new float[6];
         private float mCurrentSegmentLength;

         /**
          * Current segment length offset. When asking for the length of the current segment, the
          * length will be reduced by this amount. This is useful when we are only using portions of
          * the segment.
          *
          * @see #jumpToSegment(float)
          */
         private float mOffsetLength;

         /** Point where the current segment started */
         private float[] mLastPoint = new float[2];
         private boolean isIteratorDone;

         private CachedPathIterator() {
             next();
         }

         public float getCurrentSegmentLength() {
             return mCurrentSegmentLength;
         }

         @Override
         public int getWindingRule() {
             return mWindingRule;
         }

         @Override
         public boolean isDone() {
             return isIteratorDone;
         }

         @Override
         public void next() {
             if (mNextIndex >= mTypes.length) {
                 isIteratorDone = true;
                 return;
             }

             if (mNextIndex >= 1) {
                 // We've already called next() once so there is a previous segment in this path.
                 // We want to get the coordinates where the path ends.
                 getShapeEndPoint(mCurrentType, mCurrentCoords, mLastPoint);
             } else {
                 // This is the first segment, no previous point so initialize to 0, 0
                 mLastPoint[0] = mLastPoint[1] = 0f;
             }
             mCurrentType = mTypes[mNextIndex];
             mCurrentSegmentLength = mSegmentsLength[mNextIndex] - mOffsetLength;

             if (mOffsetLength > 0f && (mCurrentType == SEG_CUBICTO || mCurrentType == SEG_QUADTO)) {
                 // We need to skip part of the start of the current segment (because
                 // mOffsetLength > 0)
                 float[] points = new float[8];

                 if (mNextIndex < 1) {
                     points[0] = points[1] = 0f;
                 } else {
                     getShapeEndPoint(mTypes[mNextIndex - 1], mCoordinates[mNextIndex - 1], points);
                 }

                 System.arraycopy(mCoordinates[mNextIndex], 0, points, 2,
                         mCoordinates[mNextIndex].length);
                 float t0 = (mSegmentsLength[mNextIndex] - mCurrentSegmentLength) /
                         mSegmentsLength[mNextIndex];
                 if (mCurrentType == SEG_CUBICTO) {
                     cubicCurveSegment(points, t0, 1f);
                 } else {
                     quadCurveSegment(points, t0, 1f);
                 }
                 System.arraycopy(points, 2, mCurrentCoords, 0, mCoordinates[mNextIndex].length);
             } else {
                 System.arraycopy(mCoordinates[mNextIndex], 0, mCurrentCoords, 0,
                         mCoordinates[mNextIndex].length);
             }

             mOffsetLength = 0f;
             mNextIndex++;
         }

         @Override
         public int currentSegment(float[] coords) {
             System.arraycopy(mCurrentCoords, 0, coords, 0, getNumberOfPoints(mCurrentType) * 2);
             return mCurrentType;
         }

         @Override
         public int currentSegment(double[] coords) {
             throw new UnsupportedOperationException();
         }

         /**
          * Returns the point where the current segment ends
          */
         public void getCurrentSegmentEnd(float[] point) {
             point[0] = mLastPoint[0];
             point[1] = mLastPoint[1];
         }

         /**
          * Restarts the iterator and jumps all the segments of this path up to the length value.
          */
         public void jumpToSegment(float length) {
             isIteratorDone = false;
             if (length <= 0f) {
                 mNextIndex = 0;
                 return;
             }

             float accLength = 0;
             float lastPoint[] = new float[2];
             for (mNextIndex = 0; mNextIndex < mTypes.length; mNextIndex++) {
                 float segmentLength = mSegmentsLength[mNextIndex];
                 if (accLength + segmentLength >= length && mTypes[mNextIndex] != SEG_MOVETO) {
                     float[] estimatedPoint = new float[2];
                     getPointAtLength(mTypes[mNextIndex],
                             mCoordinates[mNextIndex], lastPoint[0], lastPoint[1],
                             (length - accLength) / segmentLength,
                             estimatedPoint);

                     // This segment makes us go further than length so we go back one step,
                     // set a moveto and offset the length of the next segment by the length
                     // of this segment that we've already used.
                     mCurrentType = PathIterator.SEG_MOVETO;
                     mCurrentCoords[0] = estimatedPoint[0];
                     mCurrentCoords[1] = estimatedPoint[1];
                     mCurrentSegmentLength = 0;

                     // We need to offset next path length to account for the segment we've just
                     // skipped.
                     mOffsetLength = length - accLength;
                     return;
                 }
                 accLength += segmentLength;
                 getShapeEndPoint(mTypes[mNextIndex], mCoordinates[mNextIndex], lastPoint);
             }
         }

         /**
          * Returns the current segment up to certain length. If the current segment is shorter than
          * length, then the whole segment is returned. The segment coordinates are copied into the
          * coords array.
          *
          * @return the segment type
          */
         public int currentSegment(@NonNull float[] coords, float length) {
             int type = currentSegment(coords);
             // If the length is greater than the current segment length, no need to find
             // the cut point. Same if this is a SEG_MOVETO.
             if (mCurrentSegmentLength <= length || type == SEG_MOVETO) {
                 return type;
             }

             float t = length / getCurrentSegmentLength();

             // We find at which offset the end point is located within the coords array and set
             // a new end point to cut the segment short
             switch (type) {
                 case SEG_CUBICTO:
                 case SEG_QUADTO:
                     float[] curve = new float[8];
                     curve[0] = mLastPoint[0];
                     curve[1] = mLastPoint[1];
                     System.arraycopy(coords, 0, curve, 2, coords.length);
                     if (type == SEG_CUBICTO) {
                         cubicCurveSegment(curve, 0f, t);
                     } else {
                         quadCurveSegment(curve, 0f, t);
                     }
                     System.arraycopy(curve, 2, coords, 0, coords.length);
                     break;
                 default:
                     float[] point = new float[2];
                     getPointAtLength(type, coords, mLastPoint[0], mLastPoint[1], t, point);
                     coords[0] = point[0];
                     coords[1] = point[1];
             }

             return type;
         }

         /**
          * Returns the total length of the path
          */
         public float getTotalLength() {
             return mTotalLength;
         }
     }
 }
	/*
	* Copyright (C) 2015 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 com.android.layoutlib.bridge.util;

	import android.annotation.NonNull;

	import java.awt.geom.CubicCurve2D;
	import java.awt.geom.PathIterator;
	import java.awt.geom.Point2D;
	import java.awt.geom.QuadCurve2D;
	import java.util.ArrayList;

	import com.google.android.collect.Lists;

	/**
	* Class that returns iterators for a given path. These iterators are lightweight and can be reused
	* multiple times to iterate over the path.
	*/
	public class CachedPathIteratorFactory {
	/*
	* A few conventions used in the code:
	* Coordinates or coords arrays store segment coordinates. They use the same format as
	* PathIterator#currentSegment coordinates array.
	* float arrays store always points where the first element is X and the second is Y.
	*/

	// This governs how accurate the approximation of the Path is.
	private static final float PRECISION = 0.002f;

	private final int mWindingRule;
	private final int[] mTypes;
	private final float[][] mCoordinates;
	private final float[] mSegmentsLength;
	private final float mTotalLength;

	public CachedPathIteratorFactory(@NonNull PathIterator iterator) {
	mWindingRule = iterator.getWindingRule();

	ArrayList<Integer> typesArray = Lists.newArrayList();
	ArrayList<float[]> pointsArray = Lists.newArrayList();
	float[] points = new float[6];
	while (!iterator.isDone()) {
	int type = iterator.currentSegment(points);
	int nPoints = getNumberOfPoints(type) * 2; // 2 coordinates per point

	typesArray.add(type);
	float[] itemPoints = new float[nPoints];
	System.arraycopy(points, 0, itemPoints, 0, nPoints);
	pointsArray.add(itemPoints);
	iterator.next();
	}

	mTypes = new int[typesArray.size()];
	mCoordinates = new float[mTypes.length][];
	for (int i = 0; i < typesArray.size(); i++) {
	mTypes[i] = typesArray.get(i);
	mCoordinates[i] = pointsArray.get(i);
	}

	// Do measurement
	mSegmentsLength = new float[mTypes.length];

	// Curves that we can reuse to estimate segments length
	CubicCurve2D.Float cubicCurve = new CubicCurve2D.Float();
	QuadCurve2D.Float quadCurve = new QuadCurve2D.Float();
	float lastX = 0;
	float lastY = 0;
	float totalLength = 0;
	for (int i = 0; i < mTypes.length; i++) {
	switch (mTypes[i]) {
	case PathIterator.SEG_CUBICTO:
	cubicCurve.setCurve(lastX, lastY,
	mCoordinates[i][0], mCoordinates[i][1], mCoordinates[i][2],
	mCoordinates[i][3], lastX = mCoordinates[i][4],
	lastY = mCoordinates[i][5]);
	mSegmentsLength[i] =
	getFlatPathLength(cubicCurve.getPathIterator(null, PRECISION));
	break;
	case PathIterator.SEG_QUADTO:
	quadCurve.setCurve(lastX, lastY, mCoordinates[i][0], mCoordinates[i][1],
	lastX = mCoordinates[i][2], lastY = mCoordinates[i][3]);
	mSegmentsLength[i] =
	getFlatPathLength(quadCurve.getPathIterator(null, PRECISION));
	break;
	case PathIterator.SEG_CLOSE:
	mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY,
	lastX = mCoordinates[0][0],
	lastY = mCoordinates[0][1]);
	mCoordinates[i] = new float[2];
	// We convert a SEG_CLOSE segment to a SEG_LINETO so we do not have to worry
	// about this special case in the rest of the code.
	mTypes[i] = PathIterator.SEG_LINETO;
	mCoordinates[i][0] = mCoordinates[0][0];
	mCoordinates[i][1] = mCoordinates[0][1];
	break;
	case PathIterator.SEG_MOVETO:
	mSegmentsLength[i] = 0;
	lastX = mCoordinates[i][0];
	lastY = mCoordinates[i][1];
	break;
	case PathIterator.SEG_LINETO:
	mSegmentsLength[i] = (float) Point2D.distance(lastX, lastY, mCoordinates[i][0],
	mCoordinates[i][1]);
	lastX = mCoordinates[i][0];
	lastY = mCoordinates[i][1];
	default:
	}
	totalLength += mSegmentsLength[i];
	}

	mTotalLength = totalLength;
	}

	private static void quadCurveSegment(float[] coords, float t0, float t1) {
	// Calculate X and Y at 0.5 (We'll use this to reconstruct the control point later)
	float mt = t0 + (t1 - t0) / 2;
	float mu = 1 - mt;
	float mx = mu * mu * coords[0] + 2 * mu * mt * coords[2] + mt * mt * coords[4];
	float my = mu * mu * coords[1] + 2 * mu * mt * coords[3] + mt * mt * coords[5];

	float u0 = 1 - t0;
	float u1 = 1 - t1;

	// coords at t0
	coords[0] = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
	coords[1] = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;

	// coords at t1
	coords[4] = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
	coords[5] = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;

	// estimated control point at t'=0.5
	coords[2] = 2 * mx - coords[0] / 2 - coords[4] / 2;
	coords[3] = 2 * my - coords[1] / 2 - coords[5] / 2;
	}

	private static void cubicCurveSegment(float[] coords, float t0, float t1) {
	// http://stackoverflow.com/questions/11703283/cubic-bezier-curve-segment
	float u0 = 1 - t0;
	float u1 = 1 - t1;

	// Calculate the points at t0 and t1 for the quadratic curves formed by (P0, P1, P2) and
	// (P1, P2, P3)
	float qxa = coords[0] * u0 * u0 + coords[2] * 2 * t0 * u0 + coords[4] * t0 * t0;
	float qxb = coords[0] * u1 * u1 + coords[2] * 2 * t1 * u1 + coords[4] * t1 * t1;
	float qxc = coords[2] * u0 * u0 + coords[4] * 2 * t0 * u0 + coords[6] * t0 * t0;
	float qxd = coords[2] * u1 * u1 + coords[4] * 2 * t1 * u1 + coords[6] * t1 * t1;

	float qya = coords[1] * u0 * u0 + coords[3] * 2 * t0 * u0 + coords[5] * t0 * t0;
	float qyb = coords[1] * u1 * u1 + coords[3] * 2 * t1 * u1 + coords[5] * t1 * t1;
	float qyc = coords[3] * u0 * u0 + coords[5] * 2 * t0 * u0 + coords[7] * t0 * t0;
	float qyd = coords[3] * u1 * u1 + coords[5] * 2 * t1 * u1 + coords[7] * t1 * t1;

	// Linear interpolation
	coords[0] = qxa * u0 + qxc * t0;
	coords[1] = qya * u0 + qyc * t0;

	coords[2] = qxa * u1 + qxc * t1;
	coords[3] = qya * u1 + qyc * t1;

	coords[4] = qxb * u0 + qxd * t0;
	coords[5] = qyb * u0 + qyd * t0;

	coords[6] = qxb * u1 + qxd * t1;
	coords[7] = qyb * u1 + qyd * t1;
	}

	/**
	* Returns the end point of a given segment
	*
	* @param type the segment type
	* @param coords the segment coordinates array
	* @param point the return array where the point will be stored
	*/
	private static void getShapeEndPoint(int type, @NonNull float[] coords, @NonNull float[]
	point) {
	// start index of the end point for the segment type
	int pointIndex = (getNumberOfPoints(type) - 1) * 2;
	point[0] = coords[pointIndex];
	point[1] = coords[pointIndex + 1];
	}

	/**
	* Returns the number of points stored in a coordinates array for the given segment type.
	*/
	private static int getNumberOfPoints(int segmentType) {
	switch (segmentType) {
	case PathIterator.SEG_QUADTO:
	return 2;
	case PathIterator.SEG_CUBICTO:
	return 3;
	case PathIterator.SEG_CLOSE:
	return 0;
	default:
	return 1;
	}
	}

	/**
	* Returns the estimated length of a flat path. If the passed path is not flat (i.e. contains a
	* segment that is not {@link PathIterator#SEG_CLOSE}, {@link PathIterator#SEG_MOVETO} or {@link
	* PathIterator#SEG_LINETO} this method will fail.
	*/
	private static float getFlatPathLength(@NonNull PathIterator iterator) {
	float segment[] = new float[6];
	float totalLength = 0;
	float[] previousPoint = new float[2];
	boolean isFirstPoint = true;

	while (!iterator.isDone()) {
	int type = iterator.currentSegment(segment);
	assert type == PathIterator.SEG_LINETO \|\| type == PathIterator.SEG_CLOSE \|\| type ==
	PathIterator.SEG_MOVETO;

	// MoveTo shouldn't affect the length
	if (!isFirstPoint && type != PathIterator.SEG_MOVETO) {
	totalLength += Point2D.distance(previousPoint[0], previousPoint[1], segment[0],
	segment[1]);
	} else {
	isFirstPoint = false;
	}
	previousPoint[0] = segment[0];
	previousPoint[1] = segment[1];
	iterator.next();
	}

	return totalLength;
	}

	/**
	* Returns the estimated position along a path of the given length.
	*/
	private void getPointAtLength(int type, @NonNull float[] coords, float lastX, float
	lastY, float t, @NonNull float[] point) {
	if (type == PathIterator.SEG_LINETO) {
	point[0] = lastX + (coords[0] - lastX) * t;
	point[1] = lastY + (coords[1] - lastY) * t;
	// Return here, since we do not need a shape to estimate
	return;
	}

	float[] curve = new float[8];
	int lastPointIndex = (getNumberOfPoints(type) - 1) * 2;

	System.arraycopy(coords, 0, curve, 2, coords.length);
	curve[0] = lastX;
	curve[1] = lastY;
	if (type == PathIterator.SEG_CUBICTO) {
	cubicCurveSegment(curve, 0f, t);
	} else {
	quadCurveSegment(curve, 0f, t);
	}

	point[0] = curve[2 + lastPointIndex];
	point[1] = curve[2 + lastPointIndex + 1];
	}

	public CachedPathIterator iterator() {
	return new CachedPathIterator();
	}

	/**
	* Class that allows us to iterate over a path multiple times
	*/
	public class CachedPathIterator implements PathIterator {
	private int mNextIndex;

	/**
	* Current segment type.
	*
	* @see PathIterator
	*/
	private int mCurrentType;

	/**
	* Stores the coordinates array of the current segment. The number of points stored depends
	* on the segment type.
	*
	* @see PathIterator
	*/
	private float[] mCurrentCoords = new float[6];
	private float mCurrentSegmentLength;

	/**
	* Current segment length offset. When asking for the length of the current segment, the
	* length will be reduced by this amount. This is useful when we are only using portions of
	* the segment.
	*
	* @see #jumpToSegment(float)
	*/
	private float mOffsetLength;

	/** Point where the current segment started */
	private float[] mLastPoint = new float[2];
	private boolean isIteratorDone;

	private CachedPathIterator() {
	next();
	}

	public float getCurrentSegmentLength() {
	return mCurrentSegmentLength;
	}

	@Override
	public int getWindingRule() {
	return mWindingRule;
	}

	@Override
	public boolean isDone() {
	return isIteratorDone;
	}

	@Override
	public void next() {
	if (mNextIndex >= mTypes.length) {
	isIteratorDone = true;
	return;
	}

	if (mNextIndex >= 1) {
	// We've already called next() once so there is a previous segment in this path.
	// We want to get the coordinates where the path ends.
	getShapeEndPoint(mCurrentType, mCurrentCoords, mLastPoint);
	} else {
	// This is the first segment, no previous point so initialize to 0, 0
	mLastPoint[0] = mLastPoint[1] = 0f;
	}
	mCurrentType = mTypes[mNextIndex];
	mCurrentSegmentLength = mSegmentsLength[mNextIndex] - mOffsetLength;

	if (mOffsetLength > 0f && (mCurrentType == SEG_CUBICTO \|\| mCurrentType == SEG_QUADTO)) {
	// We need to skip part of the start of the current segment (because
	// mOffsetLength > 0)
	float[] points = new float[8];

	if (mNextIndex < 1) {
	points[0] = points[1] = 0f;
	} else {
	getShapeEndPoint(mTypes[mNextIndex - 1], mCoordinates[mNextIndex - 1], points);
	}

	System.arraycopy(mCoordinates[mNextIndex], 0, points, 2,
	mCoordinates[mNextIndex].length);
	float t0 = (mSegmentsLength[mNextIndex] - mCurrentSegmentLength) /
	mSegmentsLength[mNextIndex];
	if (mCurrentType == SEG_CUBICTO) {
	cubicCurveSegment(points, t0, 1f);
	} else {
	quadCurveSegment(points, t0, 1f);
	}
	System.arraycopy(points, 2, mCurrentCoords, 0, mCoordinates[mNextIndex].length);
	} else {
	System.arraycopy(mCoordinates[mNextIndex], 0, mCurrentCoords, 0,
	mCoordinates[mNextIndex].length);
	}

	mOffsetLength = 0f;
	mNextIndex++;
	}

	@Override
	public int currentSegment(float[] coords) {
	System.arraycopy(mCurrentCoords, 0, coords, 0, getNumberOfPoints(mCurrentType) * 2);
	return mCurrentType;
	}

	@Override
	public int currentSegment(double[] coords) {
	throw new UnsupportedOperationException();
	}

	/**
	* Returns the point where the current segment ends
	*/
	public void getCurrentSegmentEnd(float[] point) {
	point[0] = mLastPoint[0];
	point[1] = mLastPoint[1];
	}

	/**
	* Restarts the iterator and jumps all the segments of this path up to the length value.
	*/
	public void jumpToSegment(float length) {
	isIteratorDone = false;
	if (length <= 0f) {
	mNextIndex = 0;
	return;
	}

	float accLength = 0;
	float lastPoint[] = new float[2];
	for (mNextIndex = 0; mNextIndex < mTypes.length; mNextIndex++) {
	float segmentLength = mSegmentsLength[mNextIndex];
	if (accLength + segmentLength >= length && mTypes[mNextIndex] != SEG_MOVETO) {
	float[] estimatedPoint = new float[2];
	getPointAtLength(mTypes[mNextIndex],
	mCoordinates[mNextIndex], lastPoint[0], lastPoint[1],
	(length - accLength) / segmentLength,
	estimatedPoint);

	// This segment makes us go further than length so we go back one step,
	// set a moveto and offset the length of the next segment by the length
	// of this segment that we've already used.
	mCurrentType = PathIterator.SEG_MOVETO;
	mCurrentCoords[0] = estimatedPoint[0];
	mCurrentCoords[1] = estimatedPoint[1];
	mCurrentSegmentLength = 0;

	// We need to offset next path length to account for the segment we've just
	// skipped.
	mOffsetLength = length - accLength;
	return;
	}
	accLength += segmentLength;
	getShapeEndPoint(mTypes[mNextIndex], mCoordinates[mNextIndex], lastPoint);
	}
	}

	/**
	* Returns the current segment up to certain length. If the current segment is shorter than
	* length, then the whole segment is returned. The segment coordinates are copied into the
	* coords array.
	*
	* @return the segment type
	*/
	public int currentSegment(@NonNull float[] coords, float length) {
	int type = currentSegment(coords);
	// If the length is greater than the current segment length, no need to find
	// the cut point. Same if this is a SEG_MOVETO.
	if (mCurrentSegmentLength <= length \|\| type == SEG_MOVETO) {
	return type;
	}

	float t = length / getCurrentSegmentLength();

	// We find at which offset the end point is located within the coords array and set
	// a new end point to cut the segment short
	switch (type) {
	case SEG_CUBICTO:
	case SEG_QUADTO:
	float[] curve = new float[8];
	curve[0] = mLastPoint[0];
	curve[1] = mLastPoint[1];
	System.arraycopy(coords, 0, curve, 2, coords.length);
	if (type == SEG_CUBICTO) {
	cubicCurveSegment(curve, 0f, t);
	} else {
	quadCurveSegment(curve, 0f, t);
	}
	System.arraycopy(curve, 2, coords, 0, coords.length);
	break;
	default:
	float[] point = new float[2];
	getPointAtLength(type, coords, mLastPoint[0], mLastPoint[1], t, point);
	coords[0] = point[0];
	coords[1] = point[1];
	}

	return type;
	}

	/**
	* Returns the total length of the path
	*/
	public float getTotalLength() {
	return mTotalLength;
	}
	}
	}