# 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?

-
It's Equal, sorry. I'm away from the computer for an hour or so, but it literally just compares the x's, y's, and z's to within an epsilon. – djcmm476 Mar 25 '14 at 16:07
just to clarify what you mean: contained means, whether each point in subline is also contained in line, correct? (line: {0,1,1},{1,3,3}; subline:{0.5,2,2}, {0.75, 2.5, 2.5} should not return true?) – Vogel612 Mar 25 '14 at 16:15
Ah, that's a good points you bring up actually. No, all we really have to check is that the actual points forming the line are matched, not any points that might be on the line between points. – djcmm476 Mar 25 '14 at 16:21
There are a variety of well-known substring algorithms which you could apply here. – Daniel Wagner Mar 25 '14 at 23:53
what if you have a line of 5 points and a sub-line of 3 points where the first and the last points of the line are not part of the subline? will this program say that the sub-line is not part of the line? – Malachi Jul 29 '14 at 21:49

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()))
}

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()))
}

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;
}
}

-
I think it's only O(n) if you assume that there are no repeated points. – Snowbody Jul 28 '14 at 19:22

That random static bool Equal method with an optional parameter, is confusing.

There's already object.Equals with that name and functionality - what you need here is custom equality behavior... and that is achieved by overriding object.Equals:

public struct LinePoint
{
public Point ApiPoint { get; set; }

public override bool Equals(object obj)
{
return Equals(obj, CoordinateEpsilon);
}

public bool Equals(object obj, float epsilon)
{
}
}


Note the optional parameter is replaced with a method overload.

The fact that Point is from an API that you can't modify, shouldn't stop you from extending the type, or to compose a new structure with it, which you can modify at will.

-
Also, as @Olivier mentioned in his answer, you should also override GetHashCode when overriding Equals. – Mat's Mug Mar 25 '14 at 16:55
There is a certain amount of allowance that his Equals method allows for. When dealing with float and double, the value is subject to change slightly due to the way it is stored, so when comparing point you need to give a certain amount of leeway in-case the value has changed. this kind of equals is also used a lot in 3d engines when you want to know if something is "roughly" in the same position. – BenVlodgi Mar 25 '14 at 17:54

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<Point, int>();

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

foreach (int i = 0; i < subline.Length - 1; i++) {
Point sublinePoint1 = subline[i];
Point sublinePoint2 = subline[i + 1];

int k; // Index in line.
If (lineIndexes.TryGetValue(sublinePoint1, out k) &&         // We found one matching point AND
( k > 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<TKey>. Provide your own implementation of IEqualityComparer<Point>.

-
you kinda break the abstraction level. your code requires a high level of understanding the problem in itself, and thus is hard to read. – Vogel612 Mar 25 '14 at 16:30
Yes (where I assume that one of the two is for filling the dictionary), but O(m + n) is equal to O(n) since only the behavior for n's going towards infinity is considered. The big-O notation is not a calculation of the actual time in seconds. O(n) only says: It's linear, but no more. – Olivier Jacot-Descombes Mar 25 '14 at 16:34
thanks for the lesson ;) my other point is still standing though. I think you should extract the if statement to a method, to make more clear what actually happens there. – Vogel612 Mar 25 '14 at 16:39
Ah, I was just about to ask about Equals there. Unfortunatly the Point object is from an API, and I can't update it. – djcmm476 Mar 25 '14 at 16:44

Just looking at the code, you could eliminate one Nested if statement from this

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;
}
}


and make it

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

if (!contains)
{
break;
}
}


It will look at the first expression and evaluate it, if it is true it will evaluate the second expression and decide if that is true, if both expressions are true then it will run the code inside the then block.

It looks like we can eliminate another if statement, the one that asks if contains is false. instead of that we can use a return because we don't want to keep going if something doesn't match we already know that the subline doesn't match.

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


The big problem that I am seeing is that the code you have currently will show that a line is not a sub-line if the sub-line is in the middle of the line.

-
The first break is because we have a a matching value at this value in the subline, and it's within 1 index of the previous one, so set contains to true and move on to the next one. The second break is there because, if we reach that point and contains is false, it means the current value of subline is not present in line at all, and so we mayaswell quit now, because subline is, in fact, not a subline (the liar). – djcmm476 Mar 25 '14 at 16:57
EDIT: I just noticed your edit, and I'm not sure what you mean, there only is one subline to be checked, we're looping through the points. – djcmm476 Mar 25 '14 at 16:58
The break exits the first for loop. – djcmm476 Mar 25 '14 at 17:03
msdn.microsoft.com/en-us/library/adbctzc4.aspx The first example there shows a break within an if exiting the enclosing for. I might be misunderstanding you though. – djcmm476 Mar 25 '14 at 17:05