检测与给定矩形相交的矩形的快速方法

Question

我正在维护的应用程序具有自定义绘图功能，该功能在Graphics表面上绘制了一些“对象”王。对象边界用Rectangle来描述。

有时我需要检测矩形与给定矩形相交的对象。

如果对象的数量足够大，简单的重复这样的：

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

显然太慢（_objects这里是List<MyObjType>，IscribeRect是对象边界，并rc是一个给定的矩形）。

我在想如何更快地做到这一点。第一个想法是通过它们的矩形对对象进行“排序”，并将它们放入有序集合中......但我怀疑，我正在重新发明轮子。

是否有任何知名的方法来实现我想要的？

Answer 1

这可以使用Quadtrees来完成。您可以在这里找到一个C＃实现：Virtualized WPF Canvas（四叉树代码不严格相关WPF），也大量的信息在这里：ZoomableApplication2: A Million Items这里另一种实现方式：PriorityQuadTree

Answer 2

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

创建另一个函数来获取所有的边界线（获得四个点并从矩形1创建四行），并检查是否有任何行使用lineintersectsRect与另一个rectanglecare合并，如果其中任何一个返回true，则矩形1将与您的矩形R相交，则可以将其循环以检查矩形2与rectanglecompare相交等。 确保你不通过除零排除异常行