Finding the nearby points from an array

Question

I have the following code that takes a Point and a given tolerance value and looks for all other Points that fall within the tolerance from a Point array. Now this code is quite slow, does anyone know a faster way of doing this?

Also if you have any tips on how I can improve my coding style, if needed, that would be great.

private Point[] FindNearbyPoints(Point[] points, Point initialPoint, int tolerance)
{
    return points.Select(p => p)
                 .Where(p => (p.X >= initialPoint.X - tolerance && p.X <= initialPoint.X + tolerance) &&
                             (p.Y >= initialPoint.Y - tolerance && p.Y <= initialPoint.Y + tolerance))
                 .ToArray();
}

Answer 1

How many points are we talking about that makes performance slow? If its a crazy amount, you could use a Range Partitioner and a Parallel.For. But I would suggest outputting as a List<Point> rather than an array so that each parallel thread can merge the subset of points. I'd rather not get into details about in this answer though.

One alternative is to check X or Y against the tolerance once:

private Point[] FindNearbyPoints(Point[] points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance))
                 .ToArray();
}

You could try making that an extension method in a public static class, such as:

public static Point[] FindNearbyPoints(this Point[] points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance))
                 .ToArray();
}

A bigger consideration is whether the return type must be Point[]. You might see some performance boost if you went with IEnumerable<Point>. In fact the extension method could be more reachable if you changed the input signature a bit too. Something like:

public static IEnumerable<Point> FindNearbyPoints(this IEnumerable<Point> points, Point initialPoint, int tolerance)
{
    tolerance = Math.Abs(tolerance);
    return points.Select(p => p)
                 .Where(p => (Math.Abs(p.X - initialPoint.X) <= tolerance) &&
                             (Math.Abs(p.Y - initialPoint.Y) <= tolerance));
}

Other than that, your coding style looks fine. Give these changes a try and see if performance is still an issue. If it is, I'll try to find time to work up an example using a range partitioner.