import ArcType from "./ArcType.js";
import arrayRemoveDuplicates from "./arrayRemoveDuplicates.js";
import Cartesian2 from "./Cartesian2.js";
import Cartesian3 from "./Cartesian3.js";
import Cartographic from "./Cartographic.js";
import ComponentDatatype from "./ComponentDatatype.js";
import defaultValue from "./defaultValue.js";
import defined from "./defined.js";
import Ellipsoid from "./Ellipsoid.js";
import EllipsoidRhumbLine from "./EllipsoidRhumbLine.js";
import Geometry from "./Geometry.js";
import GeometryAttribute from "./GeometryAttribute.js";
import GeometryAttributes from "./GeometryAttributes.js";
import GeometryPipeline from "./GeometryPipeline.js";
import IndexDatatype from "./IndexDatatype.js";
import CesiumMath from "./Math.js";
import Matrix3 from "./Matrix3.js";
import PolygonPipeline from "./PolygonPipeline.js";
import PrimitiveType from "./PrimitiveType.js";
import Quaternion from "./Quaternion.js";
import Queue from "./Queue.js";
import WindingOrder from "./WindingOrder.js";

/**
 * @private
 */
var PolygonGeometryLibrary = {};

PolygonGeometryLibrary.computeHierarchyPackedLength = function (
  polygonHierarchy
) {
  var numComponents = 0;
  var stack = [polygonHierarchy];
  while (stack.length > 0) {
    var hierarchy = stack.pop();
    if (!defined(hierarchy)) {
      continue;
    }

    numComponents += 2;

    var positions = hierarchy.positions;
    var holes = hierarchy.holes;

    if (defined(positions)) {
      numComponents += positions.length * Cartesian3.packedLength;
    }

    if (defined(holes)) {
      var length = holes.length;
      for (var i = 0; i < length; ++i) {
        stack.push(holes[i]);
      }
    }
  }

  return numComponents;
};

PolygonGeometryLibrary.packPolygonHierarchy = function (
  polygonHierarchy,
  array,
  startingIndex
) {
  var stack = [polygonHierarchy];
  while (stack.length > 0) {
    var hierarchy = stack.pop();
    if (!defined(hierarchy)) {
      continue;
    }

    var positions = hierarchy.positions;
    var holes = hierarchy.holes;

    array[startingIndex++] = defined(positions) ? positions.length : 0;
    array[startingIndex++] = defined(holes) ? holes.length : 0;

    if (defined(positions)) {
      var positionsLength = positions.length;
      for (var i = 0; i < positionsLength; ++i, startingIndex += 3) {
        Cartesian3.pack(positions[i], array, startingIndex);
      }
    }

    if (defined(holes)) {
      var holesLength = holes.length;
      for (var j = 0; j < holesLength; ++j) {
        stack.push(holes[j]);
      }
    }
  }

  return startingIndex;
};

PolygonGeometryLibrary.unpackPolygonHierarchy = function (
  array,
  startingIndex
) {
  var positionsLength = array[startingIndex++];
  var holesLength = array[startingIndex++];

  var positions = new Array(positionsLength);
  var holes = holesLength > 0 ? new Array(holesLength) : undefined;

  for (
    var i = 0;
    i < positionsLength;
    ++i, startingIndex += Cartesian3.packedLength
  ) {
    positions[i] = Cartesian3.unpack(array, startingIndex);
  }

  for (var j = 0; j < holesLength; ++j) {
    holes[j] = PolygonGeometryLibrary.unpackPolygonHierarchy(
      array,
      startingIndex
    );
    startingIndex = holes[j].startingIndex;
    delete holes[j].startingIndex;
  }

  return {
    positions: positions,
    holes: holes,
    startingIndex: startingIndex,
  };
};

var distanceScratch = new Cartesian3();
function getPointAtDistance(p0, p1, distance, length) {
  Cartesian3.subtract(p1, p0, distanceScratch);
  Cartesian3.multiplyByScalar(
    distanceScratch,
    distance / length,
    distanceScratch
  );
  Cartesian3.add(p0, distanceScratch, distanceScratch);
  return [distanceScratch.x, distanceScratch.y, distanceScratch.z];
}

PolygonGeometryLibrary.subdivideLineCount = function (p0, p1, minDistance) {
  var distance = Cartesian3.distance(p0, p1);
  var n = distance / minDistance;
  var countDivide = Math.max(0, Math.ceil(CesiumMath.log2(n)));
  return Math.pow(2, countDivide);
};

