Check if rectangles intersect in Canvas XAML

c#, canvas, wpf, xaml

Solution

To check if your rectangle is intersecting with the others, the minimum number of interactions you need to do in the worst case is going through them all at least once; you can't avoid this fact. This means that in the worst case, you simply cannot go lower than a complexity of `O(n)`.

This complexity can can be achieved with a single loop like you do or you can simply use the LINQ method `.Any()`, which will stop as soon as there is an intersection (So we can get a best case of `O(1)`).

Here, the worst case is 'no intersection', because you need to check the next rectangle to see if that one will collide. The best case is represented by a hit on the first check.

Let's say that your collection is called coordinates and the Rect your are checking newRect, the check would become :

if (coordinates.Any(c => c.IntersectsWith(newRect)))
{
    //There is overlapping
}

With your last update, it's clear that you don't have "the rectangle coordinates" in a collection but the `Rectangle` from `Windows.Shapes`, which is not the same thing at all. `Rectangle` contains only the information on its width and height, not its own position.

You'll need to convert them to `Rect` before the loop by using their position on the canvas and their dimensions :

IEnumerable<Rect> coordinates = rectCollection.Select(r => new Rect(Canvas.GetLeft(r), Canvas.GetTop(r), r.Width, r.Height));

To exclude the sides, you can roll up your own extension method (As a matter of personal preference, I prefer to keep my ifs and lamdas clean):

public static class Extensions
{
    public static bool InteriorIntersectsWith(this Rect rect, Rect other)
    {
        return rect.IntersectsWith(other) && IsIntersectingInside(rect, other);
    }

    private static bool IsIntersectingInside(Rect rect, Rect other)
    {
        Rect intersectionArea = Rect.Intersect(rect, other);
        return intersectionArea.Width > 0 && intersectionArea.Height > 0;
    }
}

The logic is a little different than yours however, so if it works feel free to use the one you want. Basically I'm using the fact that the intersection area will have only one dimension if only the borders are touching.

So the check would change to

if (coordinates.Any(c => c.InteriorIntersectsWith(newRect)))
{
    //There is overlapping
}

Problem

I have a canvas, in which i draw different rectangles. I have the rectangle coordinates in a collection. Each time a rectangle is added to the canvas i need to check if it over laps other existing rectangle. I check a new rectangle with each existing Rectangle in the canvas to know if the rectangle overlaps with any other rectangle. Is this the most efficient solution? ``` foreach(System.Windows.Shapes.Rectangle r in rectCollection) { IntersectionDetail d1 = r.RenderedGeometry.FillContainsWithDetail(this.rect.RenderedGeometry); if(d1 == IntersectionDetail.Intersects) { MessageBox.Show("New Rectangle intersects with existing rectangle"); } } ```

Original source