查找2D網格中節點/頂點的鄰居

Question

我有一個由節點和元素定義的2D網格。

結構中的節點的：節點ID，X位置，Y位置

的元件的結構：元素ID，節點1，節點2，節點3，節點2×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

將元素的頂點排列成閉合多邊形將是一件好事。頂點[1,2,4,5]不唯一定義第一個元素。從你的描述中可以看出，你的意思是這是一個有四個頂點的多邊形（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 

如果你不能確定頂點的訂單，比你必須檢查有關元素自相交，並重新排列頂點，以解決交叉點。

用這種數據很容易找到給定節點的所有鄰居。如果元素包含給定節點，則通過所有元素，而不是該元素中有兩個鄰居，即列表中前後的頂點。

對於節點5，在第一個元素有鄰居2和4，在第二個元素有鄰居6和2，...

如果會有很多這樣的查詢，比它更好在不同的結構中提取連接信息。這可以是將節點映射到它的鄰居集合的映射。要做到這一點，通過所有元素，併爲每個元素頂點添加兩個鄰居節點的列表中。