var scratchCartographic0 = new Cartographic();
var scratchCartographic1 = new Cartographic();
var scratchCartographic2 = new Cartographic();
var scratchCartesian0 = new Cartesian3();
PolygonGeometryLibrary.subdivideRhumbLineCount = function (
  ellipsoid,
  p0,
  p1,
  minDistance
) {
  var c0 = ellipsoid.cartesianToCartographic(p0, scratchCartographic0);
  var c1 = ellipsoid.cartesianToCartographic(p1, scratchCartographic1);
  var rhumb = new EllipsoidRhumbLine(c0, c1, ellipsoid);
  var n = rhumb.surfaceDistance / minDistance;
  var countDivide = Math.max(0, Math.ceil(CesiumMath.log2(n)));
  return Math.pow(2, countDivide);
};

PolygonGeometryLibrary.subdivideLine = function (p0, p1, minDistance, result) {
  var numVertices = PolygonGeometryLibrary.subdivideLineCount(
    p0,
    p1,
    minDistance
  );
  var length = Cartesian3.distance(p0, p1);
  var distanceBetweenVertices = length / numVertices;

  if (!defined(result)) {
    result = [];
  }

  var positions = result;
  positions.length = numVertices * 3;

  var index = 0;
  for (var i = 0; i < numVertices; i++) {
    var p = getPointAtDistance(p0, p1, i * distanceBetweenVertices, length);
    positions[index++] = p[0];
    positions[index++] = p[1];
    positions[index++] = p[2];
  }

  return positions;
};

PolygonGeometryLibrary.subdivideRhumbLine = function (
  ellipsoid,
  p0,
  p1,
  minDistance,
  result
) {
  var c0 = ellipsoid.cartesianToCartographic(p0, scratchCartographic0);
  var c1 = ellipsoid.cartesianToCartographic(p1, scratchCartographic1);
  var rhumb = new EllipsoidRhumbLine(c0, c1, ellipsoid);

  var n = rhumb.surfaceDistance / minDistance;
  var countDivide = Math.max(0, Math.ceil(CesiumMath.log2(n)));
  var numVertices = Math.pow(2, countDivide);
  var distanceBetweenVertices = rhumb.surfaceDistance / numVertices;

  if (!defined(result)) {
    result = [];
  }

  var positions = result;
  positions.length = numVertices * 3;

  var index = 0;
  for (var i = 0; i < numVertices; i++) {
    var c = rhumb.interpolateUsingSurfaceDistance(
      i * distanceBetweenVertices,
      scratchCartographic2
    );
    var p = ellipsoid.cartographicToCartesian(c, scratchCartesian0);
    positions[index++] = p.x;
    positions[index++] = p.y;
    positions[index++] = p.z;
  }

  return positions;
};

var scaleToGeodeticHeightN1 = new Cartesian3();
var scaleToGeodeticHeightN2 = new Cartesian3();
var scaleToGeodeticHeightP1 = new Cartesian3();
var scaleToGeodeticHeightP2 = new Cartesian3();

PolygonGeometryLibrary.scaleToGeodeticHeightExtruded = function (
  geometry,
  maxHeight,
  minHeight,
  ellipsoid,
  perPositionHeight
) {
  ellipsoid = defaultValue(ellipsoid, Ellipsoid.WGS84);

  var n1 = scaleToGeodeticHeightN1;
  var n2 = scaleToGeodeticHeightN2;
  var p = scaleToGeodeticHeightP1;
  var p2 = scaleToGeodeticHeightP2;

  if (
    defined(geometry) &&
    defined(geometry.attributes) &&
    defined(geometry.attributes.position)
  ) {
    var positions = geometry.attributes.position.values;
    var length = positions.length / 2;

    for (var i = 0; i < length; i += 3) {
      Cartesian3.fromArray(positions, i, p);

      ellipsoid.geodeticSurfaceNormal(p, n1);
      p2 = ellipsoid.scaleToGeodeticSurface(p, p2);
      n2 = Cartesian3.multiplyByScalar(n1, minHeight, n2);
      n2 = Cartesian3.add(p2, n2, n2);
      positions[i + length] = n2.x;
      positions[i + 1 + length] = n2.y;
      positions[i + 2 + length] = n2.z;

      if (perPositionHeight) {
        p2 = Cartesian3.clone(p, p2);
      }
      n2 = Cartesian3.multiplyByScalar(n1, maxHeight, n2);
      n2 = Cartesian3.add(p2, n2, n2);
      positions[i] = n2.x;
      positions[i + 1] = n2.y;
      positions[i + 2] = n2.z;
    }
  }
  return geometry;
};

