var LocMath = {
    // Resize vector to a unit vector
    unitVector: function(x)
    {
        var size = Math.sqrt(x[0] * x[0] + x[1] * x[1] + x[2] * x[2]);
        return x.map(function(a) { return a / size; });
    },

    // Dot product of two vectors
    dotProduct: function(x, y)
    {
        var sum = 0;
        for (i in x)
        {
            i = parseInt(i); if (isNaN(i)) { continue; }
            sum += x[i] * y[i];
        }
        return sum;
    },

    // Cross product of two vectors
    crossProduct: function(x, y)
    {
        return [x[1] * y[2] - x[2] * y[1],
                x[2] * y[0] - x[0] * y[2],
                x[0] * y[1] - x[1] * y[0]];
    },

    // Apply a coordinate transform, t, to a vector, v.
    coordinateTransform: function(t, v, inverse)
    {
        var result = [0, 0, 0];
        for (var i in t)
        {
            i = parseInt(i); if (isNaN(i)) { continue; }

            for (var j in t[i])
            {
                j = parseInt(j); if (isNaN(j)) { continue; }

                result[i] += (inverse ? t[j][i] : t[i][j]) * v[j];
            }
        }
        return result;
    },

    // Find the approximate up normal for the polygon based on ecef coordinates
    polygonUpNormal: function(ecef)
    {
        var vector = [0, 0, 0];
        for (var i in ecef)
        {
            i = parseInt(i); if (isNaN(i)) { continue; }

            var next = (i + 1) % ecef.length;
            var prev = (i - 1 + ecef.length) % ecef.length;
            vector[0] += ecef[i].y * (ecef[next].z - ecef[prev].z);
            vector[1] += ecef[i].z * (ecef[next].x - ecef[prev].x);
            vector[2] += ecef[i].x * (ecef[next].y - ecef[prev].y);
        }
        return LocMath.unitVector(vector);
    },

    // two dimensional area of a polygon (ignores the z value)
    polygonArea: function(xy)
    {
        var area = 0;
        for (var i in xy)
        {
            i = parseInt(i); if (isNaN(i)) { continue; }
            var next = (i + 1) % xy.length;
            area += xy[i][0] * xy[next][1] - xy[next][0] * xy[i][1];
        }
        return area / 2;
    },

    // Finds the centroid on the x-y plane and averages the z values.
    xyPolygonCentroid: function(points)
    {
        var area = LocMath.polygonArea(points);
        var xy_centroid = [0, 0, 0];
        for (var i in points)
        {
            i = parseInt(i); if (isNaN(i)) { continue; }

            var next = (i + 1) % points.length;
            var base = (points[i][0] * points[next][1]
                        - points[next][0] * points[i][1]);
            xy_centroid[0] += (points[i][0] + points[next][0]) * base;
            xy_centroid[1] += (points[i][1] + points[next][1]) * base;
            xy_centroid[2] += points[i][2];
        }
        xy_centroid[0] /= 6 * area;
        xy_centroid[1] /= 6 * area;
        xy_centroid[2] /= points.length;
        return xy_centroid;
    },

    // Find a special orthogonal transformation matrix that rotates
    // coordinates to a coordinate system that has a z-axis along the given
    // normal vector.
    planeOrient: function(normal)
    {
        var n = LocMath.unitVector(normal);
        if (n[2] == 1 || n[2] == -1) // Simple: identity matrix
        {
            return [[n[2], 0, 0], [0, n[2], 0], [0, 0, n[2]]];
        }
        if (n[1] == 1 || n[1] == -1) // z -> x, -x -> y, y -> z
        {
            return [[0, 0, n[1]], [-1 * n[1], 0, 0], [0, n[1], 0]];
        }
        if (n[0] == 1 || n[0] == -1) // y -> x, -z -> y, x -> z
        {
            return [[0, 0, n[0]], [-1 * n[0], 0, 0], [0, n[0], 0]];
        }

        // The first row of the transformation is selected based on the two
        // non-zero indices of the normal vector.
        var i = 0;
        var j = 1;
        if (n[0] == 0)
        {
            i = 1;
            j = 2;
        }
        else if (n[1] == 0)
        {
            j = 2;
        }

        var t1 = [0, 0, 0];
        t1[i] = 0 - n[j];
        t1[j] = n[i];
        t1 = LocMath.unitVector(t1);
        var t2 = LocMath.crossProduct(n, t1);
        return [t1, t2, n];
    },


    movePoint: function(pt, d, angle)
    {
	var ecef = pt.toEcefPoint();

        var pt_lat = pt.latitude * Math.PI / 180;
        var pt_lng = pt.longitude * Math.PI / 180;
        var cos_lat = Math.cos(pt_lat);
        var cos_lng = Math.cos(pt_lng);
        var sin_lat = Math.sin(pt_lat);
        var sin_lng = Math.sin(pt_lng);

	var v_up = [cos_lat * cos_lng, cos_lat * sin_lng, sin_lat];
        var v_north = [-1 * sin_lat * cos_lng, -1 * sin_lat * sin_lng, cos_lat];
	var v_east = LocMath.crossProduct(v_north, v_up);

	var d_east = d * Math.sin(angle);
	var d_north = d * Math.cos(angle);

	ecef.x += v_east[0] * d_east + v_north[0] * d_north;
	ecef.y += v_east[1] * d_east + v_north[1] * d_north;
	ecef.z += v_east[2] * d_east + v_north[2] * d_north;

	return ecef.toGeoPoint();
    },

    getRandomGenerator: function(seed)
    {
        if (seed)
        {
            var rand_current = seed & 0xffffffff;
            return function()
            {
                rand_current = (1103515245 * rand_current + 12345) & 0xffffffff;
                return rand_current / 0xffffffff;
            };
        }
        return Math.random;
    },

    fuzzPoint: function(pt, size, seed)
    {
        var rand = LocMath.getRandomGenerator(seed);

        var angle = rand() * 2 * Math.PI;
        var distance = size * (1 - Math.abs(rand() + rand() - 1));
        var moved = LocMath.movePoint(pt, distance, angle);
        if (! pt.altitude)
        {
            moved.altitude = 0;
        }
        return moved;
    }
}