Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 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 at 16:21
    
There are a variety of well-known substring algorithms which you could apply here. –  Daniel Wagner Mar 25 at 23:53
add comment

4 Answers 4

up vote 4 down vote accepted
  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;
    }
}
share|improve this answer
add comment

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)
    {
        // your implementation
    }
}

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.

share|improve this answer
    
Also, as @Olivier mentioned in his answer, you should also override GetHashCode when overriding Equals. –  Mat's Mug Mar 25 at 16:55
1  
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 at 17:54
add comment

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>.

share|improve this answer
    
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 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 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 at 16:39
2  
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 at 16:44
add comment

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.


This changes the needed logic

and then you could probably go one step further by adding the break where you assign contains = false; like this

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

not sure you want to do this as it would change the logic too much, but I am unsure why you do what you do with the breaks?


it looks like your logic is flawed.
your current code shows that if the first subline is contained the code will still cycle through the rest and change the contains variable to false again and you will lose your value.

share|improve this answer
    
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 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 at 16:58
    
maybe I am reading it wrong –  Malachi Mar 25 at 16:59
1  
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 at 17:05
1  
@Malachi break doesn't exit the current scope, it exits the current loop. (has 95% turned to 55%? ;) –  Mat's Mug Mar 25 at 17:15
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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