PolygonGeometryLibrary.polygonOutlinesFromHierarchy = function (
  polygonHierarchy,
  scaleToEllipsoidSurface,
  ellipsoid
) {
  // create from a polygon hierarchy
  // Algorithm adapted from http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
  var polygons = [];
  var queue = new Queue();
  queue.enqueue(polygonHierarchy);
  var i;
  var j;
  var length;
  while (queue.length !== 0) {
    var outerNode = queue.dequeue();
    var outerRing = outerNode.positions;
    if (scaleToEllipsoidSurface) {
      length = outerRing.length;
      for (i = 0; i < length; i++) {
        ellipsoid.scaleToGeodeticSurface(outerRing[i], outerRing[i]);
      }
    }
    outerRing = arrayRemoveDuplicates(
      outerRing,
      Cartesian3.equalsEpsilon,
      true
    );
    if (outerRing.length < 3) {
      continue;
    }

    var numChildren = outerNode.holes ? outerNode.holes.length : 0;
    // The outer polygon contains inner polygons
    for (i = 0; i < numChildren; i++) {
      var hole = outerNode.holes[i];
      var holePositions = hole.positions;
      if (scaleToEllipsoidSurface) {
        length = holePositions.length;
        for (j = 0; j < length; ++j) {
          ellipsoid.scaleToGeodeticSurface(holePositions[j], holePositions[j]);
        }
      }
      holePositions = arrayRemoveDuplicates(
        holePositions,
        Cartesian3.equalsEpsilon,
        true
      );
      if (holePositions.length < 3) {
        continue;
      }
      polygons.push(holePositions);

      var numGrandchildren = 0;
      if (defined(hole.holes)) {
        numGrandchildren = hole.holes.length;
      }

      for (j = 0; j < numGrandchildren; j++) {
        queue.enqueue(hole.holes[j]);
      }
    }

    polygons.push(outerRing);
  }

  return polygons;
};

PolygonGeometryLibrary.polygonsFromHierarchy = function (
  polygonHierarchy,
  projectPointsTo2D,
  scaleToEllipsoidSurface,
  ellipsoid
) {
  // create from a polygon hierarchy
  // Algorithm adapted from http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
  var hierarchy = [];
  var polygons = [];

  var queue = new Queue();
  queue.enqueue(polygonHierarchy);

  while (queue.length !== 0) {
    var outerNode = queue.dequeue();
    var outerRing = outerNode.positions;
    var holes = outerNode.holes;

    var i;
    var length;
    if (scaleToEllipsoidSurface) {
      length = outerRing.length;
      for (i = 0; i < length; i++) {
        ellipsoid.scaleToGeodeticSurface(outerRing[i], outerRing[i]);
      }
    }

    outerRing = arrayRemoveDuplicates(
      outerRing,
      Cartesian3.equalsEpsilon,
      true
    );
    if (outerRing.length < 3) {
      continue;
    }

    var positions2D = projectPointsTo2D(outerRing);
    if (!defined(positions2D)) {
      continue;
    }
    var holeIndices = [];

    var originalWindingOrder = PolygonPipeline.computeWindingOrder2D(
      positions2D
    );
    if (originalWindingOrder === WindingOrder.CLOCKWISE) {
      positions2D.reverse();
      outerRing = outerRing.slice().reverse();
    }

    var positions = outerRing.slice();
    var numChildren = defined(holes) ? holes.length : 0;
    var polygonHoles = [];
    var j;

    for (i = 0; i < numChildren; i++) {
      var hole = holes[i];
      var holePositions = hole.positions;
      if (scaleToEllipsoidSurface) {
        length = holePositions.length;
        for (j = 0; j < length; ++j) {
          ellipsoid.scaleToGeodeticSurface(holePositions[j], holePositions[j]);
        }
      }

      holePositions = arrayRemoveDuplicates(
        holePositions,
        Cartesian3.equalsEpsilon,
        true
      );
      if (holePositions.length < 3) {
        continue;
      }

      var holePositions2D = projectPointsTo2D(holePositions);
      if (!defined(holePositions2D)) {
        continue;
      }

      originalWindingOrder = PolygonPipeline.computeWindingOrder2D(
        holePositions2D
      );
      if (originalWindingOrder === WindingOrder.CLOCKWISE) {
        holePositions2D.reverse();
        holePositions = holePositions.slice().reverse();
      }

      polygonHoles.push(holePositions);
      holeIndices.push(positions.length);
      positions = positions.concat(holePositions);
      positions2D = positions2D.concat(holePositions2D);

      var numGrandchildren = 0;
      if (defined(hole.holes)) {
        numGrandchildren = hole.holes.length;
      }

      for (j = 0; j < numGrandchildren; j++) {
        queue.enqueue(hole.holes[j]);
      }
    }

    hierarchy.push({
      outerRing: outerRing,
      holes: polygonHoles,
    });
    polygons.push({
      positions: positions,
      positions2D: positions2D,
      holes: holeIndices,
    });
  }

  return {
    hierarchy: hierarchy,
    polygons: polygons,
  };
};

