c# - 在大列表中找到彼此接近的点

Question

我有一个结构节点的大列表(如 300000 个元素)，其中节点定义为

public struct Node
{
    public int nid;
    public double x, y, z;
}

我想知道哪些节点彼此靠近一定数量(在称为间隙的代码中)，以便将元素组织成集合。请注意，对于给定的节点分布，每个节点只属于一个集合。

我尝试过这种方式，循环每个节点并使用 Linq 查询和 3d 空间中两点之间距离的经典公式寻找它的邻居，但它真的很慢。

有什么建议吗？提前致谢。

List<Node> nList;
[...]

for (int i = 0; i < nList.Count; i++) // cycles through all nodes in list
{
    Node nodo_old = nList[i]; // current node

    List<Node> nset = nList.Where(n => (Math.Sqrt(Math.Pow((n.x - nodo_old.x),2) + Math.Pow((n.y - nodo_old.y), 2) + Math.Pow((n.z - nodo_old.z), 2)) <= gap)).ToList();

    [...]  // now nset contains a list of neighbour nodes
}

Answer 1

该算法删除已检查的节点以减少处理时间。我没有尝试解决您的问题，但我相信它会对您有所帮助，因为我在另一个场景中对其进行了测试并且它运行良好。

// to hold sets of neighbour nodes
Dictionary<int, List<Node>> relatedCollectionsDictionary = new Dictionary<int, List<Node>>();
int index = 0;

List<Node> nList;

while (nList.Any())
{
    var relatedCollection = nList.Where(n => (Math.Sqrt(Math.Pow((n.x - nList.First().x), 2) + Math.Pow((n.y - nList.First().y), 2) + Math.Pow((n.z - nList.First().z), 2)) <= gap));

    List<Node> relatedCollectionList = relatedCollection.ToList();
    List<Node> relatedCollectionListForDictionary = relatedCollection.ToList();

    relatedCollectionsDictionary.Add(index++, relatedCollectionListForDictionary);

    while (relatedCollectionList.Any())
    {
        nList.Remove(relatedCollectionList.First());
        relatedCollectionList.RemoveAt(0);
    }
}

这个想法是你做很多处理并且每次都遍历所有节点。但是使用这种情况，您不会多次迭代任何项目。