Alpha Shape

In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. https://en.wikipedia.org/wiki/Alpha_shape

class AlphaShape {
    double alpha;
    std::set<std::pair<int,int>> Border; //pair;
public:
    AlphaShape() { }
    AlphaShape(CDC *pDC, std::vector<CfPt>& Q, const double radius = 50) {
        if (Q.size() < 2) return;
        alpha = radius;
        const double alphaSq = alpha * alpha;
        const double diameter = 2 * alpha;
        for (int i = 0; i < Q.size(); ++i) {
            const CfPt &p = Q[i];
            for (int j = 0; j < i; ++j) {
                const CfPt &q = Q[j];
                if (q == p) continue;
                const double edist = p.Dist(q); 
                // 두 점의 사잇거리가 지름보다 크면 edge가 안됨;
                if (edist > diameter) continue;                     

                // 두 점을 원주에 포함하는 반지름 alpha인 두 원을 찾음;
                // note that c1 == c2 if edist == diameter;
                double scale = sqrt(alphaSq - (edist/2)*(edist/2));
                CfPt n = (q - p) * scale / edist;
                CfPt mid = (q + p) / 2;
                CfPt c1 = mid + n.Rot90(); // CfPt(mid.x - ny, mid.y + nx);
                CfPt c2 = mid - n.Rot90(); // CfPt(mid.x + ny, mid.y - nx);

                // alpha shape의 변이 되기 위해서는 두 원 중 하나는
                // 다른 점들을 포함하지 않아야 함;
                bool c1_empty = true, c2_empty = true;
                for (int k = Q.size(); (k-->0) && (c1_empty || c2_empty);) {
                    if (Q[k] == p|| Q[k]== q) continue; //i==k || j==k?
                    if (c1.DistSq(Q[k]) < alphaSq) c1_empty = false;
                    if (c2.DistSq(Q[k]) < alphaSq) c2_empty = false;            
                }

                if (c1_empty || c2_empty) {                  
                    if (c1_empty) drawCircle(pDC, c1);
                    if (c2_empty) drawCircle(pDC, c2);
                    // draw edge;
                    drawEdge(pDC, p, q);
                    //Border.insert(std::make_pair(i,j));
                }
            }
        }
    } 
    void drawEdge(CDC *pDC, const CfPt &p, const CfPt &q) {
        CPen pen(PS_SOLID,2,RGB(255,0,255)); //magenta;
        CPen *pOld = pDC->SelectObject(&pen);
        pDC->MoveTo(p); pDC->LineTo(q);
        pDC->SelectObject(pOld);
    }
    void drawCircle(CDC *pDC, const CfPt &c) {
        CPen pen(PS_SOLID, 1, RGB(0,200,200));
        CPen *pOld = pDC->SelectObject(&pen);
        pDC->SelectObject(GetStockObject(NULL_BRUSH));
        pDC->Ellipse(c.x-alpha, c.y-alpha, c.x+alpha, c.y+alpha);
        pDC->SelectObject(pOld);		
    }
    std::set<std::pair<int,int>> getBorder() {
        return Border;
    }
};