Finding corners from Line arrays

Question

I have the following code that takes input of Line arrays and attempts to find the intersections on the end points between them. The value _nConrerTolerance is an int of a value of around 10% of the average Line length to allow the lines to not need to be exactly on each other. Now obvisouly this code will be quite slow, especially as I have similar methods for top left, bottom left and bottom right corners. Can anyone suggest a way to improve this?

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

private Point[] FindTopRightCorners(Line[] horizontalLines, Line[] verticalLines)
{
    List<Point> TopRightCorners = new List<Point>();

    Line[] laHorizontalLines = horizontalLines.OrderByDescending(l => l.EndPoint.X).ThenBy(l => l.EndPoint.Y).ToArray();
    Line[] laVerticalLines = verticalLines.OrderByDescending(l => l.StartPoint.X).ThenBy(l => l.StartPoint.Y).ToArray();

    foreach (Line verticalLine in laVerticalLines)
    {
        foreach (Line horizontalLine in laHorizontalLines)
        {
            if (verticalLine.StartPoint.X >= (horizontalLine.EndPoint.X - _nCornerTolerance) && verticalLine.StartPoint.X <= (horizontalLine.EndPoint.X + _nCornerTolerance))
            {
                if (horizontalLine.EndPoint.Y <= (verticalLine.StartPoint.Y + _nCornerTolerance) && horizontalLine.EndPoint.Y >= (verticalLine.StartPoint.Y - _nCornerTolerance))
                {
                    int nX = Math.Abs((verticalLine.StartPoint.X + horizontalLine.EndPoint.X) / 2);
                    int nY = Math.Abs((verticalLine.StartPoint.Y + horizontalLine.EndPoint.Y) / 2);

                    TopRightCorners.Add(new Point(nX, nY));
                    break;
                }
            }
        }
    }

    return TopRightCorners.Distinct().ToArray();
}

And the Line class is defined as follows:

public class Line
{
    public Point StartPoint { get; private set; }

    public Point EndPoint { get; private set; }

    public Line(Point startPoint, Point endPoint)
    {
        this.StartPoint = startPoint;
        this.EndPoint = endPoint;
    }
}

Answer 1

You have similar code and similar performance issue in your other question about points instead of lines. I answered that one here. Some of my answers can apply here particularly as to the repeated use of .ToArray()?

If you skipped everything as arrays and went with IEnumerable<Line> or IEnumerable<Point> for inputs, output, and anything inbetween then you might see some performance benefit. Might. Don't know until you run it. But sounds like you are talking about big collections.

If you try using IEnumerable and things are still slow, I'd try to use Parallel.For with a range partitioner.

That should address your major concern. On a minor concern, the Line class is good enough and looks like something I once wrote. I eventually switched from StartPoint and EndPoint to Point1 and Point2 since some readers may think StartPoint should somehow be 'less than' when compared to EndPoint or that it should be drawn like a vector that somehow starts at StartPoint and is then drawn to EndPoint. To avoid such needless notions, I went with the generic Point1 and Point2.

Answer 2

I ended up managing to take about 40-50% of the time off of each loop.

private Point[] FindTopLeftCorners(List<Line> horizontalLines, List<Line> verticalLines)
{
    Point[] paHorizontalLines = horizontalLines.OrderBy(l => l.Point1.X)
                                               .ThenBy(l => l.Point1.Y)
                                               .Select(l => l.Point1)
                                               .ToArray();

    Point[] paVerticalLines = verticalLines.OrderBy(l => l.Point1.X)
                                           .ThenBy(l => l.Point1.Y)
                                           .Select(l => l.Point1)
                                           .ToArray();

   List<Point> plTopLeftCorners = new List<Point>();
    for (int vi = 0, vc = paVerticalLines.Length, hi = 0, hc = 0; vi < vc; ++vi)
    {
        for (hi = 0, hc = paHorizontalLines.Length; hi < hc; ++hi)
        {
            if (Math.Abs(paVerticalLines[vi].X - paHorizontalLines[hi].X) <= _nCornerTolerance
             && Math.Abs(paVerticalLines[vi].Y - paHorizontalLines[hi].Y) <= _nCornerTolerance)
            {
                plTopLeftCorners.Add(new Point((paVerticalLines[vi].X + paHorizontalLines[hi].X) / 2,
                                               (paVerticalLines[vi].Y + paHorizontalLines[hi].Y) / 2));
                break;
            }
        }
    }

    return AverageNearbyPoints(plTopLeftCorners.Distinct().ToArray(), true, true);
}

Essentially the biggest change is selecting the point to be used in the initial order statement instead of the full line. The other changes are going to a for loops and various other memory allocation changes.