How to optimize two cycles with finding vector length?

Got such functions, that delete's some points from Curve, if it's too close to the Line (its straight line). But the point is the amount of coordinates. One Curve can have about 1000 coordinates, and it makes program works for 3-4 times slower.

Start Index and End index is needed for not checking all the straight line (amount of coordinates is about 3000)

(List<int>, List<int>) LineCheck(List<int> Xcurve, List<int> Ycurve, List<int> XLine, List<int> YLine, double deviation)
        {
            //point - координаты точки для проверки, LineUp - список координат верхней прямой
            //LineDown - список координат нижней прямой
            List<int> returnCurveX = new List<int>();
            List<int> returnCurveY = new List<int>();
            //отклонение от прямой, для большей точности проверки можно уменьшить
            //но надо проверять по факту

            for (int i = 0; i < Xcurve.Count - 1; i++)
            {
                bool flag = true;
                int XStartIndex = XLine.Where(w => w >= Xcurve[0]).First();
                int XEndIndex = XLine.Where(w => w <= Xcurve[Xcurve.Count - 1]).Last();

                for (int j = XStartIndex; j < XEndIndex; j++)
                {
                    double[] vector1 = { Xcurve[i] - XLine[j], Ycurve[i] - YLine[j] };
                    // Вычисление длин векторов
                    double length1 = Math.Sqrt(vector1[0] * vector1[0] + vector1[1] * vector1[1]);
                    if (length1 < deviation)
                    {
                        flag = false;


                    }

                }
                if (flag)

                {
                    returnCurveX.Add(Xcurve[i]);
                    returnCurveY.Add(Ycurve[i]);
                    //принадлежит прямой
                }
            }

           // return (Xcurve, Ycurve);
            //точка не попала на координаты прямой
            return (returnCurveX, returnCurveY);


        }

I've tried to break somehow the first cycle, but it don't allow me to return needed points. If we could change source array, maybe it would be easier.

Solution

Assuming that XLine and YLine have just 2 points each we can try solving problem as follow. Having a line which is drawn through two points (ax, ay) and (bx, by) we can write this line as an equation

A * x + B * y + C = 0

as (https://math.stackexchange.com/questions/422602/convert-two-points-to-line-eq-ax-by-c-0)

A = ay - by
B = bx - ax
C = ax * by - bx * ay

Having the equation, we can easily compute distance from a point (px, py) to the line

DistanceSquared = (A * px + B * py + C) * (A * px + B * py + C) / (A * A + B * B)

Something like this:

LineCheck(...) {
  ...

  // Let use long to avoid integer overflow
  long ax = XLine[0];
  long bx = XLine[1];
  long ay = YLine[0];
  long by = YLine[1];

  long A = ay - by;
  long B = bx - ax;
  long C = ax * by - bx * ay;

  for (int i = 0; i < Xcurve.Count; ++i) {
    double px = Xcurve[i];
    double py = Ycurve[i];

    var d2 = (A * px + B * py + C) * (A * px + B * py + C) / (A * A + B * B);

    if (d2 >= deviation * deviation) {
      returnCurveX.Add(Xcurve[i]);
      returnCurveY.Add(Ycurve[i]);
    }
  }

  ...
}