mainform.cpp

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

        p1 = e1->First;
        p2 = e1->Last;
        if(e2->First != p1 && e2->First != p2)
        {
            p3 = e2->First;
        }
        else
        {
            p3 = e2->Last;
        }
        t = new Triangle;
        GetExternPt(p1,p2,p3,t);
        TriangleList->Add(t);
    }
    delete SelectedList;
    Mode = 3;
    ReDraw();
}
//---------------------------------------------------------------------------

void __fastcall TTMainForm::FormDestroy(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();
    delete EdgeList;
    EdgeList = NULL;
    for(i=0; i<BorderList->Count; i++)
    {
        e = (Edge*)BorderList->Items[i];
        delete e;
    }
    BorderList->Clear();
    delete BorderList;
    BorderList = NULL;
    for(i=0; i<PointList->Count; i++)
    {
        p = (MyPoint*)PointList->Items[i];
        delete p;
    }
    PointList->Clear();
    delete PointList;
    PointList = NULL;
    for(i=0; i<TriangleList->Count; i++)
    {
        t = (Triangle*)TriangleList->Items[i];
        delete t;
    }
    TriangleList->Clear();
    delete TriangleList;
    TriangleList = NULL;
}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::PtShowExecute(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 = 1;
    ReDraw();
}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::FormPaint(TObject *Sender)
{
    ReDraw();    
}
//---------------------------------------------------------------------------

