#region Written by Tamas Budavari (budavari@jhu.edu)
/**
 * SphericalLib.Outline
 * 
 * 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@pha.jhu.edu)
 * See bottom of file for revision history
 * 
 * Current revision:
 *   ID:          $Id: Outline.cs,v 1.1.1.1 2006/11/14 02:56:39 gupchup Exp $
 *   Revision:    $Revision: 1.1.1.1 $
 *   Date:        $Date: 2006/11/14 02:56:39 $
 */
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;
#endregion

namespace Spherical.IO
{
    /// <summary>
    /// Class represents a "free-hand" outline of a region
    /// </summary>
    [CLSCompliant(true)]
    public class Outline
    {
        #region Private members ...

        private List<Cartesian> points;
        private List<Arc> arcList;
        private List<bool> concave;

        #endregion
        #region Public properties ...

        //public ReadOnlyCollection<Arc> ArcList
        //{
        //    get { return arcList.AsReadOnly(); }
        //}

        #endregion
        #region Constructors ...

        /// <summary>
        /// Create outline by forming arcs
        /// </summary>
        /// <param name="points"></param>
        public Outline(List<Cartesian> pts)
        {
            double tolerance = Const.Tolerance;

            // clone list of points
            points = new List<Cartesian>(pts);

            if (points.Count < 3)
                throw new ArgumentException("Outline.ctor(): # of points is < 3");

            // Arcs from the points and which convex
            arcList = new List<Arc>(points.Count);
            concave = new List<bool>(points.Count);
            int im, ip;
            for (int i = 0; i < points.Count; i++)
            {
                im = (i - 1 + points.Count) % points.Count;
                ip = (i + 1) % points.Count;

                Cartesian m = points[im];
                Cartesian c = points[i];
                Cartesian p = points[ip];
                concave.Add(Outline.IsConcave(m, c, p, tolerance));
                arcList.Add(new Arc(c, p));
 
            }

            // todo: check for bowtie if requested?
        }

        #endregion
        #region Test if vertex is concave ...

        /// <summary>
        /// Check if vertex is concave
        /// </summary>
        /// <param name="m"></param>
        /// <param name="c"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        public static bool IsConcave(Cartesian m, Cartesian c, Cartesian p, double tolerance)
        {
            Halfspace h = new Halfspace(m.Cross(c, true), 0);
            if (h.Covers(p, tolerance))
                return false;
            else
                return true;
        }

        #endregion
        #region Create inside convex ...

        /// <summary>
        /// Get one convex and update self. Return null if nothing left but hole (if any)
        /// </summary>
        /// <returns></returns>
        private Convex ConvexInside(double tolerance)
        {
            if (this.arcList.Count < 3) return null;

            // create new convex
            Convex convex = new Convex();
            List<Arc> arcs = new List<Arc>();

            // 
            // 1) pick arc with convex end point and concave start point
            //
            List<int> taken = new List<int>(arcList.Count);
            int start = -1; 
            for (int i = 1; i < arcList.Count; i++)
            {
                if (!concave[i] && concave[i-1])
                {
                    start = i - 1;
                    Arc a = arcList[start];
                    convex.Add(a.Circle);
                    arcs.Add(new Arc(a));
                    taken.Add(start);
                    break;
                }
            }
            //
            // 1b) or just convex end point?
            //
            if (start == -1)
            {
                for (int i = 1; i < arcList.Count; i++)
                {
                    if (!concave[i])
                    {
                        start = i - 1;
                        Arc a = arcList[start];
                        convex.Add(a.Circle);
                        arcs.Add(new Arc(a));
                        taken.Add(start);
                        break;
                    }
                }
            }
            // if nothing found -> only hole left
            if (start == -1) return null; 

            // 
            // 2) go till concave arc or the end and claim arcs
            //
            int E = -1; // end index of taken arc list
            for (int j = 1; j < arcList.Count; j++)
            {
                int i = (start + j) % arcList.Count; // current index
                Arc a = arcList[i];
                if (concave[i] || !convex.Covers(a.Point2, tolerance))
                {
                    E = i;
                    break;
                }
                convex.Add(a.Circle);
                arcs.Add(new Arc(a));
                taken.Add(i);
            }
            if (E == -1) 
                E = (start - 1 + arcList.Count) % arcList.Count;
            
            // 
            // 3) Remove arcs from the beginning of the 'taken' list 
            //    that are not covered by convex
            List<int> notTaken = new List<int>(taken.Count);
            int S = -1;
            foreach (int i in taken)
            {
                Arc a = arcList[i];
                //if (arcList[i].EndpointsCoveredByConvex(convex))
                if (convex.Covers(a.Point1, tolerance) && convex.Covers(a.Point2, tolerance))
                {
                    S = i;
                    break;
                }
                notTaken.Add(i);
            }
            if (S == -1)
            {
                throw new ApplicationException
                    ("Outline.ConvexInside(): no start point? should not happen");
            }
            // 
            // 4) Remove redundant halfspaces from convex
            // 
            convex.RemoveRange(0,notTaken.Count);
            arcs.RemoveRange(0, notTaken.Count);

            if (convex.HalfspaceList.Count < 2)
                throw new ApplicationException
                    ("Outline.ConvexInside: less than 2 halfspace in convex? shouldn't happen");
            // 
            // 5) Close the remaining arc list
            //
            //if (!arcList[E].Point2.Equals(arcList[S].Point1))
            if (arcList[E].Point2 != arcList[S].Point1)
            {
                // add extra constraint
                Arc a = new Arc(arcList[E].Point1, arcList[S].Point1);
                convex.Add(a.Circle);
                arcs.Add(a);

                // arc[S].p2 should now point to arc[E].p1
                arcList[S] = new Arc(arcList[S].Point1, arcList[E].Point1);

                // revise concave at 'S' and 'E'
                int Sm = (S - 1 + arcList.Count) % arcList.Count;
                concave[S] = Outline.IsConcave(arcList[Sm].Point1, arcList[S].Point1, arcList[S].Point2, tolerance);
                concave[E] = Outline.IsConcave(arcList[S].Point1, arcList[E].Point1, arcList[E].Point2, tolerance);

                // do not remove - now points to E
                taken.Remove(S); 
            }

            // 
            // 6) Remove taken arcs from self
            //
            taken.Sort();
            taken.Reverse();
            foreach (int i in taken)
            {
                if (notTaken.Contains(i))
                    continue;
                arcList.RemoveAt(i);
                concave.RemoveAt(i);
            }

            // add patches
            Patch patch = new Patch(arcs.ToArray());
            List<Patch> patchlist = new List<Patch>(1);
            patchlist.Add(patch);
            convex.SetPatches(patchlist);

            return convex;
        }

