설명
원 채우기는 내부가 분리된 원의 모음입니다. 평면에 채워져 있는 원의 접촉 그래프는 항상 평면 그래프이며, 접선 원 중심을 연결하는 선분을 갖는 원 중심 세트 접촉 그래프의 평면 임베딩을 형성합니다. Koebe-Andreev-Thurston 정리는 그 반대도 사실임을 나타냅니다. 연결된 모든 단순 평면 그래프 G에 대해 원 채우기가 있습니다. 접촉 그래프가 G와 동형인 평면. 우리는 원을 구성하기 위해 삼각형 안의 n-3 임의 점의 삼각측량을 사용합니다. 포장 인스턴스. 유사점(변환, 회전, 크기 조정)에 유의하세요. 일부 좌표를 고정하거나 적절한 시작 값을 선택하여 제외해야 합니다. 이러한 방식으로 완전한 세분화 솔버에 대한 멋진 기하학적 문제가 생성됩니다.
대형 모델 유형 :QCP
카테고리 : 슬롯 게임 모델 라이브러리
메인 파일 : tricp.gms
$title 삼각 그래프 원 채우기(TRICP,SEQ=395)
$onText
원 채우기는 내부가 분리된 원의 모음입니다.
평면에 채워져 있는 원의 접촉 그래프는 항상 평면 그래프이며,
접선 원 중심을 연결하는 선분을 갖는 원 중심 세트
접촉 그래프의 평면 임베딩을 형성합니다.
Koebe-Andreev-Thurston 정리는 그 반대도 사실임을 나타냅니다.
연결된 모든 단순 평면 그래프 G에 대해 원 채우기가 있습니다.
접촉 그래프가 G와 동형인 평면.
우리는 원을 구성하기 위해 삼각형 안의 n-3 임의 점의 삼각측량을 사용합니다.
포장 인스턴스. 유사점(변환, 회전, 크기 조정)에 유의하세요.
일부 좌표를 고정하거나 적절한 시작 값을 선택하여 제외해야 합니다.
이러한 방식으로 완전한 세분화 솔버에 대한 멋진 기하학적 문제가 생성됩니다.
Ch. Fuenfzig, D. Michelucci, S. Foufou: 부동 소수점의 비선형 시스템 솔버
LP 축소를 이용한 산술, 기하학 및 물리에 관한 SIAM/ACM 공동 컨퍼런스
모델링 2009.
기여자: Christoph Fuenfzig (c.fuenfzig@gmx.de)
키워드: 2차 제약 조건 프로그래밍, 원 채우기 문제, KoebeAndreevThurston
정리, 단순 평면 그래프, 그래프 이론
$offText
세트
n '노드' / n0*n19 /
e(n,n) '모서리' / n0.(n1,n2,n3,n5,n6,n7,n9,n11,n19)
n1.(n2,n3)
n2.(n3,n4,n7)
n3.(n4,n5)
n4.(n5,n6,n7)
n5.n6
n6.(n7,n8)
n7.(n8,n9)
n6.(n10,n11)
n8.(n9,n10)
n9.(n10,n11,n12,n13,n14,n15,n18,n19)
n10.n11
n11.(n12,n13,n14,n16,n17,n19)
n12.n13
n13.n14
n14.(n15,n16)
n15.(n16,n17,n18)
n16.n17
n17.(n18,n19)
n18.n19 /
k '차원' / k0*k1 /;
별칭 (n,i,j), (k,kp);
$onEps
매개변수 fx(n,k) / n0 .k0 10, n0 .k1 10
n19.k0 20, n19.k1 10
n9 .k0 15, n9 .k1 20 /;
$offEps
변수
x(n,k) '좌표'
r(n) '반경'
slp(n,n) '양성 여유'
sln(n,n) '음의 여유 시간'
z '타당성 조사자'
obj '객관적';
양수 변수 x, r, z, slp, sln;
스칼라 myScale / 1e2 /;
x.up(n,k) = myScale*smax((i,kp),fx(i,kp));
x.fx(n,k)$fx(n,k) = myScale*fx(n,k);
r.lo(n) = myScale*0.001;
* 임의의 시작점
x.l(n,k) = myScale*uniform(0,smax(i,fx(i,k)));
r.l(n) = myScale*1;
방정식
defobj '목표'
eq1(n,n) '이웃 노드 키스'
eq2(n,n) '인접하지 않은 노드가 분리되었습니다';
eq1(e(i,j))..
sum(k, sqr(x(i,k) - x(j,k))) =e= sqr(r(i) + r(j)) + slp(e) - sln(e);
eq2(i,j)$(e(i,j) 및 ord(i) < ord(j)가 아님)..
합계(k, sqr(x(i,k) - x(j,k))) =g= sqr(r(i) + r(j)) - z;
디포브..
obj =e= 100*z + sum(e, slp(e) + sln(e));
모델 cp / 모두 /;
옵션 optCr = 1e-6, optCa = 1e-6;
obj를 최소화하는 qcp를 사용하여 cp를 해결합니다.
* EPS로 출력 포장
파일 fcp / 'cp.eps' /;
fcp.ap = 1;
fcp.nd = 4;
fcp를 넣어;
if(cp.modelStat <= 2,
x.l(n,k) = x.l(n,k)/myScale;
r.l(n) = r.l(n)/myScale;
루프(n,
회색으로 '% 주석'을 입력하세요.
/ '0.4 세트회색'
/ '새 경로'
/ x.l(n,'k0'):0:4 ' ' x.l(n,'k1'):0:4 ' 이동'
/ 'currentpoint exch 0.1 2 div sub exch moveto'
/ '(' (ord(n) - 1):0:0 ') 표시'
/ '% 빨간색으로 원 그리기'
/ '1 0 0 setrgbcolor'
/ '새 경로'
/ x.l(n,'k0'):0:4 ' ' x.l(n,'k1'):0:4 ' ' r.l(n):0:4 ' 0 360 호 스트로크'
/ '뇌졸중' /;
);
'쇼페이지'를 입력하세요.
);
$onEchoV > cp.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Creator: EPSDevice 클래스
%%제목: template.eps
%%BoundingBox: 0 0 501 501
%%끝댓글
/오른쪽
/InputDict 8 사전 정의
입력사전 시작
/Y4 교환 def
/X4 교환 정의
/Y3 교환 def
/X3 교환 정의
/Y2 교환 def
/X2 교환 정의
/Y1 교환 def
/X1 교환 def
새로운 경로
X1 Y1 이동
X2 Y2 라인토
X3 Y3 라인토
X4 Y4 라인토
근접 경로
끝 데프
/cRect
/InputDict 9 사전 정의
입력사전 시작
/댓글 exch def
/Y4 교환 def
/X4 교환 정의
/Y3 교환 def
/X3 교환 정의
/Y2 교환 def
/X2 교환 정의
/Y1 교환 def
/X1 교환 def
새로운 경로
X1 Y1 이동
현재 글꼴 12 스케일 글꼴
코멘트 문자열 폭 팝
X3 X1 하위 교환 div 0.8 mul
Y3 Y1 하위 12div
1 인덱스 1 인덱스 lt exch if
gsave dup 스케일
코멘트 쇼
X1 Y1 주석 문자열 너비 retclip grestore
새로운 경로
X1 Y1 이동
X2 Y2 라인토
X3 Y3 라인토
X4 Y4 라인토
근접 경로
끝 데프
/설정글꼴
/InputDict 1 사전 정의
입력사전 시작
/크기 교환 def
/Helvetica findfont
크기 축척글꼴
setfont 끝 def
%% 끝 헤더
% 설정 좌표계 [10, 20]*[10, 20]
0 0 번역하다
48.0769 48.0769 스케일
-9.8 -9.8 번역
% 클리핑 상자 설정
새로운 경로
9.8 9.8 무브토
20.2 9.8 라인토
20.2 20.2 라인토
9.8 20.2 라인토
근접 경로
클립
회색 % 그리기 상자
0.01 설정선폭
0 세트회색
9.8 9.8 20.2 9.8 20.2 20.2 9.8 20.2 직사각형
뇌졸중
아래 %% 그림
0.02 세트라인폭
0.2 설정폰트
$offEcho