삼각형 메쉬로 주어진 도형을 다음의 세 종으로 분류하고 특성을 계산하라


1. 도형이 방향이 있고 닫혀있는 경우 (closed and oriented, 구면, 토러스 등)

내부 부피와 표면적을 구하라


2. 도형이 방향이 있고 닫혀있지 않은 경우 (oriented, 반구 등)

표면적과 둘레의 길이를 구하라


3. 도형이 방향이 없는 경우 (unoriented, 뫼비우스 띠 등)

표면적과 둘레의 길이를 구하라


입력 포맷

첫 줄에서 정점의 갯수 m을 입력받는다.

이후 m개의 정점의 좌표를 입력 받는다.

다음 줄에서 삼각형 면의 갯수 n을 입력받는다.

이후 n개의 삼각형 면을 입력 받는다. 삼각형은 정점 인덱스의 삼중쌍 (v0, v1, v2) 이다.

정점의 인덱스는 0부터 시작한다.


입력 예시 (사면체)

4 (0.0, 0.0, 0.0) (1.0, 0.0, 0.0) (0.0, 1.0, 0.0) (0.0, 0.0, 1.0) 4 (0, 2, 1) (0, 1, 3) (0, 3, 2) (1, 2, 3)


입출력 예시

https://gist.github.com/damhiya/6c12e8b0edd9a7e9e9f6c6e53ecbd1a0

mesh.jlGitHub Gist: instantly share code, notes, and snippets.gist.github.com


> julia mesh.jl tetrahedron | ./Main closed and oriented volume : 0.16666666666666666 area : 2.3660254037844384 > julia mesh.jl torus | ./Main closed and oriented volume : 197.13246713805412 area : 394.5569513126211 > julia mesh.jl hemisphere | ./Main oriented area : 6.280924884315729 perimeter : 6.282151815625658 > julia mesh.jl moebius | ./Main unoriented area : 6.3506731194187935 perimeter : 13.004505814286443


세부사항 및 힌트

1. 주어지는 메쉬는 다음과 같은 조건을 만족한다.

모든 삼각형은 넓이가 0보다 크다.

서로 다른 두 삼각형은 최대 2개의 정점과 1개의 변을 공유한다.

정점을 공유하지 않는 삼각형은 만나지 않는다.

한 변을 공유하는 삼각형은 최대 2개 있다.


2. 삼각형이 방향이 있음에 주의하라
예를 들어 {0, 1, 2} 3개의 정점이 있을 때

(0, 1, 2), (1, 2, 0), (2, 0, 1) 3개가 같은 방향의 삼각형이고

(1, 0, 2), (2, 1, 0), (0, 2, 1) 3개가 같은 방향의 삼각형이다.
(0, 1, 2)와 (1,0,2)는 서로 반대방향의 삼각형이다.


3. 도형이 방향이 있는지 여부를 판단하는 방법.

한 변을 공유하는 삼각형의 모든 쌍들에 대해, 그 변에 대한 방향이 서로 반대인 경우 방향이 잘 주어졌다고 한다. (oriented)

다음의 예시를 보자.


두 삼각형 (0,1,2), (2,1,3) 각각의 경계는

(0,1,2) : (0,1), (1,2), (2,0)

(2,1,3) : (2,1), (1,3), (3,2)

이다.

이때 방향이 서로 반대인 변은 서로 상쇄된다. 즉 (1,2)와 (2,1) 이 서로 상쇄되어 전체 도형의 경계는

(0,1) (1,3) (3,2) (2,0) 으로 구성된다.

이 때 남은 모든 변들이 서로 다르므로 이 도형은 방향이 있는 도형이다.


삼각형이 (0,1,2) (1,2,3) 인 경우 경계는

(0,1,2) : (0,1), (1,2) (2,0)

(1,2,3) : (1,2), (2,3) (3,1)

이므로 전체 도형의 경계는

(0,1) (1,2) (1,2) (2,3), (3,1) (2,0) 이다.
여기서 (1,2) 가 중복되므로 이 도형은 제대로된 방향이 할당되지 않았다.
이와 같이 제대로된 방향이 할당되지 않은 경우, 방향이 없는 도형으로 취급한다. (unoriented)


모든 변들이 서로 상쇄되어 경계가 없는 경우, 그 곡면은 폐곡면(closed) 이다.


4. 방향이 없는 도형의 둘레의 길이

방향이 없는 도형의 둘레를 생각할 때는 같은 방향의 변도 서로 소거해야 한다.

(뫼비우스의 띠를 생각해보라.)


5. 도형의 방향은 주어졌다고 생각한다.

구면은 방향을 줄 수 있는 (orientable) 도형이지만, 주어진 메쉬에서 각 삼각형에 대한 방향이 올바르지 않게 할당 되었을 수 있다.

이 경우 올바른 방향 할당을 직접 찾을 필요 없이 방향이 없는 도형으로 취급하라.


(추가문제 : 주어진 메쉬에 올바른 방향을 할당할 수 있는지 여부를 (orientability) 조사하라)


6. 내부 부피를 구하는 방법


https://medium.com/@evanwallace/easy-scalable-text-rendering-on-the-gpu-c3f4d782c5ac

Easy Scalable Text Rendering on the GPUThis post describes the text rendering algorithm I used on thetamath.com, a GPU-powered 2D equation renderer I wrote for fun last December…medium.com


여기 있는 움짤을 보면 힌트가 될지도...








나는 왜 이 문제를 지금 내는가?

시험기간이니까

22


학식깃붕군/양들은 주말동안 깃갤 문제 풀고 중간고사 잘 보시기 바랍니다

학식이 아닌 깃붕군/양들도 문제를 풀며 즐거운 시간 보내시기 바랍니다