A Line Intersecting Rectangles

Hi,

I have a bunch of rectangles simulating players for a football game I'm designing. I want to find out how many "players" are in between two points on the field. I have a start point (a defender trying to locate the ball carrier) and endpoint (the ball carrier). I need the number of other players in between those two points (I have all of their coordinates as well). The more traffic in the defender's field of vision the harder it will be to find the ball.

If this is a process is wicked complicated it won't be worth the effort to implement it as it is not crucial in what I'm trying to do. If it's medium or easy code then I will try it out.

Thanx!

try this:

vb Code:

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    'finds each picturebox that the specified area (r) fully contains
    For Each pb As PictureBox In Me.Controls.OfType(Of PictureBox)()
        If pb IsNot PictureBox1 Then
            Dim r As Rectangle = PictureBox1.Bounds
            Dim r2 As Rectangle = pb.Bounds
            r2.Intersect(r)
            If r2 = pb.Bounds Then
                MsgBox("area contains PictureBox")
            End If
        End If
    Next
End Sub

Hi neef, you need to find if each rectangle r intersect a line between two given points p1 and p2. As far as I can see .Paul's code only checks if two rectangles intersect.

I can think of a way to solve the problem which should be easy to code in in VB.Net.

First, define a rectangle of which p1 and p2 form the diagonal:

Code:

---

  Dim field As New Rectangle With _
          {.X = Math.Min(p1.X, p2.X), _
            .Y = Math.Min(p1.Y, p2.Y), _
            .Width = Math.Abs(p1.X - p2.X), _
            .Height = Math.Abs(p1.Y - p2.Y)}

---

Now for each player rectangle r (excluding the players at p1 and p2), check if its centre is inside "field":

Code:

---

Dim centre As New Point(r.Left + r.Width \ 2, r.Top + r.Height \2)
If field.Contains(centre) then ...

---

This exludes any rectangles that intersect with the geometrical line p1-p2, but not the part of it between p1 and p2. In other words, they could be in line, but not in the line of sight.

For each rectangle r which passes the above test, you need to check if it crosses the line anywhere. The easiest way is to check if all its corners are on the same side of the line. You could do that with the following function:

Code:

---

Private Function CornerIsAboveLine(ByVal corner As Point, ByVal p1 As Point, ByVal p2 As Point) As Boolean
        If p1.X = p2.X Then
            Return False 'return a value to avoid divide by zero when line p1-p2 is vertical.
        Else
          Return corner.Y < (p1.Y + (corner.X - p1.X) * (p2.Y - p1.Y) / (p2.X - p1.X))
        End If
    End Function

---

If all four corners of r return either CornerIsAboveLine = True or = False, then r is not in the line of sight. Otherwise it is.

I don't have time to work out a full code example now, but maybe you can take it from here.

BB

Edit: note that I just revised the first test.

[/code]

I just got around to checking my (off the cuff) code and I discovered to my horror there is an error in line 5 of the CornerIsAboveLine function. I have now edited it. The first test is also going to need a little more thought: there are some corner conditions where "rectangles intersect" will be wrong and others where "centre is in rectangle" will be wrong. Neef, can I assume you are treating the centre of each player rectangle as the player position? This is not what I would call "wicked complicated" but it takes some care to get it right.

I now see I misread .Paul's code: it tests if a small rectange is entirely inside a larger rectangle. Unfortunately it can't be applied to what I call field (a rectangle with the players at opposite corners). Imagine the line between players p1 and p2 is nearly horizontal or nearly vertical. A player (rectangle r) could be partly outside the field but still block the view. I think I can come up with a definitive test soon.

BB