Convert list of pairs into array groups in AS3

Question

I have an ActionScript 3 array that lists pairs of items like this:

pairs[0] = Array('ItemA', 'ItemB');
pairs[1] = Array('ItemA', 'ItemC');
pairs[2] = Array('ItemC', 'ItemD');
pairs[3] = Array('ItemC', 'ItemE');
pairs[4] = Array('ItemF', 'ItemG');
pairs[5] = Array('ItemF', 'ItemH');

And I need to loop over the array in some way to find all overlapping pairs (any pairs that share common pairs).

For example, ItemA is paired with ItemB and ItemC, so they belong in a group together. ItemC is also paired with ItemD and ItemE so they also need to be a part of the first group.

ItemF, ItemG and ItemH do not overlap with any of the items fromt he first group, so they need to be put into their own group.

The resulting array would need to be something like:

groups[0] = Array('ItemA', 'ItemB', 'ItemC', 'ItemD', 'ItemE');
groups[1] = Array('ItemF', 'ItemG', 'ItemH');

Thanks for any help and suggestions!

Edit:

A little bit of a back story; I'm trying to group together movie clips that overlap each other in 2D to create groups or clusters (might be a better word).

So if I have 3 movieclips on the stage and ClipA overlaps with ClipB and ClipB overlaps ClipC (but ClipA doesn't directly overlap ClipC) they should all be grouped together as they are all a part of the same cluster. This way should a new clip overlap any single item in a cluster, it will be added to that group's array.

I've already got the code worked out to find overlapping elements which is producing this pairs list, now I need to condense it into tidy groups.

Possibly helpful: essentially I want to do the exact opposite of this ( stackoverflow.com/questions/3770362/… ) but in AS3 (not PHP). Though if the solution is supplied in PHP I can probably easily work it into AS3. — levi
– levi, Commented Nov 29, 2010 at 7:06
The key here is that as long as they overlap, they should be in the same Array? Do you know which ones that overlap or do you have to find it out runtime? — Mattias
– Mattias, Commented Nov 29, 2010 at 7:07
Yes, as long as they overlap with any other item that already exists in the group, they should be added to that group. — levi
– levi, Commented Nov 29, 2010 at 7:20
This all needs to be figured out in runtime, the pairs list can be changed at any time, so I'll need to be able to regenerate the groups/cluster array whenever this happens. — levi
– levi, Commented Nov 29, 2010 at 7:25

Lee · Accepted Answer · 2010-11-29 08:15:00Z

An algorithm like the example below should work.

NOTE: This is not the most efficient or concise way to write this code (it's certainly more repetitive than it needs to be), but I wanted to keep it clear and simple for this example. [Also, I haven't tested this code--it's presented as pseudo-code only--so if you find an error, please just let me know, and I'll fix it]

var idx:Object = new Object;
var groups:Array = new Array();
for( var i:int = 0; i<pairs.length; ++i ) {
   var onePair:Array = pairs[i];

   // which groups do the two items belong to?
   var g1:Array = idx[onePair[0]];
   var g2:Array = idx[onePair[1]];

   if( !g1 ) {
     // if item #1 is not yet in a group, then add it to item #2's
     // existing group, or if neither group exists yet, just create a new one
     g1 = g2;
     if( !g1 ) {
        g1 = [];
        groups.push(g1);
     }
     g1.push( onePair[0] );

     // ensure that the idx properly reflects the location of the new item
     idx[onePair[0]] = g1;
   }

   // now do the same for the second item... but g1 will never be null, so
   // this case is a little simpler.
   if( !g2 ) {
     g2 = g1;
     g2.push( onePair[1] );
     idx[onePair[1]] = g2;
   }

   if( g1 != g2 ) {
      // now, if they're not already the same group, then merge the two
      // groups, and update the idx to reflect the merge.

      for( var z:int=0; z<g2.length; ++z ) {
         idx[g2[z]] = g1;
         g1.push( g2[z] );
         g2.splice(0);
      }
   }
}

groups will end up being an array of arrays, just like you asked for -- but there will be a few empty arrays that can be discarded. Just prune (or ignore) the empty ones, and you'll have your groups.

the basic idea here, is that idx provides a lookup table that indicates, throughout the indexing process, for any given item, which group it's in (if any). This allows us to determine whether an item has been encountered previously or not, and if so, to utilize it's existing group.

Patrick · Accepted Answer · 2010-11-29 08:37:39Z

You can use an Object to keep the track of the association of a pair iten and a group, the key will be each item of your pair.

Here a litle snippet that make the works :

var pairs:Array=[];
pairs[0] = ['ItemA', 'ItemB'];
pairs[1] = ['ItemA', 'ItemC'];
pairs[2] = ['ItemC', 'ItemD'];
pairs[3] = ['ItemC', 'ItemE'];
pairs[4] = ['ItemF', 'ItemG'];
pairs[5] = ['ItemF', 'ItemH'];


// will contain group created
var groups:Array=[];

// will contain association between a pair item and a group
var pair2group:Object={};

// function that turn pairs into groups
function makeGroups(pairs:Array):void{
    var pairLen:int = pairs.length;

    for (var i:int=0;i<pairLen;i++){
        var pair:Array = pairs[i];
        var item1:String = pair[0];
        var item2:String = pair[1];

        var group:Array = pair2group[item1];

        // is first pair item already in a group
        if (group == null) {
            // no so create a new group
            group=[];

            // create the association
            pair2group[item1] = group;

            // add the item to the group we have created
            group.push(item1);

            // add it to all the groups 
            groups.push(group);
        }

        // is the second pair item into a grouo
        if (pair2group[item2] == null) {
            // no so add it to the group where the first item belong
            group.push(item2);

            // create the association for the second item
            pair2group[item2] = group;
        }
    }
}

// ---- test
makeGroups(pairs);
trace(groups.length);
trace(groups[0]);
trace(groups[1]);

levi · Accepted Answer · 2010-11-29 08:24:02Z

After lots of playing around here's the solution I came up with.

This will take an 2D overlapArray that has pairs and produce a group list with unique values.

I used a in_array() function to duplicate PHP's handy function for finding if an item is already in an array.

for each(var pair:Array in overlapArray) {
    var pairInGroup = false;
    for each(var group:Array in overlapArrayGroups) {
        if(in_array(pair[0],group) || in_array(pair[1],group)) {
            if(!in_array(pair[0],group)) {
                group.push(pair[0]);
            }
            if(!in_array(pair[1],group)) {
                group.push(pair[1]);
            }
            pairInGroup = true;
        }
    }
    if(!pairInGroup) {
        overlapArrayGroups.push(pair);
    }
}

The in_array() function:

public static function in_array( needle:String, haystack:Array ):Boolean {
    for( var a = 0; a < haystack.length; a++ ) {
        if( haystack[a] == needle ) {
            return true;
        } else if( haystack[a] is Array ) {
            return in_array(needle, haystack[a]);
        }
    }
    return false;
}

Collectives™ on Stack Overflow

Convert list of pairs into array groups in AS3

3 Answers 3

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Linked

Related