Sorting a List (Of Point) Based on Distance

[neef]

This is a nice little puzzle challenge.

I have a list of collection of points on the screen. I want to order them based on their distance from a seperate, independent point. What's working is I have a function GetDistance which does the dirty pythagorian work of returning the distance between two points.

Let me explain more in the code block below...

'Create the set point from which to start all measurements from (startpoint)
dim SetPoint as new Point(200,200)
'Create a list to hold arbitrary points to test (endpoints)
dim ListOfPoints as new list(of point)
'Add points to test
ListOfPoints.Add(1000,2000)
ListOfPoints.Add(340,400)
ListOfPoints.Add(1022,53)
ListOfPoints.Add(333,987)

'The code should now rearrange the above list from closest to furthest from 
'the SetPoint using my GetDistance(StartPoint, EndPoint) pythagorian function

Thanks for any help in advance.

[Shaggy Hiker]

You could probably create a custom sorter, but it could end up being kind of painful. After all, it would require that the distance be calculated for every comparison, of which there will be many for a sort. Therefore, you are going to end up doing far more distance calculations than the number of items in the list. So is that worthwhile? If it isn't, then you might want to create a new class that holds a point and a distance, then sort that list rather than sorting the point list. By doing this, you can make the distance a member of the class and only calculate it once per point, rather than twice per comparison.

[neef]

That's the outside the box thinking I was looking for, thank you.

How would you use the Sort method in this case (using a member variable of an object to sort the objects themselves)?

Sort has always thrown me off a little; I'm not sure why.

[Shaggy Hiker]

You just need to implement IComparable on the class. That will create a stub of CompareTo. What you do in there is something I always forget, so I go to MSDN where there happens to be a good example, which I copy into my project. Here's what is in MSDN:

Public Overloads Function CompareTo(ByVal obj As Object) As Integer _
        Implements IComparable.CompareTo

        If TypeOf obj Is Temperature Then
            Dim otherTemperature As Temperature = DirectCast(obj, Temperature)
            Return Me.temperatureF.CompareTo(otherTemperature.temperatureF)
        Else
           Throw New ArgumentException("object is not a Temperature")
        End If   
    End Function

I believe that there is also an IComparable (of T), which would be better, as you would use your class for T, and instead of receiving an object, you will get an argument of type T, so that whole If statement and the cast can be removed. You just want to compare the distance of the incoming T to the distance of the current instance, and return 1 or -1 depending on which should sort ahead of the other.

I never remember how it works, though, so I happen to know that MSDN spells it out.

[.paul.]

I believe that there is also an IComparable (of T), which would be better.

Shaggy is right...

Public Class Class1
    Implements IComparable(Of Class1)
 
    Public Function CompareTo(ByVal other As Class1) As Integer Implements System.IComparable(Of Class1).CompareTo
        Return Me.temperatureF.CompareTo(other.temperatureF)
    End Function
 
    Private _temperatureF As Decimal
    Public Property temperatureF As Decimal
        Get
            Return _temperatureF
        End Get
        Set(ByVal value As Decimal)
            _temperatureF = value
        End Set
    End Property
 
End Class

[jmcilhinney]

You can implement IComparable on the item type but that doesn't necessarily make sense in all cases, plus it's downright impossible if you're using a type that you didn't define yourself. In your case, it would make most sense to either define a class that implements IComparer (note that this is different to IComparable) or else just write a method that matched the signature of the Comparison delegate. Follow the Blog link in my signature and check out my three-part post on sorting lists for all the details.

[neef]

Thank you all for your help.

[.paul.]

could you post your GetDistance function?

[.paul.]

try this:

'Create a list to hold arbitrary points to test (endpoints)
Dim ListOfPoints As New List(Of Point)
'Add points to test
ListOfPoints.Add(New Point(1000, 2000))
ListOfPoints.Add(New Point(340, 400))
ListOfPoints.Add(New Point(1022, 53))
ListOfPoints.Add(New Point(333, 987))
 
ListOfPoints.Sort(New comparer2)

this is the comparer:

Public Class comparer2
    Implements IComparer(Of Point)
 
    Public Function Compare(ByVal x As Point, ByVal y As Point) As Integer Implements System.Collections.Generic.IComparer(Of Point).Compare
        'Create the set point from which to start all measurements from (startpoint)
        Dim SetPoint As New Point(200, 200)
        Return lineLength(SetPoint, x).CompareTo(lineLength(SetPoint, y))
    End Function
 
    ''' <summary>
    ''' lineLength
    ''' </summary>
    ''' <param name="p1">point1</param>
    ''' <param name="p2">point2</param>
    ''' <returns>length in pixels between p1 and p2</returns>
    ''' <remarks></remarks>
    Public Shared Function lineLength(ByVal p1 As Point, ByVal p2 As Point) As Double
        Dim r As Rectangle = normalizeRect(p1, p2)
        Return Math.Sqrt(r.Width ^ 2 + r.Height ^ 2)
    End Function
 
    ''' <summary>
    ''' </summary>
    ''' <param name="p1">point1</param>
    ''' <param name="p2">point2</param>
    ''' <returns>a rectangle encapsulating p1, p2</returns>
    ''' <remarks></remarks>
    Private Shared Function normalizeRect(ByVal p1 As Point, ByVal p2 As Point) As Rectangle
        Dim r As New Rectangle
        If p1.X < p2.X Then
            r.X = p1.X
            r.Width = p2.X - p1.X
        Else
            r.X = p2.X
            r.Width = p1.X - p2.X
        End If
        If p1.Y < p2.Y Then
            r.Y = p1.Y
            r.Height = p2.Y - p1.Y
        Else
            r.Y = p2.Y
            r.Height = p1.Y - p2.Y
        End If
        Return r
    End Function
 
End Class

[jmcilhinney]

Just to be clear, here's an example of an IComparer that would suit your situation:

Friend Class PointComparer
    Implements IComparer(Of Point)
 
    Private reference As Point
 
 
    Public Sub New()
        'Use the origin as the default reference point.
        Me.New(Point.Empty)
    End Sub
 
    Public Sub New(ByVal reference As Point)
        Me.reference = reference
    End Sub
 
 
    Public Function Compare(ByVal pt1 As Point, _
                            ByVal pt2 As Point) As Integer Implements IComparer(Of Point).Compare
        Dim distance1 As Double = Math.Sqrt((pt1.X - Me.reference.X) ^ 2 + (pt1.Y - Me.reference.Y) ^ 2)
        Dim distance2 As Double = Math.Sqrt((pt2.X - Me.reference.X) ^ 2 + (pt2.Y - Me.reference.Y) ^ 2)
 
        Return distance1.CompareTo(distance2)
    End Function
 
End Class

And here's how you might use it:

Private Sub SortPointsByDistanceFromReference(ByVal points As List(Of Point), _
                                              ByVal reference As Point)
    points.Sort(New PointComparer(reference))
End Sub

Note that, as with all sorting, it still makes use of the IComparable interface. In the PointComparer.Compare method the IComparable.CompareTo implementation of the Double structure is being invoked to compare two Double values that represent the distances of the two Points from the specified reference Point.