查找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，...

如果会有很多这样的查询，比它更好在不同的结构中提取连接信息。这可以是将节点映射到它的邻居集合的映射。要做到这一点，通过所有元素，并为每个元素顶点添加两个邻居节点的列表中。