Increase performance in sub-line detection

I have an algorithm for checking whether one line is contained within another. The lines I have are made up of an ordered array of points, which are just data structures with values for x, y and z. The lines are no necessarily straight. The subline does not need to be going in the same direction as the main line.

The algorithm I have currently is:

public static bool IsSubline(Point[] subline, Point[] line)
{

    int prevIndex = int.MaxValue;
    bool contains = false;

    foreach (Point point in subline)
    {
        for (int i = 0; i < line.Length; i++)
        {
            if (Equal(point, line[i]))
            {
                if (prevIndex == int.MaxValue || System.Math.Abs(prevIndex - i) == 1)
                {
                    prevIndex = i;
                    contains = true;
                    break;
                }
            }

            contains = false;
        }

        if (!contains)
        {
            break;
        }
    }

    return contains;
}

Equal is:

internal static bool Equal(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;
}

I feel like this could be done in a faster way, anyone have any suggestions?

Yes it can be done faster. Your algorithm has a \$O(n^2)\$ time.

Idea: store the indexes of the points of the line in a dictionary and use the points as key (I assume that two distinct points never have the same coordinates. If this is not the case, then an index list would have to be stored for each point).

var lineIndexes = new Dictionary();

//TODO: add the points of the line to the dictionary

foreach (int i = 0; i  0 && sublinePoint2.Equals(line[k - 1]) ||              // (previous one matches OR
          k < line.Lengh - 1 && sublinePoint2.Equals(line[k + 1]))) {//  next one matches)

        return true;
    }
}
return false;

This is \$O(n)\$, since the dictionaries have a constant access time.

Equal vs. Equals

Every object (other than System.Object) inherits Equals and GetHashCode from System.Object. Do not introduce your own Equal method but override Equals and GetHashCode in your own objects. This is necessary for right functioning of the dictionary and other .NET data structures.

If you cannot do that, there are overloads of the dictionary's constructor accepting an IEqualityComparer. Provide your own implementation of IEqualityComparer.

StackExchange Code Review Q#45320, answer score: 6