Fast way to detect rectangles, which intersect with the given rectangle

Question

The application I'm maintaining has custom drawing functionality, which draws some king of "objects" on an Graphics surface. Object boundaries are described with Rectangle.

Sometimes I need to detect objects, whose rectangles are intersecting with given rectangle.

If the number of objects is large enough, simple iteration like this:

var objectsToManage = _objects.Where(_ => rc.IntersectsWith(_.InscribeRect));

obviously, too slow (_objects here is List<MyObjType>, IscribeRect is object boundaries, and rc is a given rectangle).

I'm thinking about how to do this much faster. First idea is to "sort" objects by theirs rectangles and put them into sorted set... But I'm suspecting, that I'm re-inventing the wheel.

Is there any well-known approaches to achieve what I want?

Simon Mourier · Accepted Answer · 2015-03-19 07:04:09Z

2

This is can be done using Quadtrees. You can find a c# implementation here: Virtualized WPF Canvas (the quadtree code is not strictly related to WPF), also lots of info here: ZoomableApplication2: A Million Items and another implementation here: PriorityQuadTree

answered Mar 19, 2015 at 7:04

Simon Mourier

141k22 gold badges269 silver badges320 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dennis Over a year ago

Thanks, I'll look into these articles.

Simon Mourier Over a year ago

@ErnodeWeerd - Even if the links disappear, the only mention of the 'quatree' term would be enough as an answer.

Dennis Over a year ago

@ErnodeWeerd: actually, I'm asking about concept/link... Obviously, this isn't a question, that could be answered win a couple lines of code.

balaji dileep kumar · Accepted Answer · 2015-03-19 08:07:42Z

0

    #region FnLineMerginRectandLines
    public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
    {
        return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
               (r.Contains(p1) && r.Contains(p2));
    }

    private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
    {
        float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
        float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);

        if (d == 0)
        {
            return false;
        }

        float r = q / d;

        q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
        float s = q / d;

        if (r < 0 || r > 1 || s < 0 || s > 1)
        {
            return false;
        }

        return true;
    }
    #endregion
public class Line
{
    private int Point1X;
    private int Point1Y;
    private int Point2X;
    private int Point2Y;
    public Point P1;
    public Point P2;

    public Line()
    {

    }
    public Line(int left, int top, int width, int height)
    {
        this.Point1X = Convert.ToInt32(left);
        this.Point1Y = Convert.ToInt32(top);
        this.Point2X = Convert.ToInt32(width);
        this.Point2Y = Convert.ToInt32(height);
        P1 = new Point(Point1X, Point1Y);
        P2 = new Point(Point2X, Point2Y);
    }
    public Line(string left, string top, string width, string height)
    {
        this.Point1X = Convert.ToInt32(left);
        this.Point1Y = Convert.ToInt32(top);
        this.Point2X = Convert.ToInt32(width);
        this.Point2Y = Convert.ToInt32(height);
        P1 = new Point(Point1X, Point1Y);
        P2 = new Point(Point2X, Point2Y);
    }   
    public Line(Point p1, Point P2)
    {
        this.P1 = p1;
        this.P2 = P2;
    }
}


public static List<Line>getfourborders(Rectangle RT)
    {
        Line topline = new Line(new Point(RT.Left,RT.Top),new Point(RT.Width+RT.Left,RT.Top));// Top Line
        Line leftline = new Line((new Point(RT.Left,RT.Top)),new Point(RT.Left,RT.Top+RT.Height));// left Line
        Line  rightline = new Line((new Point(RT.Left+RT.Width,RT.Top)),new Point(RT.Left + RT.Width,RT.Top+RT.Height));// Right Line
        Line bottomline = new Line((new Point(RT.Left,RT.Top+RT.Height)),new Point(RT.Left+RT.Width,RT.Top+RT.Height));//bottom line
        List<Line> borderlines = new List<Line>();
        borderlines.Add(leftline);
        borderlines.Add(topline);
        borderlines.Add(rightline);
        borderlines.Add(bottomline);
        return borderlines;
    }

 //YourObjectList() contains a rectangle type
        public class myobject
        {
            public myobject(object S, Rectangle RT)
            {
            this.Rt = RT;
            this.anyobjecttype= S;
            }
            public Rectangle Rt;
            public  object anyobjecttype ;
        }

        public List<myobject> CompareRectangles(List<myobject> Rect ,Rectangle GivenRectangle)
        {
            List<myobject> intersectingobjects = new List<myobject>();
            Rectangle CompareWith = new Rectangle();//"_objects.Where(_ => rc.IntersectsWith(_.InscribeRect));"

            foreach(myobject iterate in Rect)
            {
                List<Line> BorderLines = new List<Line>();
                BorderLines.AddRange(getfourborders(iterate.Rt));
                bool Intersects = BorderLines.Any(x=>LineIntersectsRect(x.P1,x.P2,CompareWith));
                if (Intersects)
                    intersectingobjects.Add(iterate);
            }
            return intersectingobjects;
        }

create another function to get all the border lines(get four points and create four lines from rectangle 1 ) and check if any of the line merges with another rectanglecompare using lineintersectsRect if any of that returns true then the rectangle 1 will intersect with your rectangle R, you can loop it to check rectangle 2 intersects with rectanglecompare and so on.. make sure that you don't pass divide by zero exception in line intersects with line

edited Mar 19, 2015 at 8:07

answered Mar 19, 2015 at 7:10

balaji dileep kumar

6428 silver badges12 bronze badges

5 Comments

Dennis Over a year ago

I didn't get your idea. Looks like it requires the iteration on objects collection anyway. Isn't it?

balaji dileep kumar Over a year ago

for a rectangle to intersect another rectangle any of the border line should intersect with the 2nd rectangle.. so i get my first rects borders and check if any of the line intersects with 2nd rectangle.....bool truefalse = borderlines.Any(x => LineIntersectsRect(x.P1, x.P2, CompareWith));

Dennis Over a year ago

The question isn't about "how to detect, that two rectangles are intersecting". Imagine, that there are tens of thousands of objects. My current code need to test every object in list.

Emond Over a year ago

@balajidileepkumar - Please write in sentences, using punctuation and proper casing. Your answer might be right but I can't read it.

balaji dileep kumar Over a year ago

you can iterate all the objects and check for all the rectangles .... if your list is large enough.. it will certainly take time depending on you r object list.. you can write, this is oop approach... sorry if i am naive

Collectives™ on Stack Overflow

Fast way to detect rectangles, which intersect with the given rectangle

2 Answers 2

3 Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related