2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Can you provide some sample Line arrays as input ? \$\endgroup\$
    – Denis
    Mar 31, 2016 at 18:37
  • \$\begingroup\$ What determines the value of _nConrerTolerance ? Are the vertical lines always equal to the horizontal lines ? \$\endgroup\$
    – Denis
    Mar 31, 2016 at 19:22
  • \$\begingroup\$ If you ar eusing C# 6 you don't even need to put private set in the properties. C# 6 allows you to set the value of a getter only property in the constructor. \$\endgroup\$
    – user9993
    Apr 1, 2016 at 7:46
  • \$\begingroup\$ @denis I've updated the question \$\endgroup\$ Apr 1, 2016 at 8:00

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Sounds like a good decision on the Line class and I can give that a go too. But with the threading, I was hoping to try and cut the time down initially and then move to threading, that way I know I've got it working as best I can. \$\endgroup\$ Apr 1, 2016 at 8:02
  • \$\begingroup\$ @TheLethalCoder The problem with parallel threading is you could just as easily degrade performance rather than improve it. It all depends upon how many lines you have. How big are your horiztonalLines and verticalLines? \$\endgroup\$
    – Rick Davin
    Apr 1, 2016 at 11:02
  • \$\begingroup\$ I'm trying to improve the performance of these four methods before I even look into multithreading anyway. Seeing as the four put together take up about 60% of the total time of the full process. And it depends they can be from a few hundred all the way up to a few thousand. There can even be none, but we hope that won't happen! \$\endgroup\$ Apr 1, 2016 at 11:13
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.