Collision Detection


I have a form where new labels can be created and dragged to a particular position (they can also be sized).  What is the best way to prevent one label from being dragged/sized over another ?

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

the good news is that all labels are rectangles, so you can use their left, top, width, height properties to determine any overlaps.

the bad news is that you will need to iterate over all the labels and check them against the other labels.

If written correctly, you will be able to prevent redundant overlap checks, bringing the work down to O((N-1) * (N-1)/2) comparisons.

You can further reduce the work by eliminating some of checks if the earlier checks mean that the two labels could not possibly overlap.
given two labels, lblA and lblB
Select Case True
    Case ((lblA.Left + lblA.Width) < lblB.Left ) Or ((lblB.Left + lblB.Width) < lblA.Left )
        'no need to check  more
    Case ((lblA.Top + lblA.Height) < lblB.Top ) Or ((lblB.Top + lblB.Heigth) < lblA.Top )
        'no need to check  more
    Case Else  'time to roll up our sleeves and check these two labels for possible overlaps
End Select

Open in new window

Christopher KileCommented:
The following code defines a class which allows Labels to be sorted according to their layout, with a comparison function that only returns equal (0) if the two labels being compared overlap each other.  Using this function as the comparer and then inserting the SortedLabels into a list, the attempted insertion will fail if the two labels are "equal" to each other (that is, if they collide). That is roughly how this code works:

    Private Class SortableLabel
        Inherits Label
        Implements IComparable

        Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
            Dim lbl As System.Windows.Forms.Label = CType(obj, Label)
            Dim leftComp As Integer = 0
            Dim topComp As Integer = 0

            If MyBase.Location.X > lbl.Location.X + lbl.Width Then
                leftComp = -1
            ElseIf MyBase.Location.X + MyBase.Width < lbl.Location.X Then
                leftComp = 1
            End If

            If MyBase.Location.Y > lbl.Location.Y + lbl.Height Then
                topComp = -1
            End If

            If MyBase.Location.Y + MyBase.Height < lbl.Location.Y Then
                topComp = 1
            End If

            If leftComp < 0 Then Return -1
            If leftComp > 0 Then Return 1
            If topComp < 0 Then Return -1
            If topComp > 0 Then Return 1
            Return 0

        End Function
    End Class

    Private labelList As New SortedList(Of SortableLabel, Label)

    Private Function LabelCollision(ByVal newLabel As Label) As Boolean
        'returns true if the label could not be inserted, i.e. if there was a collision
            Dim srtLabel As SortableLabel = CType(newLabel, SortableLabel)
            labelList.Add(srtLabel, srtLabel)
        Catch argEx As ArgumentException
            Return True
        Catch ex As Exception
            Throw ex
        End Try

        Return False
    End Function

Open in new window

Use this class and the collision function in your event handlers when you're completing the drag-drop operation to check if your label is going to lie over another - a new label will automatically be added to the list as long as it doesn't collide with an old label.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Visual Basic.NET

From novice to tech pro — start learning today.