>
>평면에 점 N개를 random 하게 뿌립니다.
>
>1. 점 N개를 포함하는 가장 작은 볼록다각형을 구하는 컴퓨터 알고리즘
>2. 점 N개를 포함하는 가장 작은 다각형을 구하는 컴퓨터 알고리즘 (다각형의 변은 서로 교차하지 않아야 한다.)
>
>직접적인 답변 뿐만 아니라 참고문헌 환영!

완전하진 않은데 시간이 없어 일단 쓰기로 해본 코드
(개선 사항 조언 환영)


% extraction boundary

clear all;
clc;
close all;

%% Distributing N random points
N=500;
X=rand(N,1);
Y=rand(N,1);

xc=sum(X)/N;
yc=sum(Y)/N;

X=X-xc;
Y=Y-yc;

for k=1:N

   % figure(1); hold on; plot3([X(k) X(k)],[Y(k) Y(k)],[0 0],'r+');

    r(k)=( X(k)^2+Y(k)^2 )^0.5;
    cost=X(k)/r(k);
    sint=Y(k)/r(k);
    
    th(k)=return_angle(cost,sint);
    
    
end;

[at bt]=sort(th);

for k=1:N
    
    sr(k)=r(bt(k));
    sth(k)=th(bt(k));
    sX(k)=X(bt(k));
    sY(k)=Y(bt(k));
    
    figure(2); hold on; plot3([sX(k) sX(k)],[sY(k),sY(k)],[0 0], 'b+' );
    
end;


%% Enclosing the distributing N random points with a N-facet-polygon
M=20;
th_a=[0:2*pi/M:2*pi];



srt_th=zeros(1,M);
srt_cnt=zeros(M,1);
for k=1:N    % point index
     for l=1:M  % azimuth angle grid
    
         if th_a(l)<= sth(k) & sth(k) < th_a(l+1)
           srt_cnt(l)=srt_cnt(l)+1;
           break;
         end;
            
     end; % for l
    
     srt_th(srt_cnt(l),l)=k;
    
end; % for k


% maximum distance 골라내기
srt_max=zeros(M,1);

for l=1:M
    
    if srt_cnt(l) == 0
    srt_max(l)=0;
    else
            clear Rs;
            for kk=1:srt_cnt(l)
            
                s_ind=srt_th(kk,l);
                Rs(kk)=( sX(s_ind)^2+sY(s_ind)^2 )^0.5;
                
            end; % for kk
            
            [atmp btmp]=max(Rs);
            srt_max(l)=srt_th(btmp,l);
            
    end;
end;


pr_ind=0;
clear srt_max_tmp;
for k=1:length(srt_max)
  
      
    if srt_max(k) == 0
        ;
    else
        pr_ind=pr_ind+1;
        srt_max_tmp(pr_ind)=srt_max(k);
    end;
  
    
end;

for k=1:length(srt_max_tmp)-1
    ind1=srt_max_tmp(k);
    ind2=srt_max_tmp(k+1);
    figure(2); hold on;
    plot3([sX(ind1) sX(ind2)],[sY(ind1) sY(ind2)],[0 0]);
end;

  ind1=srt_max_tmp(end);
  ind2=srt_max_tmp(1);
  figure(2); hold on;
  plot3([sX(ind1) sX(ind2)],[sY(ind1) sY(ind2)],[0 0]);