将碰撞的物体合并为一个

Question

我正在研究 Javascript 中的一些物理知识，基本上想将碰撞体作为一个整体来处理。

我有一个包含所有发生的碰撞的数组，一个碰撞由两个物体组成，物体 A 和物体 B。

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

X 和 Y
Y 和 Z
C 和 D
E 和 F
F 和 H
G 和 H

现在我想将所有以某种方式连接的物体合并成一个物体。我想要列表中的那些合并的机构。例如，在这种情况下，我想要一个如下所示的列表：

X、Y、Z（因为X和Y碰撞，Y和Z碰撞）
C和D（因为C和D相撞）
E、F、G、H（因为E与F相撞，F与H相撞，G与H相撞）

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

Answer 1

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

我想我会阅读每条规则。对于每条规则，我会将这两个部分连接起来。我最终得到的是一组 blob。然后我可以遍历每个图表以获取每个图表中的节点列表。每个 "connected component" 将是一个 "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) 时间。我们最终会得到一组 blob，其列表的并集将是不超过规则数的符号集，因此它也是 O(n) 存储。

所以我们有一个 O(n) 时间，O(n) space 复杂度算法来确定斑点。渐进地说，我们能做得更好吗？显然我们需要查看所有 n 条规则，所以时间复杂度是最优的。另请注意，此问题的任何解决方案都必须说明每个符号最终属于哪个 blob，因此只需将答案写在输出磁带上就需要 O(n) space。所以这也应该是最优的。

Answer 2

如果您有一个包含所有对象的 ADT（在本例中为地图）并且您保留父 ID 以跟踪对象碰撞，您可以在恒定时间内处理每个碰撞+合并。

// 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,"name":"XYZ","parent":1},"4":{"id":4,"name":"CD","parent":4},"6":{"id":6,"name":"EFHG","parent":6}}

{"1":{"id":1,"name":"XYZEFHG","parent":1},"4":{"id":4,"name":"CD","parent":4}}

将碰撞的物体合并为一个

Merge collided bodies as one

algorithm

collision