>
>평면에 점 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]);
댓글 0
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
50 | 어느 입자 논문에서 | 김휘 | 2009.02.05 | 20817 |
49 | 곡면 fitting | 김휘 | 2009.01.22 | 11515 |
» | [re] subproblem에서 막혔음..도와주실 분.. | 김휘 | 2008.12.26 | 10707 |
47 | [re] subproblem에서 막혔음..도와주실 분.. | 김휘 | 2008.12.26 | 13423 |
46 | subproblem에서 막혔음..도와주실 분.. | 김휘 | 2008.12.25 | 12333 |
45 | Transformed medial의 Hamiltonian 식 증명 | 김휘 | 2008.10.30 | 12411 |
44 | 변환광학에서의 Hamiltonian | 김휘 | 2008.10.29 | 12561 |
43 | 타운스와 블롬버겐 | 박정현 | 2008.10.28 | 12519 |
42 | 페르마의 마지막 정리..와 광학 | 김휘 | 2008.10.02 | 12593 |
41 | slow light의 상대속도 [1] | 김휘 | 2008.09.24 | 11501 |