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;