정점이 서페이스를 참조하는 그래프의 볼륨 식별

Question

지난 며칠 동안 나를 괴롭혔던 질문이 있습니다. 제 동료는 이것이 잘 연구 된 문제라고 생각하지만 온라인에서 어떤 논문도 찾을 수 없었습니다. 내가 사용한 주요 단어가 잘못되었습니다.) 각 꼭지점이 서페이스에 해당하고 해당 서페이스가 한 줄로 만나는 경우 두 꼭지점 사이에 모서리가있는 그래프가있는 경우 결합되어 닫힌 볼륨을 형성하는 서페이스를 어떻게 식별 할 수 있습니까?

그래서 예를 들어 (1 ~ 6 번호 표면) 큐브에 대한 인접리스트는 다음과 같이 보일 수 있습니다 : 일부 표면이 무료 - 경우

이 정보 외에도

1 -> [4,2,5,6] 
2 -> [1,3,5,6] 
3 -> [2,4,5,6] 
4 -> [3,1,5,6] 
5 -> [1,2,3,4] 
6 -> [1,2,3,4] 

, 나 또한 알고 모서리 (즉, 그 모서리는 다른 서페이스와 공유되지 않습니다). 자유 가장자리가있는 서페이스가 캐비티 경계의 일부가 될 수 없기 때문에 이러한 서페이스를 즉시 제외 할 수 있습니다. 또한, 두 개의 표면이 만나면 경계에서 깨끗하게 만나게됩니다. 아무런 불의 소리도 없습니다.

내가 할 수 있기를 희망하는 것은 구멍이 있다는 것을 식별하는 것뿐만 아니라 표면과 표면 사이의 매핑을 출력하는 것입니다. 그들이 포함하는 충치.

----------- 
|   | 
|   | 
|   | 
--------------------- 
      |   | 
      |   | 
      |   | 
      ----------- 

는 ...이 표면 1- 가정 원하는 출력 할 것이다 : 예를 들어, 에지에서 만나는 두 조각의 경우 (화상을 배치하는 것만으로는 충분하지 평판, 그래서 여기 측면도이다) 6 큐브 ONE을하고 7-12 큐브 두 구성 : 다른 사람이 네 개의 이웃을 가지고 있지만,이 경우, 일부 표면이 그래프에서 SIX 이웃을

Volume 1 -> [1,2,3,4,5,6] 
Volume 2 -> [7,8,9,10,11,12] 

참고.

도움이 될 것입니다.

Answer 1

예,이 영역을 계산 토폴로지라고합니다. 그 주요 대상은 상 동성 그룹 (H1은 1 차원 가장자리로 고리가 형성되고 H2는 2 차원으로 말하면 면이입니다.)로 알려진 대수 그룹의 루프입니다.

상 동성 그룹 매트릭스을 형성함으로써 이러한 그룹을 분석 할 수있다. 일부 쿼리의 경우 H1 및 H2 행렬이 모두 필요합니다.

매트릭스를 독립적 인 블록으로 재 배열 할 수 있다면 형상이 상호 작용하지 않는다는 것을 의미합니다. 단일 블록 상 동성 매트릭스가 N 순위를 갖는 경우, 형상이 N 개의 공동 (홀)을 갖는다는 것을 의미합니다. 정육면체와 같은 단순한 형태는 0 개의 구멍을 가지고 있고, 원환 체는 1 등을 가지고있다.

이러한 계산을 위해 C++ 및 MATLAB 오픈 소스 패키지를 찾을 수 있습니다.

희망적인 키워드를 알려주세요.