Ext.CompositeElement extension to intelligently cluster dom-nodes so they don't overlap. Good for un-cluttering dense markers on a map.

gistfile1.js

/**
* @class Ext.ux.PinOverlap
* An Ext.CompositeElement extension which intelligently moves dom-elements so they don't overlap each other.
* Created for clustering markers on a Map to not overlap.  First picks the most efficient direction to move-off
* of overlapped element, keeping track of where it moved from.  If it overlaps another, it'll back-track and attempt
* to move around the element based upon the MOVE_* CONSTANTS below.  Eg. 
*
* +---------------------------
* |   +-------------------+
* |   |                   |
* |   |     Subject       |
* |   +------------------+
* |     Reference 
* |
* |
* +------------------------
*
* Subject element would first be moved UP.  If that overlaps, it'll rotate through combinations from beginning @see #findMove.
* TODO Some of the combinations vs implementation might be wrong.  They could be looked through very closely and checked.
*
* TODO Add usage example from UnitLayer.js #pinOverlap
* Usage:
<code>

// Important to set {Boolean} returnElement (as opposed to DOMNode) or it won't work.
var markers = Ext.select('.marker-unit', true).pinOverlap();

// Voila.

</code>
*
* @author Chris Scott <christocracy@gmail.com>
*
*/
Ext.override(Ext.CompositeElement, {
    
    // Move strategies based upon the relative overlap
    // TODO Might possibly define these class instances in #pinOverlap instead, created once only when not-detected.
    // Ext.apply(this, {MOVES_LT: [...], ...});
    // 
    MOVES_LT: ['tl', 'l', 'bl', 't', 'b', 'r', 'tr', 'br'],
    MOVES_LB: ['bl', 'l', 'tl', 'b', 't', 'r', 'tr', 'br'],
    MOVES_RT: ['tr', 'r', 'br', 't', 'b', 'l', 'tl', 'bl'],
    MOVES_RB: ['br', 'r', 'tr', 'b', 't', 'r', 'tl', 'bl'],
    MOVES_TL: ['tl', 't', 'tr', 'l', 'bl', 'r', 'tr', 'br'],
    MOVES_TR: ['tr', 't', 'tl', 'r', 'br', 'l', 'tl', 'bl'],
    MOVES_BL: ['bl', 'b', 'l', 'l', 'br', 'r', 'tr', 'br'],
    MOVES_BR: ['br', 'b', 'r', 'r', 'bl', 'l', 'tr', 'bl'],
    
    // Length of all move strategies so we don't have to calculate all the time.
    TOTAL_MOVES: 8,
    
    pinOverlap: function(bounds) {                
        var modified = this.pin(bounds), el;
        
        for (var n=0,len=modified.length;n<len;n++) {
            el = modified[n];
            el.moveTo(el.box.x, el.box.y);
        }
        return this;
    },
    
    initBoxes: function() {
        var el;
        for (var n=0,len=this.elements.length;n<len;n++) {
            el  = this.elements[n];
            //if (!el.box) {    having trouble resetting
                el.box = el.getBox();
            //}
        }
        return this;
    },
    pinReset: function() {
        for (var n=0,len=this.elements.length;n<len;n++) {
            this.elements[n].pinned = false;
        }
        return this;
    },
    
    /**
    * pin
    * @param {Object} bounds from Ext.Element#getBox 
    */
    pin: function(bounds) {
        // pre-cache Element.getBox()
        this.initBoxes();
        
        var len, lenx, n, x,
            x1, y1,
            els         = this.elements,
            subject, ref,
            modified    = [],
            pinned      = false,
            overlap     = false,
            ratioX, ratioY,
            el, refEl;
    
        for (n=0,len=els.length;n<len;n++) {
            el = els[n];

            subject = el.box;
            subject.moves = [];
            subject.lastMove = null;
            
            // recalc, might not need here.
            subject.right   = subject.x + subject.width;
            subject.bottom  = subject.y + subject.height;
            
            while (!el.pinned) {
                overlap = false;
                for (x=0,lenx=els.length;x<lenx;x++) {
                    // Don't compare to self.
                    if ( n === x) {
                        continue;
                    }
                    ref = els[x].box;
                                        
                    // Re-calc right/bottom
                    ref.right   = ref.x + ref.width;
                    ref.bottom  = ref.y + ref.height;
                    
                    // Calculate relative distances of subject-points wrt ref-node-points to determine overlap.
                    c1 = subject.x - ref.right,
                    c2 = subject.right - ref.x,
                    c3 = subject.y - ref.bottom,
                    c4 = subject.bottom - ref.y;
                    
                    if (c1 < 0 && c2 > 0 && c3 < 0 && c4 > 0) {
                        overlap = true;
                        
                        if (!subject.lastMove) {
                            // No last move detected, move the el by the most efficient distance.
                            xOffset = (c1 + c2) / (subject.width + ref.width);
                            yOffset = (c3 + c4) / (subject.height + ref.height);
                            
                            // We load the Subject with its possible moves corresponding to its relative position against the reference el.
                            if (Math.abs(xOffset) > Math.abs(yOffset)) {
                                if (xOffset < 0) {  // left
                                    x1 = ref.x - subject.width;
                                    subject.moves = (yOffset < 0) ? this.MOVES_LT : this.MOVES_LB;  // tl || bl
                                } else {            // right
                                    x1 = ref.x + ref.width;
                                    subject.moves = (yOffset < 0) ? this.MOVES_RT : this.MOVES_RB;  // tr || br
                                }
                                els[n].x = subject.x = x1;
                            } else {
                                if (yOffset < 0) {  // up
                                    y1 = ref.y - subject.height;
                                    subject.moves = (xOffset < 0) ? this.MOVES_TL : this.MOVES_TR;  // tl || tr
                                } else {            // down
                                    y1 = ref.y + ref.height;
                                    subject.moves = (xOffset < 0) ? this.MOVES_BL : this.MOVES_BR;  // bl || br
                                }
                                els[n].y = subject.y = y1;
                            }
                            // Record the el we last moved against so we can back-track to rotate intelligently around it if we overlap with another.
                            subject.lastMove = els[x];
                            subject.lastMoveIndex = 0;
                        } else if(subject.lastMoveIndex < this.TOTAL_MOVES) {   // Try to rotate subject around ref
                            this.findMove(subject);
                        } else {
                            // TODO give up.  Not sure what happens here.
                            subject.lastMove        = null;
                            subject.lastMoveIndex   = 0;
                        }
                        // Commit the box right/bottom now that x/y have changed.
                        subject.right = subject.x + subject.width;
                        subject.bottom = subject.y + subject.height;
                        
                        // If we haven't seen this el before, push the change.
                        if (modified.indexOf(subject) < 0) {
                            modified.push(el);
                        }
                        // Let's try that all again, shall we?  This will determine if we overlap with another shape
                        x = n;
                    }
                }
                if (!overlap) {
                    els[n].pinned = el.pinned = true;
                }
            }
        }
        return modified;
    },
    /**
    * Rotate the subject around the lastMoved ref el
    * @param {Object} Element box
    * TODO Refactor the switch.
    */
    findMove: function(subject) {
        var move    = subject.moves[subject.lastMoveIndex++],
            ref     = subject.lastMove.box,
            x, y;

        switch (move) {
            case 'tl':
                x = ref.x - subject.width;
                y = ref.y - subject.height;
                break;
            case 't':
                x = ref.x + ref.width / 2 - subject.width;
                y = ref.y - subject.height;
                break;
            case 'tr':
                x = ref.right;
                y = ref.y - subject.height;
                break;
            case 'l':
                x = ref.x - subject.width;
                y = ref.y + subject.height / 2;
                break;
            case 'r':
                x = ref.right;
                y = ref.y + subject.height / 2;
                break;
            case 'bl':
                x = ref.x - subject.width;
                y = ref.bottom;
                break;
            case 'b':
                x = ref.x + ref.width / 2 - subject.width;
                y = ref.bottom;
                break;
            case 'br':
                x = ref.right;
                y = ref.bottom;
                break;
        }
        subject.x = x;
        subject.y = y;
    }
});