一种低效但逻辑简单清晰的Delaunay三角网生成算法(2)

//判断三个点能否组成一个三角形
BOOL CMyDelaunay::IsPtsBuildTriangle(PT* pt1, PT* pt2, PT* pt3)
{
    double offset_x1 = pt2->x - pt1->x;
    double offset_x2 = pt3->x - pt2->x;
    double offset_y1 = pt2->y - pt1->y;
    double offset_y2 = pt3->y - pt2->y;

if((fabs(offset_x1) < EP) && (fabs(offset_x2) < EP))    //竖直
    {
        return FALSE;
    }
   
    if(fabs(offset_x1) > EP && fabs(offset_x2) > EP)
    {
        if(fabs(offset_y1/offset_x1 - offset_y2/offset_x2) < EP)
            return FALSE;
    }
   
    return TRUE;
}

void CMyDelaunay::BuildDelaunayEx(vector<PT>& vecPT, vector<TRIANGLE>& vecTriangleWork)
{
    int nSize = vecPT.size();
    if(nSize < 3)
        return;
   
    for(int i = 0; i < nSize - 2; ++i)
    {
        for(int j = i + 1;  j < nSize - 1; ++j)
        {
            for(int k = j + 1; k < nSize; ++k)
            {
                PT* pt1 = &vecPT[i];
                PT* pt2 = &vecPT[j];
                PT* pt3 = &vecPT[k];
                BOOL bFind = TRUE;
                for(int m = 0; m < nSize; ++m)
                {
                    PT* pt = &vecPT[m];
                    if(pt != pt1 && pt != pt2 && pt != pt3 && IsPtsBuildTriangle(pt1, pt2, pt3))
                    {
                        TRIANGLE tri(pt1, pt2, pt3);
                        if(tri.IsPtInCircle(pt))
                        {
                            bFind = FALSE;
                            break;
                        }
                    }
                }
                if(bFind)
                { 
                    vecTriangleWork.push_back(tri); 
                }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/1c0c44e95653c858ead954469fbb3b23.html