三角镶嵌邻域查找优化：实现有序无重复的邻域搜索

Problem Description #

We have a triangular tessellation structure where we store the 3D coordinates of N triangles as an N×3×3 array (each triangle has 3 vertices, each with x/y/z coordinates). Our goal is to:

• Generate a neighbor mapping table where each triangle points to its adjacent triangles that share an edge.
• No duplicate counting: If triangle j is marked as a neighbor of triangle i, i should not be marked as a neighbor of j.
• The starting triangle (specified by index) will have exactly 3 neighbors, while all other triangles will have at most 2 neighbors.

Example Input #

import numpy as np
vertices = np.array([
    [[2.0, 1.0, 3.0],[3.0, 1.0, 2.0],[1.2, 2.5, -2.0]], 
    [[3.0, 1.0, 2.0],[1.0, 2.0, 3.0],[1.2, -2.5, -2.0]], 
    [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[3.0, 1.0, 2.0]], 
    [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[2.2, 2.0, 1.0]], 
    [[1.0, 2.0, 3.0],[2.2, 2.0, 1.0],[4.0, 1.0, 0.0]], 
    [[2.0, 1.0, 3.0],[2.2, 2.0, 1.0],[-4.0, 1.0, 0.0]]
])

Expected Output #

When starting from triangle index 2, the neighbor mapping should be:

neighbour = [[], [], [0, 1, 3], [4, 5], [], []]

Update & Key Requirements #

A previous BFS-based solution (from @Ajax1234) had an ambiguity: when the order of elements in the vertices array is swapped (but the underlying tessellation structure remains the same), the output order of neighbors differs. We need an efficient implementation that guarantees consistent output by following a fixed processing order:

1. First process all neighbors of the starting triangle.
2. Then process each neighbor in ascending index order (e.g., first index 0, then 1, then 3, etc.), ensuring that the output remains consistent regardless of non-structural array element swaps.

内容的提问来源于stack exchange，提问作者konstant