var computeBoundingRectangleCartesian2 = new Cartesian2();
var computeBoundingRectangleCartesian3 = new Cartesian3();
var computeBoundingRectangleQuaternion = new Quaternion();
var computeBoundingRectangleMatrix3 = new Matrix3();
PolygonGeometryLibrary.computeBoundingRectangle = function (
  planeNormal,
  projectPointTo2D,
  positions,
  angle,
  result
) {
  var rotation = Quaternion.fromAxisAngle(
    planeNormal,
    angle,
    computeBoundingRectangleQuaternion
  );
  var textureMatrix = Matrix3.fromQuaternion(
    rotation,
    computeBoundingRectangleMatrix3
  );

  var minX = Number.POSITIVE_INFINITY;
  var maxX = Number.NEGATIVE_INFINITY;
  var minY = Number.POSITIVE_INFINITY;
  var maxY = Number.NEGATIVE_INFINITY;

  var length = positions.length;
  for (var i = 0; i < length; ++i) {
    var p = Cartesian3.clone(positions[i], computeBoundingRectangleCartesian3);
    Matrix3.multiplyByVector(textureMatrix, p, p);
    var st = projectPointTo2D(p, computeBoundingRectangleCartesian2);

    if (defined(st)) {
      minX = Math.min(minX, st.x);
      maxX = Math.max(maxX, st.x);

      minY = Math.min(minY, st.y);
      maxY = Math.max(maxY, st.y);
    }
  }

  result.x = minX;
  result.y = minY;
  result.width = maxX - minX;
  result.height = maxY - minY;
  return result;
};

PolygonGeometryLibrary.createGeometryFromPositions = function (
  ellipsoid,
  polygon,
  granularity,
  perPositionHeight,
  vertexFormat,
  arcType
) {
  var indices = PolygonPipeline.triangulate(polygon.positions2D, polygon.holes);

  /* If polygon is completely unrenderable, just use the first three vertices */
  if (indices.length < 3) {
    indices = [0, 1, 2];
  }

  var positions = polygon.positions;

  if (perPositionHeight) {
    var length = positions.length;
    var flattenedPositions = new Array(length * 3);
    var index = 0;
    for (var i = 0; i < length; i++) {
      var p = positions[i];
      flattenedPositions[index++] = p.x;
      flattenedPositions[index++] = p.y;
      flattenedPositions[index++] = p.z;
    }
    var geometry = new Geometry({
      attributes: {
        position: new GeometryAttribute({
          componentDatatype: ComponentDatatype.DOUBLE,
          componentsPerAttribute: 3,
          values: flattenedPositions,
        }),
      },
      indices: indices,
      primitiveType: PrimitiveType.TRIANGLES,
    });

    if (vertexFormat.normal) {
      return GeometryPipeline.computeNormal(geometry);
    }

    return geometry;
  }

  if (arcType === ArcType.GEODESIC) {
    return PolygonPipeline.computeSubdivision(
      ellipsoid,
      positions,
      indices,
      granularity
    );
  } else if (arcType === ArcType.RHUMB) {
    return PolygonPipeline.computeRhumbLineSubdivision(
      ellipsoid,
      positions,
      indices,
      granularity
    );
  }
};

var computeWallIndicesSubdivided = [];
var p1Scratch = new Cartesian3();
var p2Scratch = new Cartesian3();

