Speed up algorithm to detect if one line is subline of another

1. I think what you've got here would go much better in Extension Methods. I also have done this with the IsSubline Method of yours, but I've renamed it to ContainsSubLine, and changed it around a bit, that's my next point.

   public static class Extensions
   {
       internal static bool RoughlyEquals(this Point point1, Point point2, float epsilon = CoordinateEpsilon)
       {
           return System.Math.Abs(point1.x - point2.x) < epsilon &&
                  System.Math.Abs(point1.y - point2.y) < epsilon &&
                  System.Math.Abs(point1.z - point2.z) < epsilon;
       }
   }
   

2. While my algorithm for your problem does contain many nested loops, I will go through it and explain my reasoning.

   I started off by creating a list of all possible locations within the main line where the subline could have been starting.

   var possibleStartingLocations = new List<int>();
   
   for (int i = 0; i < line.Count; i++)
   {
       if (line[i].RoughlyEquals(subline.First()))
           possibleStartingLocations.Add(i);
   }
   

3. Now any calculations we do from here, we will be starting with one of these points. you could call a method doing this calculation on every one of these starting indices, or have awesome nested for-loops!

   foreach (int i in possibleStartingLocations)
   {
   

4. Because the subline could be traveling either direction down the main line, we need to check both directions.

   foreach (int direction in new int[] { 1, -1 })
   {
   

5. At this point all we have to do is travel down the main line alongside the subline, and check to see if every point is equal in succession. If at any point they are not, we break out and try our next series. But if we do finish going through the points and they were all equal, we have a match

   int newPos;
   var found = true;
   for (int offset = 0; (newPos = offset * direction + i) >= 0 && newPos < line.Count; offset++)
   {
       if (!line[newPos].RoughlyEquals(subline[offset]))
       {
           found = false;
           break;
       }
   }
   if (found)
   {
       return true;
   }
   

6. If we never find a match, defaultly return false at the end of this method.

7. This is O(n) because you only ever iterate over the entire loop once. Then you only iterate over the parts you need, which does not add to your O

Here is the full dump of the new Extension methods class

public static class Extensions
{
    public static bool ContainsSubLine(this IList<Point> line, IList<Point> subline)
    {
        //TODO: Implement argument checking to make sure line and subline are not null and contain points.

        var possibleStartingLocations = new List<int>();

        //Find all possible starting points
        for (int i = 0; i < line.Count; i++)
        {
            if (line[i].RoughlyEquals(subline.First()))
                possibleStartingLocations.Add(i);
        }

        foreach (int i in possibleStartingLocations)
        {
            //Checking backwards and forwards from that point
            foreach (int direction in new int[] { 1, -1 })
            {
                int newPos;
                var found = true;
                for (int offset = 0; (newPos = offset * direction + i) >= 0 && newPos < line.Count; offset++)
                {
                    if (!line[newPos].RoughlyEquals(subline[offset]))
                    {
                        found = false;
                        break;
                    }
                }
                if (found)
                {
                    return true;
                }
            }
        }

        return false;
    }

    internal static bool RoughlyEquals(this Point point1, Point point2, float epsilon = CoordinateEpsilon)
    {
        return System.Math.Abs(point1.x - point2.x) < epsilon &&
               System.Math.Abs(point1.y - point2.y) < epsilon &&
               System.Math.Abs(point1.z - point2.z) < epsilon;
    }
}