合并碰撞体为一体

Question

我正在研究Javascript中的一些物理材料，基本上是想把碰撞的物体作为一个整体来处理。

我已经得到了所有发生的碰撞的数组，一个碰撞由两个物体组成，体A和B体。

假设发生了六次碰撞，物体之间的碰撞：

1. X和Y
2. Y和Z
3. C和D
4. E和F
5. F和H
6. G和H

现在我想把所有以某种方式连接在一起的身体合并成一个单一的身体。我要把那些合并的身体列在一张名单上。例如，在本例中，我想要一个如下所示的列表：

1. X，Y和Z(因为X与Y碰撞，Y与Z碰撞)
2. C和D(因为C与D碰撞)
3. E，F，G和H (因为E与F碰撞，F与H碰撞，G与H碰撞)

现在我很确定有一些算法是我需要的，我只是不知道该去哪里找，我没有办法自己解决这个问题。

Answer 1

你在现实生活中会怎么做？

我想我会读每一条规则。对于每一条规则，我都会把这两部分连接起来。我的结局就是一堆小水珠。然后，我可以遍历每个图，以获得每个图中的节点列表。每个“连接组件”将是一个"blob“。将此算法形式化一点可能会给出以下结果：

// make the graph of connected components
nodes = map<symbol, pair<symbol, list<symbol>>>
for each (a, b) in rules do
    if nodes[a] is null then nodes[a] = node(a, [b])
    else nodes[a].connections.append(b)

    if nodes[b] is null then nodes[b] = node(b, [a])
    else nodes[b].connections.append(a)
loop

blobs = map<symbol, list<symbol>>
for each (a, b) in rules do

    firstNode = nodes[a]
    // do a DFS/BFS search starting from firstNode to find
    // all nodes in the connected component. whenever you
    // follow a link from a node, remove it from the node's
    // list of links. this prevents ever searching from that
    // node again since we know what component it's in already
    // add each node to the list of symbols in blobs[a]

loop

在第一个循环中，我们读取每条规则一次，然后做一定量的工作，所以在规则数中是O(n)时间。它将为每个规则存储两个连接，O(n)存储的规则数量也是如此。

在第二个循环中，我们查看每个规则，并为每个规则的LHS符号执行DFS或BFS。但是，请注意，搜索将只遍历任何边一次，因此这是O(n)时间的规则数。我们最后会有一些小块，其列表的合并将是一组符号，它不会超过规则的数量，所以它也是O(n)存储。

因此，我们有一个O(n)时间，O(n)空间复杂度算法来确定blobs。我们能做得更好吗？显然，我们需要研究所有的n个规则，所以时间复杂度是最优的。还请注意，这个问题的任何解决方案都必须对blob所属于的每个符号说明，因此将答案写在输出磁带上就会占用O(n)空间。所以这也应该是最优的。

Answer 2

如果您有一个包含所有对象的ADT (在本例中是一个映射)，并且保持父id来跟踪对象冲突，则可以在恒定时间内处理每个collision+merge。

// setup
var X = {id: 1, name:'X'};
var Y = {id: 2, name:'Y'};
var Z = {id: 3, name:'Z'};
var C = {id: 4, name:'C'};
var D = {id: 5, name:'D'};
var E = {id: 6, name:'E'};
var F = {id: 7, name:'F'};
var G = {id: 8, name:'G'};
var H = {id: 9, name:'H'};
var all = { 1:X, 2:Y, 3:Z, 4:C, 5:D, 6:E, 7:F, 8:G, 9:H };

// method to merge collided objects together
function collision(obj1, obj2) {
    var p1 = obj1.parent;
    var p2 = obj2.parent;
    if(p1 === undefined && p2 === undefined) {
        obj1.parent = obj1.id;
        obj2.parent = obj1.id;
        obj1.name += obj2.name;
        delete all[obj2.id];
    } else if(p1 !== undefined && p2 === undefined) {
        obj2.parent = obj1.parent;
        all[obj1.parent].name += obj2.name;
        delete all[obj2.id];
    } else if(p1 === undefined && p2 !== undefined) {
        obj1.parent = obj2.parent;
        all[obj2.parent].name += obj1.name;
        delete all[obj1.id];
    } else if(p1 !== undefined && p2 !== undefined && obj1.parent !== obj2.parent) {
        if(all[obj1.parent] !== undefined) {
            all[obj1.parent].name += all[obj2.parent].name;
            delete all[obj2.parent];
        } else if(all[obj2.parent] !== undefined) {
            all[obj2.parent].name += all[obj1.parent].name;
            delete all[obj1.parent];
        }
    }
}

// test
console.log(JSON.stringify(all));
collision(X, Y);
collision(Y, Z);
collision(C, D);
collision(E, F);
collision(F, H);
collision(G, H);
console.log(JSON.stringify(all));
collision(X, E);
console.log(JSON.stringify(all));

{"1":{"id":1，"name":"X"}，"2":{"id":2，"name":"Y"}，"3":{"id":3，"name":"Z"}，"4":{"id":4，"name":"C"}，"5":{"id":5，"name":"D"}，"6":{"id":6，“name”：“名称”：“E”}，"7":{"id":7，"name":"F"}，"8":{"id":8，"name":"G"}，"9":{"id":9，"name":"H"}} {"1":{"id":1，“名称”：“XYZ”，“父”：1}，"4":{"id":4，"name":"CD"，“双亲”：4}，"6":{"id":6，“name”：“名称”：“EFHG”，“父”：6}} {"1":{"id":1，“名称”：“XYZEFHG”，“父”：1}，"4":{"id":4，"name":"CD"，“父”：4}}