Ritter's算法如下:
1.從點集中隨機選出兩個點作為直徑對圓進行初始化。
2.判斷下一個點p是否在圓中,如果在則繼續本步驟,如果不在則進行步驟3。
3.使用p作為新圓的一個邊界點,另一個邊界點為距離p最遠的圓上的點(舊圓心和新的點p連線方向的向量,直徑d+r),使用這兩個點作為直徑構造新圓。
4.繼續步驟2,直到遍歷完所有點。
n=100;p=rand(n,2); %100個點的坐標,二維坐標p1=p(1,:);p2=p(2,:);r=sqrt((p1(1)-p2(1))^2+(p1(2)-p2(2))^2)/2; %兩點距離的一半是半徑cenp=(p1+p2)/2; %圓心的坐標for i=3:n newp=p(i,:); d=sqrt((cenp(1)-newp(1))^2+(cenp(2)-newp(2))^2); if d>r r=(r+d)/2; cenp=cenp+(d-r)/d*(newp-cenp); %(newp-cenp)/d是這個方向上的單位向量,這個新的圓不是最優的,是直徑d+原先r的,新直徑就是r=(r+d)/2 end endhold on;plot(p(:,1),p(:,2),'o');x0=cenp(1); %迭代出來的最后的圓心坐標y0=cenp(2); %迭代出來的最后的圓心坐標theta=0:0.01:2*pi; %參數theta,用來極坐標畫圓圈用x=x0+r*cos(theta);y=y0+r*sin(theta);plot(x,y,'-',x0,y0,'.'); %把圓周上的點用-直線段依次連接起來,正多邊形無限逼近圓,步長0.01很小,最終的圓心(x0,y0)用一點句號點標出來axis equal %橫縱坐標刻度是一樣比例的,防止圓變形成橢圓。axis square命令意思是畫出來正方形的坐標圖
新聞熱點
疑難解答