728x90

$$\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 = 1; iter < maxiters; iter++) { 
        // find the furthest point from (cx, cy);
        maxdist2 = 0;
        id = 0;
        for (int i = pts.size() - 1; i >= 0; --i) {
            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

 

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

Graham Scan  (0) 2021.03.28
Jarvis March  (0) 2021.03.26
Approximate Minimum Enclosing Circle  (1) 2021.03.18
Minimum Bounding Rectangle  (0) 2021.03.15
Minimum Enclosing Circle  (0) 2021.03.01
단순 다각형 만들기  (0) 2021.01.25
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2021.03.20 21:51 신고  댓글주소  수정/삭제  댓글쓰기

    이게 말로만 듣던 최소 외접원인가요?