mainform.~cpp

该程序实现了Delaunay三角剖分的过程

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop
#include <math.h>
#include "MainForm.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TTMainForm *TMainForm;
//---------------------------------------------------------------------------
__fastcall TTMainForm::TTMainForm(TComponent* Owner)
    : TForm(Owner)
{
    X[0] = -3;
    X[1] = -2.025;
    X[2] = -0.225;
    X[3] = 0.225;
    X[4] = 2.025;
    X[5] = 3;
    X[6] = 0.5;
    X[7] = -0.5;
    Y[0] = 0;
    Y[1] = 0;
    Y[2] = 1.2;
    Y[3] = 1.2;
    Y[4] = 0;
    Y[5] = 0;
    Y[6] = 1.5;
    Y[7] = 1.5;
    Step = 0.1;
    /*
    n[0] = 4;
    n[1] = 10;
    n[2] = 3;
    n[3] = 10;
    n[4] = 4;
    n[5] = 15;
    n[6] = 5;
    n[7] = 15;
    */

    for(int i=0; i<7; i++)
    {
        n[i] = (int)(sqrt((X[i+1]-X[i])*(X[i+1]-X[i])+(Y[i+1]-Y[i])*(Y[i+1]-Y[i]))/Step)+1;
    }
    n[7] = (int)(sqrt((X[0]-X[7])*(X[0]-X[7])+(Y[0]-Y[7])*(Y[0]-Y[7]))/Step)+1;
    EdgeList = NULL;
    PointList = NULL;
    TriangleList = NULL;
    BorderList = NULL;
    EdgeList = new TList();
    PointList = new TList();
    TriangleList = new TList();
    BorderList = new TList();
    Mode = 0;

}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::ExitActionExecute(TObject *Sender)
{
    Close();
}
//---------------------------------------------------------------------------
#include "SetDlg.h"
void __fastcall TTMainForm::SetActionExecute(TObject *Sender)
{
    TTSetDlg *Dlg = new TTSetDlg(this);
    int i;
    for(i=0; i<8; i++)
    {
        Dlg->StringGrid1->Cells[1][2*i]  = FloatToStr(X[i]);
        Dlg->StringGrid1->Cells[1][2*i+1]  = FloatToStr(Y[i]);
    }
    Dlg->StringGrid1->Cells[1][16]  = FloatToStr(Step);
    if(mrOk == Dlg->ShowModal())
    {
        for(i=0; i<8; i++)
        {
            X[i] = Dlg->StringGrid1->Cells[1][2*i].ToDouble();
            Y[i] = Dlg->StringGrid1->Cells[1][2*i+1].ToDouble();
        }
        Step = Dlg->StringGrid1->Cells[1][16].ToDouble();
        for(i=0; i<7; i++)
        {
            n[i] = (int)(sqrt((X[i+1]-X[i])*(X[i+1]-X[i])+(Y[i+1]-Y[i])*(Y[i+1]-Y[i]))/Step)+1;
        }
        n[7] = (int)(sqrt((X[0]-X[7])*(X[0]-X[7])+(Y[0]-Y[7])*(Y[0]-Y[7]))/Step)+1;
    }
    delete Dlg;
}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::LineShowExecute(TObject *Sender)
{
    int i;
    Edge *e;
    MyPoint *p;
    Triangle *t;
    for(i=0; i<EdgeList->Count; i++)
    {
        e = (Edge*)EdgeList->Items[i];
        delete e;
    }
    EdgeList->Clear();
    for(i=0; i<BorderList->Count; i++)
    {
        e = (Edge*)BorderList->Items[i];
        delete e;
    }
    BorderList->Clear();
    for(i=0; i<PointList->Count; i++)
    {
        p = (MyPoint*)PointList->Items[i];
        delete p;
    }
    PointList->Clear();
    for(i=0; i<TriangleList->Count; i++)
    {
        t = (Triangle*)TriangleList->Items[i];
        delete t;
    }
    TriangleList->Clear();
    //将线段分段
    float fStepX,fStepY;
    for(i=0; i<7; i++)
    {
        fStepX = (X[i+1]-X[i])/n[i];
        fStepY = (Y[i+1]-Y[i])/n[i];
        for(int j=0; j<n[i]; j++)
        {
            p = new MyPoint;
            p->X = X[i]+j*fStepX;
            p->Y = Y[i]+j*fStepY;
            PointList->Add(p);
        }
    }
    fStepX = (X[0]-X[7])/n[7];
    fStepY = (Y[0]-Y[7])/n[7];
    for(int j=0; j<n[7]; j++)
    {
        p = new MyPoint;
        p->X = X[7]+j*fStepX;
        p->Y = Y[7]+j*fStepY;
        PointList->Add(p);
    }
    float XMin,XMax,YMin,YMax;
    p = (MyPoint*)PointList->Items[0];
    p->No = 1;
    p->Flag = 0;
    XMin = p->X;
    XMax = XMin;
    YMin = p->Y;
    YMax = YMin;
    for(i=1; i<PointList->Count; i++)
    {
        p = (MyPoint*)PointList->Items[i];
        p->No = i+1;
        p->Flag = 0;
        if(p->X > XMax)
        {
            XMax = p->X;
        }
        if(p->X < XMin)
        {
            XMin = p->X;
        }
        if(p->Y > YMax)
        {
            YMax = p->Y;
        }
        if(p->Y < YMin)
        {
            YMin = p->Y;
        }
    }

    Scale = ClientWidth/(2*(XMax-XMin));
    if(Scale > ClientHeight/(2*(YMax-YMin)))
    {
        Scale = ClientHeight/(2*(YMax-YMin));
    }

    Mode = 2;
    ReDraw();
}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::DelaunayExecute(TObject *Sender)
{
    int i;
    Edge *e;
    MyPoint *p;
    Triangle *t;
    for(i=0; i<EdgeList->Count; i++)
    {
        e = (Edge*)EdgeList->Items[i];
        delete e;
    }
    EdgeList->Clear();
    for(i=0; i<BorderList->Count; i++)
    {
        e = (Edge*)BorderList->Items[i];
        delete e;
    }
    BorderList->Clear();
    for(i=0; i<PointList->Count; i++)
    {
        p = (MyPoint*)PointList->Items[i];
        delete p;
    }
    PointList->Clear();
    for(i=0; i<TriangleList->Count; i++)
    {
        t = (Triangle*)TriangleList->Items[i];
        delete t;
    }
    TriangleList->Clear();
    //将线段分段
    float fStepX,fStepY;
    for(i=0; i<7; i++)
    {
        fStepX = (X[i+1]-X[i])/n[i];
        fStepY = (Y[i+1]-Y[i])/n[i];
        for(int j=0; j<n[i]; j++)
        {
            p = new MyPoint;
            p->X = X[i]+j*fStepX;
            p->Y = Y[i]+j*fStepY;
            PointList->Add(p);
        }
    }
    fStepX = (X[0]-X[7])/n[7];
    fStepY = (Y[0]-Y[7])/n[7];
    for(int j=0; j<n[7]; j++)
    {
        p = new MyPoint;
        p->X = X[7]+j*fStepX;
        p->Y = Y[7]+j*fStepY;
        PointList->Add(p);
    }
    float XMin,XMax,YMin,YMax;
    p = (MyPoint*)PointList->Items[0];
    p->No = 1;
    p->Flag = 0;
    XMin = p->X;
    XMax = XMin;
    YMin = p->Y;
    YMax = YMin;
    for(i=1; i<PointList->Count; i++)
    {
        p = (MyPoint*)PointList->Items[i];
        p->No = i+1;
        p->Flag = 0;
        if(p->X > XMax)
        {
            XMax = p->X;
        }
        if(p->X < XMin)
        {
            XMin = p->X;
        }
        if(p->Y > YMax)
        {
            YMax = p->Y;
        }
        if(p->Y < YMin)
        {
            YMin = p->Y;
        }
    }
    //确定显示比例
    Scale = ClientWidth/(2*(XMax-XMin));
    if(Scale > ClientHeight/(2*(YMax-YMin)))
    {
        Scale = ClientHeight/(2*(YMax-YMin));
    }
    MyPoint *p1,*p2;
    //生成边界边
    p1 = NULL;
    p2 = NULL;
    for(i=0; i<PointList->Count-1; i++)
    {
        p1 = (MyPoint*)PointList->Items[i];
        p2 = (MyPoint*)PointList->Items[i+1];
        e = new Edge;
        e->First = p1;
        e->Last = p2;
        BorderList->Add(e);
    }
    p1 = (MyPoint*)PointList->Items[0];
    e = new Edge;
    e->First = p2;
    e->Last = p1;
    BorderList->Add(e);
    //初始化候选列表
    SelectedList = new TList();
    Edge *e1,*e2,*e3;
    while(BorderList->Count > 3)
    {
        Mode = 3;
        ReDraw();
        Sleep(200);
        //生成候选点列表
        SelectedList->Clear();
        e = (Edge*)BorderList->Items[0];
        for(i=1; i<BorderList->Count; i++)
        {
            e1 = (Edge*)BorderList->Items[i];
            if(Direction(e->First,e->Last,e1->Last) == 1)
            {
                //e1->Last在e边的左边
                bool flag = false;
                for(int j=0; j<BorderList->Count; j++)
                {
                    e2 = (Edge*)BorderList->Items[j];
                    if(Cross(e->First,e->Last,e2->First,e2->Last) == 1)
                    {
                        flag = true;
                        break;
                    }
                }
                if(!flag)
                {
                    SelectedList->Add(e1->Last);
                }
            }
        }
        //从候选点中选出与e生成的三角形外接圆半径最小的点
        if(SelectedList->Count == 0)
        {
            break;
        }
        Triangle *t1,*t2;
        t1 = new Triangle;
        t2 = new Triangle;
        while(SelectedList->Count > 1)
        {
            t1->R = 0;
            t2->R = 0;
            for(i=0; i<SelectedList->Count; i++)
            {
                p = (MyPoint*)SelectedList->Items[i];
                if(0 == t1->R)
                {
                    GetExternPt(e->First,e->Last,p,t1);
                }
                else
                {
                    GetExternPt(e->First,e->Last,p,t2);
                    if(0 == t1->R && 0 != t2->R )
                    {
                        t = t1;
                        t1 = t2;
                        t2 = t;
                    }
                    else
                    {
                        if(t1->R > t2->R && 0 != t2->R)
                        {
                            t = t1;
                            t1 = t2;
                            t2 = t;
                        }
                    }
                }
            }
            for(i=0; i<SelectedList->Count; i++)
            {
                p = (MyPoint*)SelectedList->Items[i];
                if(Direction(e->Last,t1->P[2],p) == -1)
                {
                    SelectedList->Remove(p);
                    i--;
                    continue;
                }
                if(Direction(t1->P[2],e->First,p) == -1)
                {
                    SelectedList->Remove(p);
                    i--;
                    continue;
                }
            }
            if(1 == SelectedList->Count)
            {
                break;
            }
            else
            {
                SelectedList->Remove(t1->P[2]);
            }
        }
        p = (MyPoint*)SelectedList->Items[0];
        GetExternPt(e->First,e->Last,p,t1);
        TriangleList->Add(t1);
        delete t2;
        //根据三角形边的情况修改多边形边
        e1 = FindEdge(t1->P[0],t1->P[2],BorderList);
        e2 = FindEdge(t1->P[1],t1->P[2],BorderList);
        if(NULL != e1 && NULL != e2)
        {
            //两条边都是多边形的边界
            BorderList->Remove(e);
            delete e;
            BorderList->Remove(e1);
            delete e1;
            BorderList->Remove(e2);
            delete e2;
        }
        else if(NULL != e1 || NULL != e2)
        {
            //有一条边是多边形的边界
            if(NULL != e1)
            {
                e->First = t1->P[2];
                BorderList->Remove(e1);
                delete e1;
            }
            else
            {
                e->Last = t1->P[2];
                BorderList->Remove(e2);
                delete e2;
            }
        }
        else
        {
            //都不是多边形的边
            e3 = new Edge;
            e3->First = t1->P[2];
            e3->Last = e->Last;
            BorderList->Add(e3);
            e->Last = t1->P[2];
        }
    }
    SelectedList->Clear();
    MyPoint *p3;
    if(3 == BorderList->Count)
    {
        e1 = (Edge*)BorderList->Items[0];
        e2 = (Edge*)BorderList->Items[1];