#region Written by Tamas Budavari (budavari@jhu.edu)
/**
 * SphericalLib.OutlineRandom
 * 
 * SphericalLib is a .NET library to deal with geometry on the unit sphere.
 * It is intented to be used for complex survey footprint descriptions in
 * standalone applications as well as in web services and perhaps Yukon.
 * 
 * Written by Tamas Budavari (budavari@jhu.edu)
 * See bottom of file for revision history
 * 
 * Current revision:
 *   ID:          $Id: OutlineRandom.cs,v 1.1.1.1 2006/11/14 02:56:34 gupchup Exp $
 *   Revision:    $Revision: 1.1.1.1 $
 *   Date:        $Date: 2006/11/14 02:56:34 $
 */
using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Collections.ObjectModel;
using System.Text;
#endregion

using Spherical;

namespace USA
{
    /// <summary>
    /// Class represents a "free-hand" outline of a region
    /// </summary>
    public class OutlineRandom
    {
        #region Private members ...

        private ReadOnlyCollection<Cartesian> points;
        private List<RingInterval> ranges;
        private Random random;

        #endregion
        #region Constructors ...

        /// <summary>
        /// Create outline by forming arcs
        /// </summary>
        /// <param name="points"></param>
        public OutlineRandom(ReadOnlyCollection<Cartesian> pts)
        {
            if (pts.Count < 3)
                throw new ArgumentException("OutlineRandom.ctor(): # of points is < 3");

            points = pts;
            ranges = new List<RingInterval>();
            random = new Random();
        }

        #endregion
        #region Create Region ...

        public double RandomTriangle(int maxiter, out int[] index, out Convex convex)
        {
            RingInterval rival = new RingInterval(0, this.points.Count);
            Cartesian[] pts = new Cartesian[3];
            index = new int[0];
            bool done = false;
            int iter;
            convex = new Convex();
            for (iter = 0; iter < maxiter; iter++)
            {
                index = rival.RandomIndexSortedArray(this.random, 3);
                for (int i = 0; i < index.Length; i++)
                    pts[i] = this.points[index[i]];

                Arc[] arcs = new Arc[3];
                arcs[0] = new Arc(pts[0], pts[1]);
                arcs[1] = new Arc(pts[1], pts[2]);
                arcs[2] = new Arc(pts[2], pts[0]);
                Patch p = new Patch(arcs);
                List<Patch> pl = new List<Patch>(1);
                pl.Add(p);
                convex = new Convex(3);
                convex.Add(arcs[0].Circle);
                convex.Add(arcs[1].Circle);
                convex.Add(arcs[2].Circle);
                int numin = convex.CoversHowMany(this.points, 0);
                //Console.Out.WriteLine("numin: {0}", numin);
                if (numin <= 3)
                {
                    done = true;
                    convex.SetPatches(pl);
                    convex.SetArea(Cartesian.GirardArea(pts[0], pts[1], pts[2]));
                    break;
                }
            }
            if (!done) throw new ApplicationException
                    ("OutlineRandom.RandomTriangle(): reached maxiter - not done!");
            //Console.Out.WriteLine("Iter: {0}", iter);
            return convex.Area.Value;
        }

        public double RandomSplit(RingInterval rival, int maxiter, out int index, out Convex convex)
        {
            Cartesian[] pts = new Cartesian[3];
            pts[0] = this.points[(rival.start - 1 + this.points.Count) % this.points.Count];
            pts[1] = this.points[rival.stop];
            index = -1;
            bool done = false;
            int iter;
            convex = new Convex();
            for (iter = 0; iter < maxiter; iter++)
            {
                index = rival.RandomIndex(this.random);
                pts[2] = this.points[index];

                Arc[] arcs = new Arc[3];
                arcs[0] = new Arc(pts[0], pts[1]);
                arcs[1] = new Arc(pts[1], pts[2]);
                arcs[2] = new Arc(pts[2], pts[0]);
                Patch p = new Patch(arcs);
                List<Patch> pl = new List<Patch>(1);
                pl.Add(p);
                convex = new Convex(3);
                convex.Add(arcs[0].Circle);
                convex.Add(arcs[1].Circle);
                convex.Add(arcs[2].Circle);
                int numin = convex.CoversHowMany(this.points, 0);
                //Console.Out.WriteLine("numin: {0}", numin);
                if (numin <= 3)
                {
                    done = true;
                    convex.SetPatches(pl);
                    convex.SetArea(Cartesian.GirardArea(pts[0], pts[1], pts[2]));
                    break;
                }
            }
            if (!done) throw new ApplicationException
                    ("OutlineRandom.RandomSplit(): reached maxiter - not done!");
            //Console.Out.WriteLine("Iter: {0}", iter);
            return convex.Area.Value;
        }

