score:4

Accepted answer

This code can found all collisions:

double[] minus = new double[]
{
    3, 24, 26, 23, 25, 18, 5,  5,  1, 10,
};
double[] plus = new ![alt text][1]double[]
{
    3,  8,  9, 11, 22, 25, 5,  5,  3, 7
};

var collisionsBetweenIndices =
Enumerable.Range(1, minus.Length - 1)
          .Where(i => ((minus[i - 1] - plus[i - 1] < 0) && (minus[i] - plus[i] > 0)) ||
                      ((minus[i - 1] - plus[i - 1] > 0) && (minus[i] - plus[i] < 0)) ||
                      ((minus[i - 1] - plus[i - 1] == 0) && (minus[i] - plus[i] == 0)))
          .ToArray();

var collisionsOnIndices =
Enumerable.Range(0, minus.Length)
          .Where(i => minus[i] == plus[i])
          .ToArray();

foreach (var idx in collisionsBetweenIndices)
    Console.WriteLine("Collision between {0} and {1}", idx - 1, idx);

foreach (var idx in collisionsOnIndices)
    Console.WriteLine("Collision on {0}", idx);

// RESULTS:
// Collision between 4 and 5
// Collision between 6 and 7
// Collision between 8 and 9
// Collision on 0
// Collision on 6
// Collision on 7

alt text

EDIT:

I did two different methods to distinguish the type of collisions (i.e. between indices or on indices), but if your purpouse is just to detect if there's a collision or not, just do the following:

var collisionDetected =
Enumerable.Range(0, minus.Length).Any(i =>
{
    if (minus[i] == plus[i])
        return true;
    if (i > 0 &&
        (((minus[i - 1] - plus[i - 1] < 0) && (minus[i] - plus[i] > 0)) ||
        ((minus[i - 1] - plus[i - 1] > 0) && (minus[i] - plus[i] < 0)) ||
        ((minus[i - 1] - plus[i - 1] == 0) && (minus[i] - plus[i] == 0))))
    {
        return true;
    }
    return false;
});

This code returns as soon as a collision is found, so it's generally faster the the above methods.

score:1

Why can't you just do:

for i=1...n
    if minus[i] > plus[i]
         return "Crossed over at index i"

score:4

To determine which is higher, just compare minus[i] to plus[i] - whichever has the greater value is the "higher" one at i.

To determine intersections, just keep track of which one is higher. When that changes, there was an intersection.

Edit

If you can't track history, then:

if ((minus[i-1] > plus[i-1]) != (minus[i] > plus[i])) then
  // there was an intersection
else
  // there was not an intersection

score:3

One way would be to break each series up into line-segments, and then compare corresponding (by index) segments from the two series.

Since you specifically mention LINQ, here's one way to achieve that. It's not very pretty:

var minusPairs = minus.Zip(minus.Skip(1), (prev, next) => new { prev, next });
var plusPairs = plus.Zip(plus.Skip(1), (prev, next) => new { prev, next });

var positions = minusPairs.Zip
               (plusPairs, (mPair, pPair) =>
                mPair.prev > pPair.prev 
                     && mPair.next > pPair.next ? "MinusAbove" :
                mPair.prev < pPair.prev
                     && mPair.next < pPair.next ? "PlusAbove" :
               "Intersection");

Output:

MinusAbove
MinusAbove
MinusAbove
Intersection

(Note that you don't get a PlusAbove for the last point because the only segment it is part of represents an Intersection. You may need to change this behaviour if desirable.)

To be honest, I would shy away from any 'cute' solution if you need to do anything even slightly more complicated than this (e.g. finding the intersection points). Good OO design is needed here.

score:1

public string DetermineCollisionInfo(double current, double next)
{
  string currentInfo =
    current == 0.0 ? "Plus and Minus have same value" :
    current < 0.0 && next > 0.0 ? "Intersection occurs" :
    current > 0.0 && next < 0.0 ? "Intersection occurs" :
    "No Intersection";

  string nextInfo =
    next > 0.0 ? "Plus will be on top" :
    next < 0.0 ? "Minus will be on top" :
    "Plus and Minus will have same value";

  return currentInfo + ".  " + nextInfo;
}

Then, later:

IEnumerable<double> differences = Enumerable
    .Range(0, minus.Length)
    .Select(i => plus[i] - minus[i]);

double current = differences.First();
IEnumerable<string> analysis = differences
  .Skip(1)
  .Select(next =>
  {
    string result = DetermineCollisionInfo(current, next);
    current = next;
    return result;
  });

foreach(string info in analysis)
{
  Console.WriteLine(analysis);
}

score:1

if minus and plus are list:

var plus1 = plus.Skip(1);
var retVal = minus
    .Skip(1)
    .Select((p,i) => new { index = i, value = (minus[i] > plus[i]) != (p > plus1[i])})
    .Where( p => !p.value);

Related Articles