Поиск соседей узла/вершины в 2D-сетке

Question

У меня есть 2D-сетка, определяемая узлами и элементами.

Структура узла: Node ID, X позиция, Y позиция

Структура элемента: Элемент ID, узел 1, узел 2, узел 3, узел 4

Пример 2х2 элементов сетки :

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.

* Примечание. Этот упрощённый пример элемента 2х2 для пояснения предлагает, что в сетках, с которыми я имею дело, может содержаться несколько тысяч узлов и элементов. Я также смотрел на некоторые концепции теории графов, но я не уверен, какой может быть правильный путь.

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, ...

Если будет много запросов такого рода, чем лучше чтобы сделать информацию о подключении экстракта в отдельной структуре. Это может быть карта, которая сопоставляет узел с множеством его соседей. Чтобы сделать это, пройдите через все элементы, и для каждой вершины элемента добавьте двух соседей в список узлов.