$$\underset{q \in P}{\text{max}}~|q - c| \le (1+\epsilon)R_P$$

$\epsilon=0.1$ (red=exact MEB)인 경우;

void ApproxMinBall(std::vector<CPoint> &pts, double epsilon, CfPt &center, double &radius) {
    double epsilonsq = epsilon * epsilon;
    int maxiters = int( 1 / epsilonsq );
    double maxdist2 = 0;
    int id = rand() % pts.size();
    center.x = pts[id].x; 
    center.y = pts[id].y;
    for (int iter = 0; iter < maxiters; iter++) { 
        // find the furthest point from (cx, cy);
        maxdist2 = 0;
        id = 0;
        for (int i = pts.size(); i-- > 0;) {
            double dx = pts[i].x - center.x, dy = pts[i].y - center.y;
            double dist2 = dx * dx + dy * dy;
            if (dist2 > maxdist2) {
                maxdist2 = dist2;
                id = i;
            }
        }
        // update center;
        center.x += (pts[id].x - center.x) / iter;
        center.y += (pts[id].y - center.y) / iter;
    }
    radius = sqrt(maxdist2);
}

kipl.tistory.com/300

 

Minimum Enclosing Circle

평면 위에서 주어진 점집합을 포함하는 가장 작은 원을 찾는 문제는 가장 단순하게는 임의의 두 점이 지름이 되는 원과 임의의 세 점이 만드는 외접원을 모두 조사하여 찾으면 된다. 따라서 O(n^4

kipl.tistory.com

 

728x90

'Computational Geometry' 카테고리의 다른 글

Graham Scan  (0) 2021.03.28
Jarvis March  (0) 2021.03.26
Minimum Bounding Rectangle  (3) 2021.03.15
Minimum Enclosing Circle  (0) 2021.03.01
Creating Simple Polygons  (0) 2021.01.25
Posted by helloktk
,