Most efficient way to sort a list of vector 2's by distance to the previous entry

Question

Hi All,
I’ve been able to test the code out on smaller list sizes and it works exactly as intended. But when its scaled up (from 200 entries to 2000) unity just freezes. In case the subject isn’t very clear I’m trying to sort a list of V2 so that each entry is the closest to the previous entry. Any ideas would be very helpful.
Thank you!

            List<Vector2> sorted = new List<Vector2>();
            List<Vector2> unsorted = new List<Vector2>();
            foreach (Vector2 V in S.DataPoints)
            {
                unsorted.Add(V);
            }
            while (unsorted.Count > 0)
            {
                Vector2 current = new Vector2();
                current = unsorted[0];
                sorted.Add(current);
                unsorted.Remove(current);
                if (unsorted.Count > 1)
                {
                    foreach (Vector2 V1 in unsorted)
                    {
                        unsorted = unsorted.OrderBy(x => Vector2.Distance(current, x)).ToList();
                    }
                }
                else
                {
                    if (unsorted.Count > 0)
                    {
                        current = unsorted[0];
                        sorted.Add(current);
                        unsorted.Remove(current);
                    }
                        
                }
                
            }
            S.DataPoints.Clear();
            foreach(Vector2 V2 in sorted)
            {
                S.DataPoints.Add(V2);
            }

Planogamete

Answer 1

Hello. There are couple of things you can do to make it faster.

1. Don’t use OrderBy, afaik that’s a linq extension that operates on enumerables. Use Sort() instead, it doesn’t require a copy of the list. Of course, to use sort with vectors, you need to provide your own comparer / comparison. But that’s just as easy, see the List.Sort() on MSDN.

2. Don’t calculate the distance of two vectors. The Distance() (or Vector.magnitude) calculates a sqrt inside (based on Pythagoras’ theorem) which is quite slow and always better to avoid. The square (^2) is a one-to-one function for non-negative numbers (which a distance always is), so result of comparison will be same for the distance and it’s square root, better avoid id. Instead, subtract the two vectors, and calculate it’s sqrMagnitude (vecB-vecA).sqrMagnitude.

3. For the cases where comparison of two vectors is necessarily expensive (eg. where the sqrMagnitude tric wouldn’t work) it would still be possible to pre-calcualte some values. Now, the distacne is calculated potentially many times in the sorting process. It would be entirely possible to pre-calculate all vector distances to a point of origin, and store that in a special struct (a struct that contains the original vector, plus the compared distance, calculated when the struct is initialized), create a list of these structs, and sort that (with the sort() comparer only wrapping the compare of those distances in the struct). But this step might not be necessary for you, as sqrMagnitude is much much faster. Do steps 1 and 2 first and observe the results

Karisakarissa

To further explain the step 2: a > b is same as sqrt(a) > sqrt(b) and a*a > b*b this is true only when a and b are non-negative numbers, but a distance will never be negative

– Karisakarissa