如何有效地将所有子数组与相关 ID 组合并删除所有重复对象

Question

我有一组对象集合。每个对象都有一个与之关联的唯一 ID。我需要一些帮助来找到一种方法，将所有相互关联的数组组合成一个数组。理想情况下，最终结果应该只有每个对象的一个实例。

这些对象被称为“模块”并且相互匹配，因为它们共享相同的坐标，因此相互接触。数据经常具有这种相关性，它并不完美，但适合用例。我已经将数据排列成集合数组，但我需要提取模块并仅列出每个模块的一个实例。这应该绘制出一串接一个角的模块。

结构示例...

[
[Module 1, Module 2],

[Module 2, Module 1, Module 3],

[Module 3, Module 2],

[Module 4, Module 5],

[Module 5, Module 4, Module 6, Module 8]
]

等等....每个模块都在一个对象中，格式如下

  {
"id": 0,
"coords": [
  [
    { "x": 539, "y": 408 },
    { "x": 594, "y": 414 }
  ],
  [
    { "x": 594, "y": 414 },
    { "x": 597, "y": 381 }
  ],
  [
    { "x": 597, "y": 381 },
    { "x": 543, "y": 375 }
  ],
  [
    { "x": 543, "y": 375 },
    { "x": 539, "y": 408 }
  ]
],
"center": { "x": 568.25, "y": 394.5 }}

这些模块在特定于每个模块的数组中“链接”在一起。 IE。模块 1 有自己的链，模块 2 有自己的链，很可能与模块 1 的链重叠...等等，n 个模块和 v 个链。

我正在寻找一种想法或方法来构建我的 _.reduce() 函数，以便我可以组合所有相互关联的链。理想情况下，最终产品将是一组数组，其中仅包含每个模块的一个实例。

按照前面的例子....它看起来像

[[1, 2, 3],[4,5,6,8],[7...],...]

我原以为您可以使用嵌套循环来搜索相关值，但我得到了一个令人讨厌的乒乓效果，它创建了很多重复项。有没有一种方法可以“边走边烧”或从内存中弹出数组条目，这样一旦我建立了一个链，它就不会循环返回？

附件是将坐标分类为对象并根据周围环境对它们进行分类的代码

        let testarray = []
        moduleobjects.forEach((firstmoduleobject,bigindex)=>{
            let matchedmodules = [firstmoduleobject]
            firstmoduleobject.coords.forEach(firstline=>{
                moduleobjects.forEach((object,index)=>{
                    if(matchedmodules.includes(object)){return}else{
                            object.coords.forEach(line=>{
                             if((line[1].x===firstline[0].x||line[1].x===firstline[1].x)&&(line[1].y===firstline[0].y||line[1].y===firstline[1].y)){
                                    console.log(line[1].x===firstline[0].x||firstline[1].x)
                                    matchedmodules.forEach(modules=>{
                                        if(modules.id===object.id===false){
                                            if(matchedmodules.includes(object)===false){
                                                matchedmodules.push(object)
                                              }
                                        }
                                        
                                    })

                                if((line[0].x===firstline[0].x||line[0].x===firstline[1].x)&&(line[0].y===firstline[0].y||line[0].y===firstline[1].y)){
                                    matchedmodules.forEach(modules=>{
                                        if(modules.id===object.id===false){
                                            if(matchedmodules.includes(object)===false){
                                                matchedmodules.push(object)
                                              }
                                        }
                                    })
                                }
                            }
                        })
                        
                    }
                })
                console.log(matchedmodules.length)
                let uniqueArr = [...matchedmodules.reduce((map,obj)=>map.set(obj.id, obj), new Map()).values()]
                testarray.push(uniqueArr)
            })

            
        })
        
        
        let finalarray=[]
        let idchecklist = []
        moduleobjects.forEach(object=>{
            idchecklist.push(object.id)
        })

        let finalarr = _.map()

Answer 1

考虑使用基于不相交集数据结构的union-find algorithm。

代码非常简单，wiki伪代码接近真实。

您必须遍历所有元素对（在较长的列表中，获得相邻对就足够了），之后每个元素都将指向其父元素（设置代表元素）。

如何有效地将所有子数组与相关 ID 组合并删除所有重复对象

How to efficiently combine all subarrays with related id's and remove all duplicate objects

sorting

algorithm

node.js

lodash