HalfEdge.cs

Go to the documentation of this file.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Wolfram.NETLink;

namespace PolyLink
{
    public class HalfEdge : MathLinked
    {

        public Facet Facet { get; set; }

        public string Tag
        {
            get { return Facet.Tag; }
        }

        public EndPointPacket EndPointPacket
        {
            get
            {
                return new EndPointPacket(Start, End);
            }
        }

        public EndPointPacket OppositesEndPointPacket
        {
            get
            {
                return EndPointPacket.Opposite;
            }
        }

        public PointRef Start
        {
            get { return _start; }
            set { _start = value; }
        }

        public PointRef End
        {
            get { return _end; }
            set { _end = value; }
        }

        protected PointRef _start;
        protected PointRef _end;

        protected HalfEdge _opposite;

        public HalfEdge Opposite
        {
            get { return _opposite; }
            set
            {
                _opposite = value;
            }
        }

        protected HalfEdge _next;
        protected HalfEdge _prev;

        public HalfEdge Next
        {
            get { return _next; }
        }

        public HalfEdge Prev
        {
            get { return _prev; }
        }

        public IEnumerable<HalfEdge> HEsFromHere
        {
            get
            {
                yield return this;
                var he = this.Next;
                while (he != this)
                {
                    yield return he;
                    he = he.Next;
                }
            }
        }

        public IEnumerable<HalfEdge> HEsFromHereReversed
        {
            get
            {
                yield return this;
                var he = this.Prev;
                while (he != this)
                {
                    yield return he;
                    he = he.Prev;
                }
            }
        }

        public Expr AsVectorExpr
        {
            get { return EndPointPacket.AsVector; }
        }

        public Vector AsVector
        {
            get {return new Vector(this.AsVectorExpr);}
        }

        public Plane Plane
        {
            get
            {
                Expr point = Start.Expr;
                Expr normal = ML["Normalize[Cross[{0},{1}]]"].Format(this.AsVectorExpr, Next.AsVectorExpr).FullSimplify().Eval();
                return new Plane(point, normal);
            }
        }

        public Expr DotOpposite
        {
            get { return ML["Dot[{0},{1}]"].Format(this.Plane.Normal, Opposite.Plane.Normal).Eval(); }
        }

        public HalfEdge[] DetourToVertex(PointRef p)
        {
            var ret = new HalfEdge[2];
            var outHE = new HalfEdge(End, p)
                {
                    Facet = Facet
                };
            var backHE = new HalfEdge(p, End)
                {
                    Facet = Facet
                };
            outHE.Opposite = backHE;
            backHE.Opposite = outHE;

            var oldNext = _next;
            _next = outHE;
            outHE._prev = this;
            outHE._next = backHE;
            backHE._prev = outHE;
            backHE._next = oldNext;

            ret[0] = outHE;
            ret[1] = backHE;
            return ret;
        }

        public Dictionary<HalfEdge, HalfEdge> LinkNext(HalfEdge he)
        {
            var d = new Dictionary<HalfEdge, HalfEdge>();
            d[this] = Next;
            d[he] = he.Prev;
            _next = he;
            he._prev = this;
            return d;
        }

        public bool OppIsNull
        {
            get { return Opposite == null; }
        }

        public void MergeAcross()
        {
            var prev = Prev;
            prev.LinkNext(Opposite.Next);
            Opposite.Prev.LinkNext(Next);
            Opposite.Facet.Head = null;
            foreach (var halfEdge in prev.HEsFromHere)
            {
                halfEdge.Facet = Facet;
            }
        }

        public override string ToString()
        {
            return String.Format("[{0} to {1}]", Start, End);
        }

        public bool DontCycle { get; set; }

        public IEnumerable<HalfEdge> CycleAboutEndPoint
        {
            get
            {
                if (DontCycle)
                {
                    yield break;
                }

                yield return this;
                var he = this.Next.Opposite;
                while (he != this)
                {
                    yield return he;
                    he = he.Next.Opposite;
                }
            }
        }

