DrawingCollisionAvoidanceUtility.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

namespace ApexInvesting.Platform.Utilities.Drawing {

    public enum HorizontalShiftPermissions {

        /// <summary>
        /// The object may not be shifted horizontally.
        /// </summary>
        None,

        /// <summary>
        /// The object may only be shifted leftwards.
        /// </summary>
        Left,

        /// <summary>
        /// The object may only be shifted rightwards
        /// </summary>
        Right,

        /// <summary>
        /// The object can be shifted either left or right
        /// </summary>
        Both
    }

    public enum VerticalShiftPermissions {

        /// <summary>
        /// The object may not be shifted vertically
        /// </summary>
        None,

        /// <summary>
        /// The object may only be shifted in an upward direction
        /// </summary>
        Up,

        /// <summary>
        /// The objct may only be shifted in a downward direction
        /// </summary>
        Down,

        /// <summary>
        /// The object may be shifted either up or down
        /// </summary>
        Both
    }

    /// <summary>
    /// Inherit this interface if your object needs to shifted to avoid drawing collision with other objects
    /// </summary>
    public interface IDrawingCollisionItem {

        /// <summary>
        /// The optimum position for the drawing object.
        /// </summary>
        Rectangle InitialBounds { get; }

        /// <summary>
        /// How this object is allowed to be shifted horizontally
        /// </summary>
        HorizontalShiftPermissions HorizontalShiftPermission { get; }

        /// <summary>
        /// How this object is allowed to be shifted vertically
        /// </summary>
        VerticalShiftPermissions VerticalShiftPermission { get; }

        /// <summary>
        /// The eventual position that has been chosen for this drawing object so it will avoid collisions with other objects.
        /// </summary>
        Rectangle AdjustedBounds { get; set; }
    }

    /// <summary>
    /// A simple convenience implementation of IDrawingCollisionItem
    /// </summary>
    public class DrawingCollisionItem : IDrawingCollisionItem {
        public Rectangle InitialBounds { get; set; }
        public HorizontalShiftPermissions HorizontalShiftPermission { get; set; }
        public VerticalShiftPermissions VerticalShiftPermission { get; set; }
        public Rectangle AdjustedBounds { get; set; }
    }

    /// <summary>
    /// Use this class to perform a layout on drawing collision items. The first item you add won't be moved.
    /// Subsequent items that you add will be moved if necessary to avoid collision with already-added items.
    /// After you have added all objects, you can access their "AdjustedBounds" property to get the place they can be drawn without collision.
    /// </summary>
    public class DrawingCollisionAvoidanceUtility {

        readonly List<IDrawingCollisionItem> items = new List<IDrawingCollisionItem>();

        /// <summary>
        /// Adds an item to the list, first adjusting its position to avoid collision with other objects that already exist in the list
        /// </summary>
        public void Add(IDrawingCollisionItem item) {

            AdjustItem(item);

            items.Add(item);
        }

        /// <summary>
        /// Adjusts the position of an item in preparation for adding it to the list.
        /// Method moves the item either horizontally or vertically but not both, choosing the shortest distance to use
        /// </summary>
        void AdjustItem(IDrawingCollisionItem item) {

            // initialize the item's adjustedBounds in preparation for adjustment
            item.AdjustedBounds = item.InitialBounds;

            // if there are no existing items, then there's nothing more to be done
            if (items.Count == 0)
                return;

            // get the distances that the item needs to be moved
            var horizontalMoveRequired = GetHorizontalMoveRequired(item);
            var verticalMoveRequired = GetVerticalMoveRequired(item);

            // Case A: No move is required
            //         How we know: horizontal == 0 && vertical == 0
            //         What we do: no move
            // Case B: Horizontal move is not allowed
            //         How we know: horizontal == 0 && vertical != 0
            //         What we do: vertical move
            // Case C: Vertical move is not allowed
            //         How we know: horizontal != 0 && vertical == 0
            //         What we do: horizontal move
            // Case D: Vertical and Horizontal move are available
            //         How we know: horizontal != 0 && vertical != 0
            //         What we do: shift by the min of horizontal and vertical

            if (horizontalMoveRequired == 0) { // covers cases A and B
                item.AdjustedBounds.Offset(0, verticalMoveRequired);
            } else if (verticalMoveRequired == 0) { // covers case C
                item.AdjustedBounds.Offset(horizontalMoveRequired, 0);
            } else { // covers case D
                if (Math.Abs(horizontalMoveRequired) < Math.Abs(verticalMoveRequired)) {
                    item.AdjustedBounds.Offset(horizontalMoveRequired, 0);
                } else {
                    item.AdjustedBounds.Offset(0, verticalMoveRequired);
                }
            }
        }

