datastruct.cs

Tin的建立

using System;
using System.Collections.Generic;
using System.Text;

namespace D_sanjiao
{
    class DPoint
    {
        public double x, y, z;
        public DPoint(double xc, double yc, double zc) { x = xc; y = yc; z = zc; }
        public DPoint() { x = 0; y = 0; z = 0;}
    }

    class DLine
    {
        public DPoint beginpoint, endpoint;
        public DTiangle Ltri, Rtri;
        public DLine(DPoint begin, DPoint end, DTiangle ltri, DTiangle rtri) { beginpoint = begin; endpoint = end; Ltri = ltri; Rtri = rtri; }
        public bool isleft(DPoint temp) 
        {
            double equation = ((temp.y - beginpoint.y) * (endpoint.x - beginpoint.x)) - ((endpoint.y - beginpoint.y) * (temp.x - beginpoint.x));
            if (equation > 0) return true;
            else return false;
        }
    }

    class DTiangle
    {
        public DPoint point1, point2, point3;
        public DLine edge1, edge2,edge3;
        public DTiangle(DPoint pit1, DPoint pit2, DPoint pit3) { point1 = pit1; point2 = pit2; point3 = pit3; }
    }

    class DelaunyBuilder
    {
        class StackList : List<DLine>
        {
            public DLine Pop()
            {
                DLine temp = this[this.Count - 1];
                this.RemoveAt(this.Count - 1);
                return temp;
            }

            public void Push(DLine temp)
            {
                this.Add(temp);
            }
        }

        List<DPoint> ThePoints;
        List<DPoint> pointlist=new List<DPoint>();
        StackList EdgeStack = new StackList();
        List<DTiangle>  TriangleList=new List<DTiangle>();

        public DelaunyBuilder(List<DPoint> thepoints) { ThePoints = thepoints; }

        public void BuildTIN()
        {

            DPoint firstp = ThePoints[0];
            ThePoints.Remove(firstp);
            DPoint secondp = GetMinDistPoint(firstp);
            ThePoints.Remove(secondp);

            DPoint midpoint = new DPoint((firstp.x + secondp.x) / 2, (firstp.y + secondp.y) / 2, 0);

            DPoint thirdp = GetMinDistPoint(midpoint);
            ThePoints.Remove(thirdp);

            pointlist.Add(firstp);
            pointlist.Add(secondp);
            pointlist.Add(thirdp);

            DLine line = new DLine(firstp, secondp,null,null);
            if (!line.isleft(thirdp))
                pointlist.Reverse();
            firstp = pointlist[0];
            secondp = pointlist[1];
            thirdp = pointlist[2];

            DTiangle newtri = new DTiangle(firstp, secondp, thirdp);

            DLine edge1 = new DLine(firstp, secondp, newtri, null);
            DLine edge2 = new DLine(secondp, thirdp, newtri, null);
            DLine edge3 = new DLine(thirdp, firstp, newtri, null);

            newtri.edge1 = edge1; newtri.edge2 = edge2; newtri.edge3 = edge3;

            TriangleList.Add(newtri);
            EdgeStack.Push(edge2);
            EdgeStack.Push(edge3);

            Expand(edge1);
        }

        private void Expand(DLine edge)
        {
            while (EdgeStack.Count != 0)
            {
                DPoint beginp= edge.beginpoint;
                DPoint endp = edge.endpoint;

                DPoint BestPoint = FindBestPoint(edge);
                ThePoints.Remove(BestPoint);

                if (BestPoint != null)
                {
                    DTiangle newtri = new DTiangle(beginp, BestPoint, endp);
                    DLine edge1 = new DLine(beginp, BestPoint, newtri, null);
                    DLine edge2 = new DLine(BestPoint, endp, newtri, null);
                    DLine edge3 = new DLine(endp, beginp, newtri, null);

                    edge3.Rtri = edge.Ltri;
                    edge.Rtri = edge3.Ltri;

                    newtri.edge1 = edge1; newtri.edge2 = edge2; newtri.edge3 = edge3;
                    TriangleList.Add(newtri);

                    ExecuteEdge(edge1);
                    ExecuteEdge(edge2);
                    edge = EdgeStack.Pop();

                }
            }
        }

        private bool IsSameLine(DLine l1, DLine l2)
        {
            //if(l1.beginpoint.x=l2.beginpoint.x&&l1.beginpoint
        }
        private void ExecuteEdge(DLine edge)
        {
            DLine FindInStack=EdgeStack.Find(delegate(DLine temp){if(temp==edge) return true;else return false;});
            if (FindInStack != null)
            {
                edge.Rtri = FindInStack.Ltri;
                FindInStack.Rtri = edge.Ltri;
                EdgeStack.Remove(FindInStack);
            }
            else
            {
                EdgeStack.Add(edge);
            }
        }

        private DPoint FindBestPoint(DLine edge)
        {
            double maxzhangjiao = double.MaxValue;
            DPoint sp=null;
            foreach (DPoint temp in ThePoints)
            {
                    if (!edge.isleft(temp))
                    {
                        double a = distan(edge.beginpoint, temp);
                        double b = distan(temp, edge.endpoint);
                        double c = distan(edge.beginpoint, edge.endpoint);
                        double CosC = (a * a + b * b + c * c) / (2 * a * b);
                        if (CosC < maxzhangjiao) { maxzhangjiao = CosC; sp = temp; }
                    }
            }
            return sp;
        }

        private double distan(DPoint p1, DPoint p2)
        {
            return Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
        }

        private DPoint GetMinDistPoint(DPoint fp)
        {
            double mindis = double.MaxValue;
            DPoint minp=null;
            ThePoints.ForEach(delegate(DPoint temp) { double dis = distan(temp, fp); if (dis < mindis) { mindis = dis; minp = temp; } } );
            return minp;
        }
    }
}