void TTMainForm::ReDraw()
{
    Canvas->Brush->Color = clWhite;
    Canvas->FillRect(TRect(0,0,ClientWidth,ClientHeight));
    int X0 = ClientWidth/2;
    int Y0 = ClientHeight/2;
    int i;
    MyPoint *p;
    Edge *e;
    Triangle *t;
    switch(Mode)
    {
        case 1:
            for(i=0; i<PointList->Count; i++)
            {
                p = (MyPoint*)PointList->Items[i];
                if(p->No>0)
                {
                    Canvas->Pixels[(int)(X0+p->X*Scale)][(int)(Y0-p->Y*Scale)] = clBlack;
                }
            }
            break;
        case 2:
            p = (MyPoint*)PointList->Items[0];
            Canvas->MoveTo((int)(X0+p->X*Scale),(int)(Y0-p->Y*Scale));

            for(i=1; i<PointList->Count; i++)
            {
                p = (MyPoint*)PointList->Items[i];
                if(p->No>0)
                {
                    Canvas->LineTo((int)(X0+p->X*Scale),(int)(Y0-p->Y*Scale));
                }
            }
            p = (MyPoint*)PointList->Items[0];
            Canvas->LineTo((int)(X0+p->X*Scale),(int)(Y0-p->Y*Scale));
            break;
        case 3:
            for(i=0; i<TriangleList->Count; i++)
            {
                t = (Triangle*)TriangleList->Items[i];
                Canvas->MoveTo((int)(X0+t->P[2]->X*Scale),(int)(Y0-t->P[2]->Y*Scale));
                for(int j=0; j<3; j++)
                {
                    Canvas->LineTo((int)(X0+t->P[j]->X*Scale),(int)(Y0-t->P[j]->Y*Scale));
                }
            }
            break;
    }
}
void __fastcall TTMainForm::RefineExecute(TObject *Sender)
{
    //细化
    Triangle *t,*t1;;
    MyPoint *p1,*p2,*p3,*p;
    int i;
    for(i=0; i<TriangleList->Count; i++)
    {
        t = (Triangle*)TriangleList->Items[i];
        p1 = t->P[0];
        p2 = t->P[1];
        p3 = t->P[2];
        if((p1->X-p2->X)*(p1->X-p2->X)+(p1->Y-p2->Y)*(p1->Y-p2->Y) > Step*Step)
        {
            if(0 != p1->Flag && 0 != p2->Flag)
            {
                p = new MyPoint;
                p->X = (p1->X+p2->X)/2;
                p->Y = (p1->Y+p2->Y)/2;
                p->Flag = 1;
                PointList->Add(p);
                t1 = new Triangle;
                t1->P[0] = p3;
                t1->P[1] = p2;
                t1->P[2] = p;
                TriangleList->Add(t1);
                t->P[1] = p;
                i--;
                continue;
            }
        }
        if((p1->X-p3->X)*(p1->X-p3->X)+(p1->Y-p3->Y)*(p1->Y-p3->Y) > Step*Step)
        {
            if(0 != p1->Flag && 0 != p3->Flag)
            {
                p = new MyPoint;
                p->X = (p1->X+p3->X)/2;
                p->Y = (p1->Y+p3->Y)/2;
                p->Flag = 1;
                PointList->Add(p);
                t1 = new Triangle;
                t1->P[0] = p2;
                t1->P[1] = p3;
                t1->P[2] = p;
                TriangleList->Add(t1);
                t->P[2] = p;
                i--;
                continue;
            }
        }
        if((p3->X-p2->X)*(p3->X-p2->X)+(p3->Y-p2->Y)*(p3->Y-p2->Y) > Step*Step)
        {
            if(0 != p3->Flag && 0 != p2->Flag)
            {
                p = new MyPoint;
                p->X = (p3->X+p2->X)/2;
                p->Y = (p3->Y+p2->Y)/2;
                p->Flag = 1;
                PointList->Add(p);
                t1 = new Triangle;
                t1->P[0] = p1;
                t1->P[1] = p2;
                t1->P[2] = p;
                TriangleList->Add(t1);
                t->P[1] = p;
                i--;
                continue;
            }
        }
    }
    Mode = 3;
    ReDraw();
}
//---------------------------------------------------------------------------
void __fastcall TTMainForm::FitExecute(TObject *Sender)
{
    //光顺
}
//---------------------------------------------------------------------------
//求三角形外心
int TTMainForm::GetExternPt(MyPoint * p1, MyPoint * p2, MyPoint * p3,Triangle *t)
{
    /*
    根据向量内积方程
    OA'*BC = 0 (A'为BC边中点)
    OB'*AC = 0 (C'为AC边中点)
    设各点坐标为 A(x1,y1),B(x2,y2),C(x3,y3),O(x0,y0)则方程可化解为
    (x2-x3)x0+(y2-y3)y0 = (x2*x2-x3*x3)/2+(y2*y2-y3*y3)/2
    (x1-x3)x0+(y1-y3)y0 = (x1*x1-x3*x3)/2+(y1*y1-y3*y3)/2
    上面方程可用矩阵法解
    |A|=|x2-x3 y2-y3|
        |x1-x3 y1-y3|
    |B|= |(x2*x2-x3*x3)/2+(y2*y2-y3*y3)/2 y2-y3|
         |(x1*x1-x3*x3)/2+(y1*y1-y3*y3)/2 y1-y3|
    |C|= |x2-x3 (x2*x2-x3*x3)/2+(y2*y2-y3*y3)/2|
         |x1-x3 (x1*x1-x3*x3)/2+(y1*y1-y3*y3)/2|
    x0 = |B|/|A|;
    y0 = |C|/|A|;
    */
    float x1,x2,x3,y1,y2,y3,A,B,C;
    x1 = p1->X;
    y1 = p1->Y;
    x2 = p2->X;
    y2 = p2->Y;
    x3 = p3->X;
    y3 = p3->Y;
    A = (x2-x3)*(y1-y3)-(x1-x3)*(y2-y3);
    B = (y1-y3)*(x2*x2-x3*x3+y2*y2-y3*y3)/2-(y2-y3)*(x1*x1-x3*x3+y1*y1-y3*y3)/2;
    C = (x2-x3)*(x1*x1-x3*x3+y1*y1-y3*y3)/2-(x1-x3)*(x2*x2-x3*x3+y2*y2-y3*y3)/2;
    if(A == 0)
    {
        return 0;
    }
    else
    {
        t->X = B/A;
        t->Y = C/A;
        t->R = (t->X-x1)*(t->X-x1)+(t->Y-y1)*(t->Y-y1);
        t->P[0] = p1;
        t->P[1] = p2;
        t->P[2] = p3;
        return 1;
    }
}