        /// <summary>
        /// Gets the shortest vertical distance that the given item would have to move to avoid collisions with all other items.
        /// A positive result is a move down. A negative result is a move up.
        /// </summary>
        int GetVerticalMoveRequired(IDrawingCollisionItem item) {

            // if the item is not allowed to move vertically, return 0 for no move.
            if (item.VerticalShiftPermission == VerticalShiftPermissions.None)
                return 0;

            // get the up and down move distances that would be required to avoid collisions with all existing items
            // note they are kept here as positive values
            int up = 0, down = 0;
            foreach (var existingItem in items) {
                // check if there is a move required
                if (item.InitialBounds.IntersectsWith(existingItem.AdjustedBounds)) {
                    // check if the item is allowed to move up
                    if (item.VerticalShiftPermission == VerticalShiftPermissions.Both || item.VerticalShiftPermission == VerticalShiftPermissions.Up) {
                        // get the upward move that would be required to avoid collision
                        up = Math.Max(up, item.InitialBounds.Bottom - existingItem.AdjustedBounds.Top);
                    }
                    // check if the item is allowed to move down
                    if (item.VerticalShiftPermission == VerticalShiftPermissions.Both || item.VerticalShiftPermission == VerticalShiftPermissions.Down) {
                        // get the downward move that would be required to avoid collision
                        down = Math.Max(down, existingItem.AdjustedBounds.Bottom - item.InitialBounds.Top);
                    }
                }
            }

            // Case A: No move is required
            //         How we know: up == 0 && down == 0
            //         What we return: 0
            // Case B: Up move is not allowed
            //         How we know: up == 0 && down > 0
            //         What we return: down
            // Case C: Down move is not allowed
            //         How we know: up > 0 && down == 0
            //         What we return: up
            // Case D: Left and Right move are available
            //         How we know: up > 0 && down > 0
            //         What we return: min(up, down)

            // cover cases A and B
            if (up == 0)
                return down;

            // cover case C, remembering to negate for upward move
            if (down == 0)
                return -up;

            // cover case D, remembering to negate for upward move
            return down < up
                ? down
                : -up;
        }

        /// <summary>
        /// Gets the shortest horizontal distance that the given item would have to move to avoid collisions with all other items.
        /// A positive result is a move right. A negative result is a move left.
        /// </summary>
        int GetHorizontalMoveRequired(IDrawingCollisionItem item) {

            // if the item is not allowed to move horizontally, return 0 for no move.
            if (item.HorizontalShiftPermission == HorizontalShiftPermissions.None)
                return 0;

            // get the left and right move distances that would be required to avoid collisions with all existing items
            // note they are kept here as positive values
            int left = 0, right = 0;
            foreach (var existingItem in items) {
                // check if there is a move required
                if (item.InitialBounds.IntersectsWith(existingItem.AdjustedBounds)) {
                    // check if the item is allowed to move left
                    if (item.HorizontalShiftPermission == HorizontalShiftPermissions.Both || item.HorizontalShiftPermission == HorizontalShiftPermissions.Left) {
                        // get the leftward move that would be required
                        left = Math.Max(left, item.InitialBounds.Right - existingItem.AdjustedBounds.Left);
                    }
                    // check if the item is allowed to move right
                    if (item.HorizontalShiftPermission == HorizontalShiftPermissions.Both || item.HorizontalShiftPermission == HorizontalShiftPermissions.Right) {
                        // get the rightward move that would be required
                        right = Math.Max(right, existingItem.AdjustedBounds.Right - item.AdjustedBounds.Left);
                    }
                }
            }

            // Case A: No move is required
            //         How we know: left == 0 && right == 0
            //         What we return: 0
            // Case B: Left move is not allowed
            //         How we know: left == 0 && right > 0
            //         What we return: right
            // Case C: Right move is not allowed
            //         How we know: left > 0 && right == 0
            //         What we return: left
            // Case D: Left and Right move are available
            //         How we know: left > 0 && right > 0
            //         What we return: min(left, right)

            // cover cases A and B
            if (left == 0)
                return right;

            // cover case C, remembering to negate for leftward move
            if (right == 0)
                return -left;

            // cover case D, remembering to negate for leftward move
            return right < left
                ? right
                : -left;
        }
    }
}