datastruct1.cs

Tin的建立

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

namespace D_sanjiao
{
    class DPoint
    {
        public double x=0, y=0, z=0;
        public List<DTiangle> UseThis = new List<DTiangle>();
        public DPoint(double xc, double yc, double zc) { x = xc; y = yc; z = zc; }
        public DPoint() { x = 0; y = 0; z = 0;}
        public bool IsClosed = true;  //共这点的三角形是否封闭
    }

    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,TheC;
        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);
            }
        }

        public List<DPoint> ThePoints;
        List<DPoint> pointlist=new List<DPoint>();
        StackList EdgeStack = new StackList();
        public 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);
            DLine line = new DLine(firstp, secondp, null, null);

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

            //DPoint thirdp = GetMinDistPoint(midpoint);
            DPoint thirdp = FindBestPoint(line);
            //ThePoints.Remove(thirdp);

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

            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;

            if(!newtri.point1.UseThis.Contains(newtri)) newtri.point1.UseThis.Add(newtri);
            if (!newtri.point2.UseThis.Contains(newtri)) newtri.point2.UseThis.Add(newtri);
            if (!newtri.point3.UseThis.Contains(newtri)) newtri.point3.UseThis.Add(newtri);
            //newtri.TheC=GetTheTriC(newtri);
            newtri.TheC = circle_center(newtri);

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

            Expand(edge1);
            ReSort(ThePoints);
        }

        private DLine GetTheProEdge(DTiangle t1, DPoint p1)
        {
            DLine resul = null;
            if (IsSamePoint(p1, t1.edge1.endpoint))
            {
                resul = t1.edge1;
            }
            if (IsSamePoint(p1, t1.edge2.endpoint))
            {
                resul = t1.edge2;
            }
            if (IsSamePoint(p1, t1.edge3.endpoint))
            {
                resul = t1.edge3;
            }
            return resul;
        }

        private void ReSort(List<DPoint> ThePoints)
        {
            for (int m = 0; m < ThePoints.Count; m++)
            {
                DPoint nowp=ThePoints[m];
                DLine StartLine=GetTheFirstTriEdge(nowp);
                List<DTiangle> newl = new List<DTiangle>();
                newl.Add(StartLine.Ltri);
                for(int n=1;n<nowp.UseThis.Count;n++)
                {
                    newl.Add(GetTheProEdge(newl[newl.Count - 1], nowp).Rtri);
                }
                nowp.UseThis = newl;
            }
        }

        private DLine GetTheFirstTriEdge(DPoint nowp)
        {
            int nulledge = 0;
            DLine maybeline = null;
            foreach (DTiangle temp in nowp.UseThis)
            {
                if (IsSamePoint(temp.edge1.beginpoint, nowp) && temp.edge1.Rtri == null) { nulledge++; maybeline = temp.edge1; }
                if (IsSamePoint(temp.edge1.endpoint, nowp) && temp.edge1.Rtri == null) nulledge++;
                if (IsSamePoint(temp.edge2.beginpoint, nowp) && temp.edge2.Rtri == null) { nulledge++; maybeline = temp.edge2; }
                if (IsSamePoint(temp.edge2.endpoint, nowp) && temp.edge2.Rtri == null) nulledge++;
                if (IsSamePoint(temp.edge3.beginpoint, nowp) && temp.edge3.Rtri == null) { nulledge++; maybeline = temp.edge3; }
                if (IsSamePoint(temp.edge3.endpoint, nowp) && temp.edge3.Rtri == null) nulledge++;
            }
            if (nulledge == 0)
            {
                nowp.IsClosed = true;
                return GetTheProEdge(nowp.UseThis[0], nowp);
            }
            if (nulledge == 2)
            {
                nowp.IsClosed = false;
                return maybeline;
            }
            return null;  //图形正常的话不可能执行到这里
        }

        private DPoint GetTheTriC(DTiangle newtri)
        {
            double x1 = newtri.point1.x;
            double y1 = newtri.point1.y;
            double x2 = newtri.point2.x;
            double y2 = newtri.point2.y;
            double x3 = newtri.point3.x;
            double y3 = newtri.point3.y;
            DPoint TheC = new DPoint();
            TheC.y = ((x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) * (x2 - x1) - (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) * (x3 - x1)) / (2 * ((y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)));
            TheC.x = ((x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) - 2 * TheC.y * (y2 - y1)) / (2 * (x2 - x1));
            return TheC;
        }

        private DPoint circle_center(DTiangle newtri)
        {
            double x1, x2, x3, y1, y2, y3;
            double x = 0;
            double y = 0;

            x1 = newtri.point1.x;
            x2 = newtri.point2.x;
            x3 = newtri.point3.x;
            y1 = newtri.point1.y;
            y2 = newtri.point2.y;
            y3 = newtri.point3.y;

            x = ((y2 - y1) * (y3 * y3 - y1 * y1 + x3 * x3 - x1 * x1) - (y3 - y1) * (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1)) / (2 * (x3 - x1) * (y2 - y1) - 2 * ((x2 - x1) * (y3 - y1)));
            y = ((x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) - (x3 - x1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)) / (2 * (y3 - y1) * (x2 - x1) - 2 * ((y2 - y1) * (x3 - x1)));

            DPoint TheC = new DPoint();
            TheC.x = x;
            TheC.y = y;
            return TheC;

        }

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

                DPoint BestPoint = FindBestPoint(edge);

                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;

                    if (!newtri.point1.UseThis.Contains(newtri)) newtri.point1.UseThis.Add(newtri);
                    if (!newtri.point2.UseThis.Contains(newtri)) newtri.point2.UseThis.Add(newtri);
                    if (!newtri.point3.UseThis.Contains(newtri)) newtri.point3.UseThis.Add(newtri);
                    newtri.TheC =circle_center(newtri);
                    TriangleList.Add(newtri);

                    ExecuteEdge(edge1);
                    ExecuteEdge(edge2);
                }
                if(EdgeStack.Count>0) edge = EdgeStack.Pop();
            }
        }

        private bool IsSamePoint(DPoint p1, DPoint p2)
        {
            if (p1.x == p2.x && p1.y == p2.y ) return true;
            return false;
        }
        private bool IsSameLine(DLine l1, DLine l2)
        {
            if(IsSamePoint(l1.beginpoint,l2.beginpoint)&&IsSamePoint(l1.endpoint, l2.endpoint)) return true;
            if(IsSamePoint(l1.beginpoint, l2.endpoint) && IsSamePoint(l1.endpoint, l2.beginpoint)) return true;
            return false;
        }

        private void ExecuteEdge(DLine edge)
        {
            DLine FindInStack = null;
            foreach (DLine temp in EdgeStack)
            {
                if (IsSameLine(temp, edge)) FindInStack = temp;
            }
            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;
            foreach (DPoint temp in ThePoints)
            {
                if (!IsSamePoint(temp, fp))
                {
                    double dis = distan(temp, fp);
                    if (dis < mindis)
                    { mindis = dis; minp = temp; }
                }
            }
            return minp;
        }
    }
}