        public Expr DotNext
        {
            get { return ML["Dot"].Bracket(this.AsVectorExpr, this.Next.EndPointPacket.Opposite.AsVector).Eval(); }
        }

        public Expr AngleToNext
        {
            get
            {
                return ML["ArcCos[{0}] / ({1} * {2})"].Format(this.DotNext, this.EndPointPacket.Magnitude,
                                                            this.Next.EndPointPacket.Magnitude).Eval();
            }
        }

        public Expr SumAngles
        {
            get
            {
                return this.CycleAboutEndPoint.Select(he => he.AngleToNext).Aggregate((a1, a2) => ML["{0} + {1}"].Format(a1,a2).Eval());
            }
        }

        public Expr Curvature
        {
            get { return ML["2*Pi - {0}"].Format(SumAngles).Eval(); }
        }

        public Expr Highlight
        {
            get { return ML["List[ {{ Thick, Red, Arrow[ {{ {0},{1} }} ] }} ]"].Format(Start.Expr, End.Expr).Eval(); }
        }

        //Static methods

        private static readonly HalfEdge littleLine = new HalfEdge(PointRef.OriginRef, PointRef.Ref100);
        private static readonly HalfEdge line2 = new HalfEdge(PointRef.Ref100, PointRef.Ref010);
        private static readonly HalfEdge line3 = new HalfEdge(PointRef.Ref010, PointRef.OriginRef);

        public static HalfEdge LittleLine
        {
            get { return littleLine; }
        }

        public static HalfEdge Facetable
        {
            get
            {
                if (LittleLine.Next == null)
                {
                    LittleLine.LinkNext(line2);
                    line2.LinkNext(line3);
                    line3.LinkNext(LittleLine);
                }
                return LittleLine;
            }
        }

        public Expr NormalGraphics
        {
            get { return ML["List[ {{Purple, Arrow[ {{ {0}, {0} + {1} }} ] }} ]"].Format(End.Expr, Plane.Normal).Eval(); }
        }
        //End section

        public HalfEdge(PointRef start, PointRef end)
        {
            _start = start;
            _end = end;
            DontCycle = false;
        }

        public bool Torn
        {
            get
            {
                return (Opposite == null)
                       || (Opposite.Start != End)
                       || (Opposite.End != Start);
            }
        }

        public void Unfold(IEnumerable<PointRef> stowaways = null, IEnumerable<HalfEdge> stowawayHalfEdges = null)
        {

            if (stowaways == null)
            {
                stowaways = Enumerable.Empty<PointRef>();
            }
            if (stowawayHalfEdges == null)
            {
                stowawayHalfEdges = Enumerable.Empty<HalfEdge>();
            }

            var transVect = Vector.FromPoints(this.Start.Expr, Opposite.End.Expr);
            var translation = ML["TranslationTransform"].Bracket(transVect.Expr).Eval();
            TransformFacet(translation);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(translation);
            }
            foreach (var halfedge in stowawayHalfEdges)
            {
                halfedge.Transform(translation,
                    includeStart: !halfedge.Start.EqualsAny(Start,End),
                    includeEnd: !halfedge.End.EqualsAny(Start,End));
            }

            var rotation1 = ML["RotationTransform"].Bracket(
                        ML["List"].Bracket(
                                this.Plane.Normal,
                                Opposite.Plane.Normal
                            ).Eval(),
                            Opposite.End.Expr
                    ).Eval();
            TransformFacet(rotation1);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(rotation1);
            }
            foreach (var halfedge in stowawayHalfEdges)
            {
                halfedge.Transform(rotation1,
                    includeStart: !halfedge.Start.EqualsAny(Start, End),
                    includeEnd: !halfedge.End.EqualsAny(Start, End));
            }