PolygonGeometryLibrary.computeWallGeometry = function (
  positions,
  ellipsoid,
  granularity,
  perPositionHeight,
  arcType
) {
  var edgePositions;
  var topEdgeLength;
  var i;
  var p1;
  var p2;

  var length = positions.length;
  var index = 0;

  if (!perPositionHeight) {
    var minDistance = CesiumMath.chordLength(
      granularity,
      ellipsoid.maximumRadius
    );

    var numVertices = 0;
    if (arcType === ArcType.GEODESIC) {
      for (i = 0; i < length; i++) {
        numVertices += PolygonGeometryLibrary.subdivideLineCount(
          positions[i],
          positions[(i + 1) % length],
          minDistance
        );
      }
    } else if (arcType === ArcType.RHUMB) {
      for (i = 0; i < length; i++) {
        numVertices += PolygonGeometryLibrary.subdivideRhumbLineCount(
          ellipsoid,
          positions[i],
          positions[(i + 1) % length],
          minDistance
        );
      }
    }

    topEdgeLength = (numVertices + length) * 3;
    edgePositions = new Array(topEdgeLength * 2);
    for (i = 0; i < length; i++) {
      p1 = positions[i];
      p2 = positions[(i + 1) % length];

      var tempPositions;
      if (arcType === ArcType.GEODESIC) {
        tempPositions = PolygonGeometryLibrary.subdivideLine(
          p1,
          p2,
          minDistance,
          computeWallIndicesSubdivided
        );
      } else if (arcType === ArcType.RHUMB) {
        tempPositions = PolygonGeometryLibrary.subdivideRhumbLine(
          ellipsoid,
          p1,
          p2,
          minDistance,
          computeWallIndicesSubdivided
        );
      }
      var tempPositionsLength = tempPositions.length;
      for (var j = 0; j < tempPositionsLength; ++j, ++index) {
        edgePositions[index] = tempPositions[j];
        edgePositions[index + topEdgeLength] = tempPositions[j];
      }

      edgePositions[index] = p2.x;
      edgePositions[index + topEdgeLength] = p2.x;
      ++index;

      edgePositions[index] = p2.y;
      edgePositions[index + topEdgeLength] = p2.y;
      ++index;

      edgePositions[index] = p2.z;
      edgePositions[index + topEdgeLength] = p2.z;
      ++index;
    }
  } else {
    topEdgeLength = length * 3 * 2;
    edgePositions = new Array(topEdgeLength * 2);
    for (i = 0; i < length; i++) {
      p1 = positions[i];
      p2 = positions[(i + 1) % length];
      edgePositions[index] = edgePositions[index + topEdgeLength] = p1.x;
      ++index;
      edgePositions[index] = edgePositions[index + topEdgeLength] = p1.y;
      ++index;
      edgePositions[index] = edgePositions[index + topEdgeLength] = p1.z;
      ++index;
      edgePositions[index] = edgePositions[index + topEdgeLength] = p2.x;
      ++index;
      edgePositions[index] = edgePositions[index + topEdgeLength] = p2.y;
      ++index;
      edgePositions[index] = edgePositions[index + topEdgeLength] = p2.z;
      ++index;
    }
  }

  length = edgePositions.length;
  var indices = IndexDatatype.createTypedArray(
    length / 3,
    length - positions.length * 6
  );
  var edgeIndex = 0;
  length /= 6;

  for (i = 0; i < length; i++) {
    var UL = i;
    var UR = UL + 1;
    var LL = UL + length;
    var LR = LL + 1;

    p1 = Cartesian3.fromArray(edgePositions, UL * 3, p1Scratch);
    p2 = Cartesian3.fromArray(edgePositions, UR * 3, p2Scratch);
    if (
      Cartesian3.equalsEpsilon(
        p1,
        p2,
        CesiumMath.EPSILON10,
        CesiumMath.EPSILON10
      )
    ) {
      //skip corner
      continue;
    }

    indices[edgeIndex++] = UL;
    indices[edgeIndex++] = LL;
    indices[edgeIndex++] = UR;
    indices[edgeIndex++] = UR;
    indices[edgeIndex++] = LL;
    indices[edgeIndex++] = LR;
  }

  return new Geometry({
    attributes: new GeometryAttributes({
      position: new GeometryAttribute({
        componentDatatype: ComponentDatatype.DOUBLE,
        componentsPerAttribute: 3,
        values: edgePositions,
      }),
    }),
    indices: indices,
    primitiveType: PrimitiveType.TRIANGLES,
  });
};
export default PolygonGeometryLibrary;