        /// <summary>
        /// Make a region from outline
        /// </summary>
        /// <returns></returns>
        public Region Region(int maxdepth, int maxtry, int maxiter)
        {
            Region region = new Region(maxdepth);

            // first triangle is the biggest out of maxtry trials
            Convex convex = new Convex();
            int[] index = new int[0];
            double maxarea = 0;
            for (int t = 0; t < maxtry; t++)
            {
                int[] idx;
                Convex k;
                double area = this.RandomTriangle(maxiter, out idx, out k);
                if (area > maxarea)
                {
                    index = idx;
                    convex = k;
                    maxarea = area;
                    //Console.Out.WriteLine("Area: {0}", area);
                }
            }
            Console.Out.WriteLine("Max Area: {0}", convex.Area);
            
            // save convex and set ranges
            region.Add(convex);
            this.ranges.Add(new RingInterval(index[0]+1, index[1]));
            this.ranges.Add(new RingInterval(index[1]+1, index[2])); 
            this.ranges.Add(new RingInterval(index[2]+1, index[0], this.points.Count));
            this.ranges.Sort(RingInterval.ComparisonLengthDescending);
            //foreach (RingInterval r in this.ranges) Console.Out.WriteLine(r);

            for (int depth = 1; depth < maxdepth; depth++)
            {
                RingInterval longest = this.ranges[0];
                maxarea = 0;
                int split = -1;
                for (int t = 0; t < maxtry; t++)
                {
                    int idx;
                    Convex k;
                    double area = this.RandomSplit(longest, maxiter, out idx, out k);
                    if (area > maxarea)
                    {
                        convex = k;
                        split = idx;
                        maxarea = area;
                    }
                }
                Console.Out.WriteLine("Max area: {0}", convex.Area);
                region.Add(convex);
                this.ranges.RemoveAt(0);
                this.ranges.Add(new RingInterval(longest.start, split, this.points.Count));
                this.ranges.Add(new RingInterval(split + 1, longest.stop, this.points.Count));
                this.ranges.Sort(RingInterval.ComparisonLengthDescending);
            }

            return region;
        }

        #endregion
    }
}

#region Revision History
/* Revision History

        $Log: OutlineRandom.cs,v $
        Revision 1.1.1.1  2006/11/14 02:56:34  gupchup
        no message

        Revision 1.1  2006/04/03 16:02:58  budavari
        project created

        Revision 1.5  2006/03/09 20:30:07  budavari
        Equality checks for value types

        Revision 1.4  2006/03/08 20:55:49  budavari
        Output region is simplified 'by hand' for speed

        Revision 1.3  2006/03/01 20:37:07  budavari
        Outline works w/o tangent plane projection - holes also!

        Revision 1.2  2006/02/28 16:25:47  budavari
        Major revision: no projection needed

        Revision 1.1  2006/01/24 15:56:05  budavari
        Re-structured directory layout to accommodate more projects

        Revision 1.3  2005/12/06 03:21:24  budavari
        Included Alex's worst case outline scenario: Samples.Greek()
        And it works!!! Hurray! Hurray! Hurray! [slowly fading...]

        Revision 1.2  2005/12/05 21:43:55  budavari
        Working Outline implementation :-) Hurray! Except for the fly in the soup:
        I did find an example, Samples.Saw3(), which makes the code throw up as
        it turns the outline into a bowtie. Coming up next...

        Revision 1.1  2005/12/04 16:50:55  budavari
        Small features and fixes. Also added Outline class - not function, yet

*/
#endregion