Linq join without equals

Question

I have a list of rectangles and a list of points. I want to construct a LINQ query that will match the list of points with their corresponding rectangles. Something like this:

// Does not compile
var matches = from rect in rectangles
              join point in points on rect.Contains(point)
              select new { rect, point };

How does one accomplish something like this with LINQ?

EDIT:

My lists are equal size - I have one point to match with one rectangle, and the rectangles don't overlap.

However, the point of the question isn't so much to solve this one specific problem. I'm interested, in general, how to join two lists on any condition other than simply 'equals'.

Answer 1

You can use multiple from clauses to achieve a join

 var matches = from p in points
               from r in rectangles
               where r.Contains(p)
               select new { r, p };

Multiple from clauses are more flexible than the join syntax (see myth 5 of 10 LINQ myths). You need to learn only this one and all joins will be easy.

Answer 2

You can use Enumerable.ToLookup to create a lookup table per rectangle:

var lookup = points.ToLookup(p => rectangles.First(r => r.Contains(point)));

Using this is similar to a grouping query:

foreach(var group in lookup)
{
    Console.WriteLine("Rectangle {0} contains:", group.Key);
    foreach(var point in group)
        Console.WriteLine("    {0}", point);
}

On a side note - this query is quadratic in nature, and likely to perform poorly with very large datasets. If you need to do this for many points and/or many rectangles, you may wish to investigate spatial data structures for quicker lookups. That may not be an issue in this case, however.