What is the most efficient way to avoid duplicate operations in a C# array?

Question

I need to calculate distances between every pair of points in an array and only want to do that once per pair. Is what I've come up with efficient enough or is there a better way? Here's an example, along with a visual to explain what I'm trying to obtain:

e.g., first get segments A-B, A-C, A-D; then B-C, B-D; and finally, C-D. In other words, we want A-B in our new array, but not B-A since it would be a duplication.

var pointsArray = new Point[4];

pointsArray[0] = new Point(0, 0);
pointsArray[1] = new Point(10, 0);
pointsArray[2] = new Point(10, 10);
pointsArray[3] = new Point(0, 10);

// using (n * (n-1)) / 2 to determine array size
int distArraySize = (pointsArray.Length*(pointsArray.Length - 1))/2;

var distanceArray = new double[distArraySize];

int distanceArrayIndex = 0;

// Loop through points and get distances, never using same point pair twice
for (int currentPointIndex = 0; currentPointIndex < pointsArray.Length - 1; currentPointIndex++)
{
    for (int otherPointIndex = currentPointIndex + 1;
            otherPointIndex < pointsArray.Length;
            otherPointIndex++)
    {
        double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X;
        double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y;

        double distance = Math.Sqrt(Math.Pow(xDistance, 2) + Math.Pow(yDistance, 2));

        // Add distance to distanceArray
        distanceArray[distanceArrayIndex] = distance;

        distanceArrayIndex++;
    }
} 

Since this will be used with many thousands of points, I'm thinking a precisely dimensioned array would be more efficient than using any sort of IEnumerable.

Answer 1

If you have n points, the set of all pairs of points contains n * (n-1) / 2 elements. That's the number of operations you are doing. The only change I would do is using Parallel.ForEach() to do the operations in parallel.

Something like this (needs debugging)

        int distArraySize = (pointsArray.Length * (pointsArray.Length - 1)) / 2;

        var distanceArray = new double[distArraySize];

        int numPoints = pointsArray.Length;

        Parallel.ForEach<int>(Enumerable.Range(0, numPoints - 2),
            currentPointIndex =>
            {
                Parallel.ForEach<int>(Enumerable.Range(currentPointIndex + 1, numPoints - 2),
                    otherPointIndex =>
                    {
                        double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X;
                        double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y;
                        double distance = Math.Sqrt(xDistance * xDistance + yDistance * yDistance);
                        int distanceArrayIndex = currentPointIndex * numPoints - (currentPointIndex * (currentPointIndex + 1) / 2) + otherPointIndex - 1;
                        distanceArray[distanceArrayIndex] = distance;
                    });
            });