            var rotation2 = ML["RotationTransform"].Bracket(
                ML["List"].Bracket(
                        this.AsVectorExpr,
                        ML["-1 * {0}"].Format(Opposite.AsVectorExpr).Eval()
                    ).Eval(),
                    Opposite.End.Expr
                ).Eval();
            TransformFacet(rotation2);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(rotation2);
            }
            foreach (var halfedge in stowawayHalfEdges)
            {
                halfedge.Transform(rotation2,
                    includeStart: !halfedge.Start.EqualsAny(Start, End),
                    includeEnd: !halfedge.End.EqualsAny(Start, End));
            }

            //This 'snapping' code is part of correct behavior, but we sometimes
            //comment it out to check our transforms.
            
            Start = Opposite.End;
            End = Opposite.Start;
            Prev.End = Start;
            Next.Start = End;
        }

        public void TransformFacet(Expr matrix)
        {
            //For every HalfEdge other than myself
            foreach (var halfEdge in HEsFromHere)
            {
                halfEdge.Transform(matrix);
            }

            foreach (var halfEdge in HEsFromHere)
            {
                halfEdge.Next.Start = halfEdge.End;
            }
        }

        public void UselessTransform()
        {
            var m = ML["TranslationTransform"].Bracket("{0,0,0}").Eval();
            TransformFacet(m);
        }

        public void Anchor(IEnumerable<PointRef> stowaways)
        {
            if (stowaways == null)
            {
                stowaways = Enumerable.Empty<PointRef>();
            }

            var transVec = new EndPointPacket(this.Start, PointRef.OriginRef).AsVector;
            var translation = ML["TranslationTransform"].Bracket(transVec).Eval();
            TransformFacet(translation);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(translation);
            }


            var rotation1 = ML["RotationTransform"].Bracket(
                        ML["List"].Bracket(
                                this.Plane.Normal,
                                ML["{0,0,1}"].Eval()
                            ).Eval(),
                            PointRef.Origin
                    ).Eval();
            TransformFacet(rotation1);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(rotation1);
            }

            var rotation2 = ML["RotationTransform"].Bracket(
                    ML["List"].Bracket(
                            this.AsVectorExpr,
                            ML["{1,0,0}"].Eval()
                        ).Eval()
                ).Eval();
            TransformFacet(rotation2);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(rotation2);
            }

            var rotation3 = ML["RotationTransform"].Bracket(
                    ML["List"].Bracket(
                            this.Plane.Normal,
                            ML["{0,0,1}"].Eval()
                        ).Eval(),
                        PointRef.Origin
                ).Eval();
            TransformFacet(rotation3);
            foreach (var stowaway in stowaways)
            {
                stowaway.Transform(rotation3);
            }
        }
        public void Transform(Expr transform, bool includeStart = true, bool includeEnd = true)
        {

            if (includeStart)
            {
                Start = new PointRef(
                    ML["{0}[{1}]"].Format(transform, Start.Expr).Eval());
            }
            if (includeEnd)
            {
                End = new PointRef(
                    ML["{0}[{1}]"].Format(transform, End.Expr).Eval());
            }
        }

        public Expr Graphics
        {
            get
            {
                if (Torn)
                {
                    return ML["List[{{ Dashed, Arrow[ {{ {0}, {1} }}] }}]"].Format(Start.Expr, Opposite.End.Expr).Eval();
                }
                return null;
            }
        }

        public void NegativeTranslate(Vector v)
        {
            var translation = ML["TranslationTransform[-{0}]"].Format(v.Expr).Eval();
            TransformFacet(translation);
        }

        public HalfEdge FacetCloneWithOriginalOpposites
        {
            get {
                var clone = FacetRingClone;
                var clonePairs = HEsFromHere
                    .NetZip(clone.HEsFromHere,
                         (o, c) => new WorkingCopy<HalfEdge>(o,c));
                foreach (var cp in clonePairs)
                {
                    cp.Copy.Facet = cp.Original.Facet;
                    cp.Copy.Opposite = cp.Original.Opposite;
                }
                return clone;
            }
        }

        public HalfEdge FacetRingClone
        {
            get
            {
                var cloneRing = HEsFromHere
                    .Select(he => he.ShallowClone).Skip(1);
                var prev = ShallowClone;
                var myClone = prev;

                foreach (var he in cloneRing.Concat(new[] { myClone }))
                {
                    he.Start = he.Start.DeepClone;
                    prev.End = he.Start;
                    prev.LinkNext(he);
                    prev = he;
                }

                return myClone;
            }
        }

        protected HalfEdge ShallowClone
        {
            get
            {
                var r=  new HalfEdge(Start, End)
                    {
                        _next = Next,
                        _prev = Prev,
                        _opposite = null,
                    };
                r.DontCycle = true;
                return r;
            }
        }

        public Expr Midpoint
        {
            get { return ML["Mean"].Bracket(
                ML["List"].Bracket(Start.Expr, End.Expr).Eval()).Eval(); }
        }

        public Expr Label(int i)
        {
            var labelPoint = ML["{0} + .05*{1}"].Format(Midpoint, Plane.Normal).Eval();
            return ML["Inset"].Bracket(i, labelPoint, "BaseStyle -> {Darker[Blue], Italic}").Eval();
        }


        public void MoveStartPoint(Expr p)
        {
            Start.Expr = p;
        }

        public Facet ForceNewFacet
        {
            get
            {
                return new Facet(this);
            }
        }

        public IEnumerable<HalfEdge> BreadthFirstGrab(bool includeTorn = false)
        {
            var dontGrab = new HashSet<HalfEdge>();
            var queue = new Queue<HalfEdge>();
            var grab = new List<HalfEdge>();

            queue.Enqueue(this);
            dontGrab.UnionWith(this.Opposite.HEsFromHere.ToHashSet());

            while (queue.Count > 0)
            {
                var he = queue.Dequeue();
                if (dontGrab.Contains(he))
                    continue;

                grab.Add(he);
                dontGrab.UnionWith(he.HEsFromHere.ToHashSet());

                var opposites = he.HEsFromHere.Skip(1).Select(h => h.Opposite).ToList();
                var validOpps = opposites
                    .Where(h => !dontGrab.Contains(h))
                    .Where(h => includeTorn || !h.Torn).ToList();
                foreach (var halfedge in validOpps)
                {
                    queue.Enqueue(halfedge);
                }
            }
           
            return grab;
        }

        public IEnumerable<PointRef> StartPointsFromHere
        {
            get { return HEsFromHere.Select(he => he.Start); }
        }
        
        public void CascadingUnfold(Polyhedron p)
        {
            var facetHesTorn = HEsFromHere.Select(he => he.Torn).ToList();

            var hes = BreadthFirstGrabAll();
            Unfold(null, hes);
            p.FusePoints();
            //Prev.End = Start;
            //Next.Start = End;

            var facetHes_facetHesTorn = HEsFromHere.NetZip(facetHesTorn, (he, b) => new Tuple<HalfEdge,bool>(he,b));
            foreach (var tuple in facetHes_facetHesTorn)
            {
                HalfEdge h = tuple.Item1;
                bool wasTorn = tuple.Item2;

                if (!wasTorn)
                {
                    h.Start = h.Opposite.End;
                    h.End = h.Opposite.Start;
                }
            }
        }

        public IEnumerable<PointRef> BreadthFirstPoints()
        {
            return BreadthFirstGrab().Except(new[] {this}).SelectMany(he => he.StartPointsFromHere).Except(new[] {Start,End}).ToHashSet();
        }

        public IEnumerable<HalfEdge> BreadthFirstGrabAll()
        {
            return BreadthFirstGrab().Except(new[] {this}).SelectMany(he => he.HEsFromHere).ToHashSet();
        }
    }
}