        #endregion
        #region Outside convexes ...

        private List<Convex> ConvexOutside(double tolerance)
        {
            List<Convex> outside = new List<Convex>(arcList.Count);
            for (int i = 0; i < arcList.Count; i++)
            {
                Convex c = new Convex(i + 1);
                for (int j = 0; j < i; j++)
                {
                    c.Add(arcList[j].Circle.Inverse());   
                }
                c.Add(arcList[i].Circle);
                c.Simplify(false, tolerance, Const.MaximumIteration);
                outside.Add(c);
            }
            arcList.Clear();
            return outside;
        }

        #endregion
        #region Create Region ...

        /// <summary>
        /// Make a region from outline
        /// </summary>
        /// <returns></returns>
        public Region Region()
        {
            return this.Region(Const.Tolerance);
        }

        /// <summary>
        /// Make a region from outline
        /// </summary>
        /// <returns></returns>
        public Region Region(double tolerance)
        {
            Region r = new Region(2);
            bool done = false;
            int maxiter = arcList.Count * 100;
            Convex c;
            for (int iter = 0; iter < maxiter; iter++)
            {
                c = this.ConvexInside(tolerance);
                if (c != null)
                {
                    //Console.Out.WriteLine("Convex area: {0}", c.Area);
                    if (c.HalfspaceList.Count < 3)
                        throw new ApplicationException
                            ("Outline.ConvexInside: less than 3 halfspaces? shouldn't happen");
                    r.Add(c);
                }
                else if (arcList.Count != 0)
                {
                    List<Convex> outside = this.ConvexOutside(tolerance);
                    r.AddRange(outside);
                }

                if (arcList.Count == 0)
                {
                    done = true;
                    break;
                }
            }
            if (!done)
                throw new ApplicationException
                    ("Outline.Region(): not done?!?");

            return r;
        }

        #endregion
        #region ToString and revision ...

        /// <summary>
        /// String representation
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            string r = "";
            foreach (Arc a in this.arcList)
                r += String.Format("{0}\n", a);
            return r;
        }

        /// <summary>
        /// Revision from CVS
        /// </summary>
        public static string Revision
        {
            get { return "$Revision: 1.1.1.1 $"; }
        }

        #endregion
    }
}

#region Revision History
/* Revision History

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

        Revision 1.2  2006/05/17 13:42:57  budavari
        Smarter staring point

        Revision 1.1  2006/04/24 13:46:51  budavari
        Outline moved to IO from Lib

        Revision 1.6  2006/04/19 16:51:01  budavari
        EVerything is now CLS compliant

        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