void __fastcall TTMainForm::FormMouseWheel(TObject *Sender,
      TShiftState Shift, int WheelDelta, TPoint &MousePos, bool &Handled)
{
    if(WheelDelta > 0)
    {
        Scale = Scale*0.8;
    }
    else
    {
        Scale = Scale*1.25;
    }
    ReDraw();
}
//---------------------------------------------------------------------------

int TTMainForm::Direction(MyPoint * p1, MyPoint * p2, MyPoint * p3)
{
    float d;
    d = p1->X*p2->Y+p1->Y*p3->X+p2->X*p3->Y-p1->X*p3->Y-p1->Y*p2->X-p2->Y*p3->X;
    if(d > 0.000001)
    {
        return 1;
    }
    if(d < -0.000001)
    {
        return -1;
    }
    return 0;
}

int TTMainForm::Cross(MyPoint * p1, MyPoint * p2, MyPoint * p3, MyPoint * p4)
{
    //TODO: Add your source code here
    /*
    判断线段p1p2和线段p3p4是否相交
    可得两线段所在直线方程为：
    p1p2: y-y1 = (y1-y2)/(x1-x2) *(x-x1)
    p3p4: y-y3 = (y3-y4)/(x3-x4) *(x-x3)
    可变换为：
    p1p2: (x1-x2)*y-(y1-y2)*x = (x1-x2)*y1-(y1-y2)*x1
    p3p4: (x3-x4)*y-(y3-y4)*x = (x3-x4)*y3-(y3-y4)*x3
    以上方程组可用矩阵法解
    A = |x1-x2 y2-y1|
        |x3-x4 y4-y3|
    B = |x1-x2 (x1-x2)*y1-(y1-y2)*x1|
        |x3-x4 (x3-x4)*y3-(y3-y4)*x3|
    C = |(x1-x2)*y1-(y1-y2)*x1 y2-y1|
        |(x3-x4)*y3-(y3-y4)*x3 y4-y3|
    x = B/A
    y = C/A;
    如果
    (x-x1)*(x-x2) < 0
    (x-x3)*(x-x4) < 0
    (y-y1)*(y-y2) < 0
    (y-y3)*(y-y4) < 0
    则两线段有交点
    */
    float x1,x2,x3,x4,y1,y2,y3,y4;
    x1 = p1->X;
    y1 = p1->Y;              
    x2 = p2->X;
    y2 = p2->Y;
    x3 = p3->X;
    y3 = p3->Y;
    x4 = p4->X;
    y4 = p4->Y;
    float A,B,C,x,y;
    A = (x1-x2)*(y4-y3)-(x3-x4)*(y2-y1);
    B = (x1-x2)*((x3-x4)*y3-(y3-y4)*x3)-(x3-x4)*((x1-x2)*y1-(y1-y2)*x1);
    C = ((x1-x2)*y1-(y1-y2)*x1)*(y4-y3)-((x3-x4)*y3-(y3-y4)*x3)*(y2-y1);
    if(0 == A)
    {
        return 0;
    }
    x = B/A;
    y = C/A;
    if((x-x1)*(x-x2) < 0 && (x-x3)*(x-x4) < 0 && (y-y1)*(y-y2) < 0 && (y-y3)*(y-y4) < 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
Edge * TTMainForm::FindEdge(MyPoint * p1, MyPoint * p2,TList *List)
{
    int i;
    Edge *e;
    for(i=0; i<List->Count; i++)
    {
        e = (Edge*)List->Items[i];
        if(e->First == p1 && e->Last == p2)
        {
            return e;
        }
        if(e->First == p2 && e->Last == p1)
        {
            return e;
        }
    }
    return NULL;
}