2D 메쉬에서 노드/버텍스의 이웃 찾기

Question

노드와 요소로 정의 된 2D 메쉬가 있습니다.

노드의

구조 : 기지국 ID, X 위치, Y 위치

소자의 구조 : 요소 ID, 노드 1, 노드 2, 노드 3, 노드 2 × 소자 4

예 메쉬 :

Nodes: 

ID X Y 
    1 0 0 
    2 0 1 
    3 0 2 
    4 1 0 
    5 1 1 
    6 1 2 
    7 2 0 
    8 2 1 
    9 2 2 

Elements: 

ID N1 N2 N3 N4 
    1 1 2 4 5 
    2 2 3 5 6 
    3 4 5 7 8 
    4 5 6 8 9 

N7-----N8-----N9 
|  |  | 
| E3 | E4 | 
|  |  | 
N4-----N5-----N6 
|  |  | 
| E1 | E2 | 
|  |  | 
N1-----N2-----N3 

링크 된 목록에 노드와 요소가 모두 저장됩니다.

내 질문 : 임의로 선택된 노드에 대해 이웃 (노드)을 어떻게 찾을 수 있습니까?

예를 들어 N5의 이웃 노드는 N2, N4, N6 및 N8입니다.

* 참고 : 설명을 위해이 2x2 요소 메쉬 단순화 된 예제가 제안한 것처럼, 내가 다루고있는 메쉬에는 수천 개의 노드와 요소가 포함될 수 있습니다. 그래프 이론에 대한 몇 가지 개념을 살펴 보았지만 어느 것이 올바른 방법 일지 모르겠습니다.

Answer 1

닫힌 다각형을 만드는 방식으로 요소의 꼭지점을 정렬하는 것이 좋을 것입니다. Vertices [1, 2, 4, 5]는 첫 번째 요소를 고유하게 정의하지 않습니다. 귀하의 설명을 보면 4 개의 정점이 순서대로있는 다각형이라는 것을 알 수 있습니다 (1, 2, 5, 4). 그러나 그림이 없으면 퇴화 된 쿼드 (1, 2, 4, 5)가 될 수도 있습니다.

등 :

Elements: 

ID N1 N2 N3 N4 
    1 1 2 5 4 
    2 2 3 6 5 
    3 4 5 8 7 
    4 5 6 9 8 

당신은 당신이 요소 자체 교차점에 대해 확인하고 교차로를 해결하기 위해 정점의 순서를 변경하는 것보다, 정점 주문에 대해 확실하지 않은 경우.

이러한 종류의 데이터를 사용하면 주어진 노드의 모든 이웃을 쉽게 찾을 수 있습니다. 요소가 지정된 노드를 포함하고 있으면 모든 요소를 ​​통과합니다. 그 요소에 두 개의 이웃이 있고 목록의 앞과 뒤의 꼭지점이 있습니다. 이웃 (2, 4)가있는 두 번째 요소에 이웃 6 2있다 첫번째 요소 노드 5

, ...이 종류의 리퀘스트의 많이있을 경우

, 그것이 더 이상 별도의 구조로 연결 정보를 추출합니다. 지도 노드를 이웃 집합으로 매핑 할 수 있습니다. 이를 만들기 위해서는 모든 요소를 ​​통과시키고 각 요소 정점에 대해 노드 목록에 두 개의 이웃을 추가합니다.