More Advanced Collision Detection
To get the most out of this tutorial, you will need to understand the following :
if and for loop constructs
types
records
functions
circular collision detection
rectangular collision detection
Circle vs Rectangle
Assume that :
(x1, y1) is the lower left corner of the rectangle
(x2, y2) is the upper right corner of the rectangle
(x, y) is the center of the circle
r is the radius of the circle
The first way we can check if the circle and rectangle are intersecting is to check if any of the rectangle's four corners are inside of the circle. We already have two of the rectangle's corners (x1, y1) and (x2, y2). The other two corners will obviously be (x1, y2) and (x2, y1).
if (x1 - x)^2 + (y1 - y)^2 <= r^2 or (x1 - x)^2 + (y2 - y)^2 <= r^2 or (x2 - x)^2 + (y1 - y)^2 <= r^2 or (x2 - x)^2 + (y2 - y)^2 <= r^2
then we know we have a collision between the circle and the rectangle
But the circle and rectangle can intersect in such a way that none of the rectangle's corners are inside of the circle. Just imagine the circle on one of the rectangle's edges. First, let's think of this type of scenario happenning on one of the rectangle's horizontal edges. If this is the case, then either the highest point on the circle or the lowest point on the circle is inside of the rectangle. Similarly, for the vertical edges, the furthest left or furthest right point on the circle must be inside of the rectangle. So, we just check these four points to be in the rectangle. These four points on a circle are obvious :
highest : (x, y + r)
lowest : (x, y - r)
furthest right : (x + r, y)
furthest left : (x - r, y)
This is one long expression, and we can even pin it on to the last one using an or. But, to keep it neat, you might want to separate them. For example, I separated them in horizontal edge collisions and vertical edge collisions :
if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y - r > y1 and y - r < y2)
then there is an intersection
if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2)
then there is an intersection
These cases above do not cover all intersections of a circle and a rectangle, though. Can you think of a scenario where none of the four corners of the rectangle are inside of the circle and the highest, lowest, furthest left, or furthest right points of the circle are not inside the rectangle?
Imagine a circle and a square with the same center and the square's corners sticking out of the circle. If this is happening, then the center of the circle must be inside of the rectangle, so we can check for that last condition.
if x > x1 and x < x2 and y > y1 and y < y2
then the rectangle and circle are intersecting
So, we have created four expressions (that can all be combined into one expression using or if we really want to). If any of these expressions are true, then there is an intersection. If none of them are true, then there is no collision between the rectangle and the circle.
| code: | View.Set ("offscreenonly")
var x1, y1, x2, y2, x, y, b, r : int
x1 := 100
y1 := 100
x2 := 200
y2 := 200
r := 60
fcn circleRectangle (x, y, r, x1, y1, x2, y2 : real) : boolean
if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y - r > y1 and y - r < y2) then
result true
end if
if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2) then
result true
end if
if (x1 - x) ** 2 + (y1 - y) ** 2 <= r ** 2 or (x1 - x) ** 2 + (y2 - y) ** 2 <= r ** 2 or (x2 - x) ** 2 + (y1 - y) ** 2 <= r ** 2 or (x2 - x) ** 2 + (y2 - y) ** 2 <= r ** 2 then
result true
end if
result x > x1 and x < x2 and y > y1 and y < y2
end circleRectangle
loop
Mouse.Where (x, y, b)
Draw.Box (x1, y1, x2, y2, black)
Draw.Oval (x, y, r, r, blue)
put circleRectangle (x, y, r, x1, y1, x2, y2)
View.Update
delay (10)
cls
end loop |
Point on Ellipse
The formula for a point (x, y) on an ellipse is :
((e.x - x)/rx)^2 + ((e.y - y)/ry)^2 = 1
where (e.x, e.y) is the center of the ellipse
e.rx is the x-radius (the distance from the center to the outside of the ellipse along the x-axis)
e.ry is the y-radius (the distance from the center to the outside of the ellipse along the y-axis)
Let's write the expression for determining if a point (x, y) is inside of a circle :
(c.x - x)^2 + (c.y - y)^2 <= r^2
this can be rewritten as :
((c.x - x)/r)^2 + ((c.y - y)/r)^2 <= 1
Do you see the similarity to the ellipse equation? It just so happens that for the ellipse, the expression is similar to the circle one except it uses the x-radius and y-radius :
((e.x - x)/rx)^2 + ((e.y - y)/ry)^2 <= 1
If the above expression evaluates to true, then the point is on or inside the ellipse. Otherwise, the point is outside of the ellipse.
Go here to find out about the derivation of the ellipse formula and more information about the ellipse.
| code: | View.Set ("offscreenonly")
type ellipse :
record
x, y, rx, ry : real
clr : int
end record
var e : ellipse
var x, y, button : int
e.x := 100
e.y := 100
e.rx := 85
e.ry := 32
e.clr := green
fcn pointEllipse (e : ellipse, x, y : real) : boolean
result ((e.x - x) / e.rx) ** 2 + ((e.y - y) / e.ry) ** 2 <= 1
end pointEllipse
loop
Mouse.Where (x, y, button)
Draw.Oval (round (e.x), round (e.y), round (e.rx), round (e.ry), e.clr)
put pointEllipse (e, x, y)
View.Update
delay (10)
cls
end loop |
Math Review : Finding the point of intersection of two lines
The equation of a line is :
y = mx + b OR where m is the slope and b is the y-intercept
y - y0 = m * (x - x0) where m is the slope and (x0, y0) is a known point on the line
Suppose we are given two points on two different lines and we want to find the point of intersection of these two lines
(x1, y1) and (x2, y2) are on the first line
(x3, y3) and (x4, y4) are on the second line
then, we have to first find the slopes of both lines so we can write the equation of each line :
m1 = (y2 - y1) / (x2 - x1) slope of the first line
m2 = (y4 - y3) / (x4 - x3) slope of the second line
Now, we write the equations of both lines :
y - y1 = m1 * (x - x1)
y - y3 = m2 * (x - x3)
To solve for the point of intersection, we solve for x and y in this system of equations.
y = m1*x - m1*x1 + y1
y = m2*x - m1*x3 + y3
m1*x - m1*x1 + y1 = m2*x - m2*x3 + y3
m1*x - m2*x = -m2*x3 + y3 + m1*x1 - y1
(m1 - m2) * x = -m2*x3 + y3 + m1*x1 - y1
x = (-m2*x3 + y3 + m1*x1 - y1) / (m1 - m2)
y = m1*(x - x1) + y1 <-we substitute x which we computed above into this equation to get y
And (x, y) will be the point of intersection.
Line Segment vs. Line Segment
Lines extend infinitely (have an infinite length), while line segments have two endpoints and a finite length. When dealing with graphics, line segments are usually more relevant. Any two non-parallel lines are intersecting, but this can not be said for line segments.
Suppose the first line segment has endpoints (x1, y1) and (x2, y2).
Suppose the second line segment has endpoints (x3, y3) and (x4, y4).
To determine whether or not two line segments are intersecting, we first treat them as lines. We find the slope of each line and calculate the intersection point.
m1 = (y2 - y1) / (x2 - x1)
m2 = (y4 - y3) / (x4 - x3)
intX = (-m2 * x3 + y3 + m1 * x1 - y1) / (m1 - m2)
intY = (m1 * (intX - x1) + y1)
Now we have the intersection point (intX, intY) of the two lines, but remember, we have line segments. So, we check if this point of intersection is on BOTH line segments. If it is, then the line segments are intersecting. If it's not on one or both of the line segments, then there is no intersection.
To check if this point is on the line segment, we just check if its x-coordinates are between the x coordinates of the endpoints of the first and second line. We do the same with its y coordinate. After some logic, it can be shortened to :
intX >= max (min (x1, x2), min (x3, x4)) and intX <= min (max (x1, x2), max (x3, x4)) and
intY >= max (min (y1, y2), min (y3, y4)) and intY <= min (max (y1, y2), max (y3, y4))
if the above expression is true, then the line segments are intersecting.
| code: | View.Set ("offscreenonly")
var x1, y1, x2, y2, x3, y3, x4, y4, angle : real
var x, y, button : int
angle := 90
x1 := 100
y1 := 100
x2 := 200
y2 := 200
fcn lineLine (x1, y1, x2, y2, x3, y3, x4, y4 : real) : boolean
var m1 := (y2 - y1) / (x2 - x1 + 1e-5)
var m2 := (y4 - y3) / (x4 - x3 + 1e-5)
var intX := round ((-m2 * x3 + y3 + m1 * x1 - y1) / (m1 - m2))
var intY := round ((m1 * (intX - x1) + y1))
result intX >= max (min (x1, x2), min (x3, x4)) and intX <= min (max (x1, x2), max (x3, x4)) and
intY >= max (min (y1, y2), min (y3, y4)) and intY <= min (max (y1, y2), max (y3, y4))
end lineLine
loop
Mouse.Where (x, y, button)
x3 := x
y3 := y
if button = 1 then
angle += 1
end if
x4 := x + 70 * cosd (angle)
y4 := y + 70 * sind (angle)
Draw.Line (round (x1), round (y1), round (x2), round (y2), blue)
Draw.Line (round (x3), round (y3), round (x4), round (y4), red)
put lineLine (x1, y1, x2, y2, x3, y3, x4, y4)
View.Update
delay (10)
cls
end loop |
Line Segment vs. Circle
We know by know that if the distance from the line to the center of the circle is less than the radius of the circle, then the line segment must be intersecting with the circle. But, we can do even better, the closest point on this line segment to the center of the circle must be inside the circle for an intersection to occur. So now the problem becomes finding the point on the line segment that is the closest to the center of the circle.
Let :
(x, y) be the center of the circle
r be the radius of the circle
(x1, y1) and (x2, y2) be the endpoints of the line segment
Now, first let's treat the line segment as a line and find the point on the line closest to the center of the circle. We'll call the line (l).
For this, we assume the geometric property that the shortest path from a point to a line is the path perpendicular to the line.
Assuming this, we now have a second line and we know its slope will be perpendicular to the original line (l) and it will go through the center of the circle. We find the intersection point of the original line (l) and the new perpendicular line.
m = (y2 - y1) / (x2 - x1)
M = -1 / m
X = (m * x1 - y1 - M * x + y) / (m - M)
Y = m * (X - x1) + y1
where m is the slope of the original line (l)
M is the slope of the new perpendicular line
(X, Y) is the point of intersection between the two lines
Now we have the point on the line that is the shortest distance away from the center of the circle. But wait, we have a line segment to start with, so we have to check if this point of intersection is actually even on our line segment.
if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2)
then the point of intersection is on the line segment. Now, we check if this point is inside the circle using circular collision.
(px - X) ** 2 + (py - Y) ** 2 <= r ** 2
If that expression is true then the closest point on the line segment is inside of the circle and there is an intersection between the line segment and the circle.
But what if the point of intersection was not on our line segment (the first if statement evaluated to false)? Then we conclude that the closest point on the line segment to the center of the circle must be one of the endpoints (whichever one is closer).
Since our general circular collision compares if the distance squared is less than or equal to the radius squared, we can check which distance from endpoint to center squared is less and then see if it less than or equal to the radius squared.
min ((px - x1) ** 2 + (py - y1) ** 2, (px - x2) ** 2 + (py - y2) ** 2) <= r ** 2
If the above expression evaluates to true, then you have an intersection between the circle and the line segment. If it evaluates to false, then there is no intersection.
Bringing our two conditions together, we get pseudocode like this :
if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2) then
result (x - X) ** 2 + (y - Y) ** 2 <= r ** 2
else
result min ((x - x1) ** 2 + (y - y1) ** 2, (x - x2) ** 2 + (y - y2) ** 2) <= r ** 2
| code: | View.Set ("offscreenonly")
var x, y, button, x1, y1, x2, y2, r : int
x1 := 100
y1 := 100
x2 := 100
y2 := 200
r := 25
fcn circleLine (px, py, r, x1, y1, x2, y2 : real) : boolean
var m := (y2 - y1) / (x2 - x1 + 1e-8)
var M := -1 / m
var X := (m * x1 - y1 - M * px + py) / (m - M)
var Y := m * (X - x1) + y1
if round (X) >= min (x1, x2) and round (X) <= max (x1, x2)
and round (Y) >= min (y1, y2) and round (Y) <= max (y1, y2) then
result (px - X) ** 2 + (py - Y) ** 2 <= r ** 2
else
result min ((px - x1) ** 2 + (py - y1) ** 2, (px - x2) ** 2 + (py - y2) ** 2) <= r ** 2
end if
end circleLine
loop
Mouse.Where (x, y, button)
put circleLine (x, y, r, x1, y1, x2, y2)
Draw.Line (x1, y1, x2, y2, black)
Draw.Oval (x, y, r, r, blue)
View.Update
delay (30)
cls
end loop |
Similar Ellipse vs Similar Ellipse
Well, if you use the circle again, let's write the expression that determines whether or not two circles are intersecting :
(c1.x - c2.x)^2 + (c1.y - c2.y)^2 <= (c1.r + c2.r)^2 OR
(c1.x - c2.x)^2 / (c1.r + c2.r)^2 + (c1.y - c2.y)/r)^2 / (c1.r + c2.r)^2 <= 1
Well, if we plug in the sum of the ellipses' x-radii for the first r and the sum of the ellipses' y-radii for the second r, then we have :
(e1.x - e2.x) ** 2 / (e1.rx + e2.rx) ** 2 + (e1.y - e2.y) ** 2 / (e1.ry + e2.ry) ** 2 <= 1
Unfortunately, that does not work for all ellipses. It only works for what I call similar ellipses (probably not the right mathematical term!). When I say the ellipses are similar, I mean that their x and y radii are proportional. So,
e1.rx / e1.ry = e2.rx / e2.ry
For example, if an ellipse has an x-radius of 25 and a y-radius of 40, then a similar ellipse might have an x-radius of 50 and a y-radius of 80.
I have yet to attempt to geometrically prove this, but the reason has something to do with the point of intersection of similar ellipses always being on the vector joining the two centers of the ellipses. So, if the expression we declared above is true, then the similar ellipses intersect. If that expression is false, then there is no collision.
| code: | View.Set ("offscreenonly")
type ellipse :
record
x, y, rx, ry, clr : int
end record
var e1, e2 : ellipse
var x, y, b : int
e1.x := 100
e1.y := 100
e1.rx := 90
e1.ry := 50
e1.clr := red
e2.rx := 45
e2.ry := 25
e2.clr := blue
fcn ellipseEllipse (e1, e2 : ellipse) : boolean
result ((e2.x - e1.x) / (e1.rx + e2.rx)) ** 2 + ((e2.y - e1.y) / (e1.ry + e2.ry)) ** 2 <= 1
end ellipseEllipse
loop
Mouse.Where (x, y, b)
e2.x := x
e2.y := y
Draw.Oval (e1.x, e1.y, e1.rx, e1.ry, e1.clr)
Draw.Oval (e2.x, e2.y, e2.rx, e2.ry, e2.clr)
put ellipseEllipse (e1, e2)
View.Update
delay (15)
cls
end loop |
Math Lesson : Determining which side of a vector a point is on (left or right?)
If you have a vector in 2 dimensions v with a tip of (x1, y1) and a tail of (x2, y2) and a point p (x, y), and you want to determine if the point is to the left or to the right of the vector, you use a cross product.
First, we construct two new vectors. One will go from the point p to the tail (start) of the vector, and the other will go from the point p to the tip (end) of the vector.
The first vector (tail to point) :
(x - x1, y - y1, 0)
The second vector (tip to point) :
(x - x2, y - y2, 0)
Note that the z component of the vectors will be 0 because we're dealing in 2 dimensions.
Now, if the point p is to the right of the original vector v, then the cross product of our two constructed vectors will be pointing out of the screen (if you know the right-hand rule, you can confirm this). If the point p is to the left, the cross product will be going into the screen. Well, if the cross product is coming out of the screen, then the z-component will be negative; and if the cross product is going into the screen then the z-component will be positive. (Note, if the point is right on the line, then the two constructed vectors' cross product would obviously be 0.)
So, we just have to check the sign of the z-component of the cross product. The z-component of the cross product can be computed like this :
(y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)
So, if the sign of the above calculation is negative, then the point is to the right of the vector. If the sign is positive, then the point is to the left of the vector. If the above calculation is 0, then the point is on the vector.
Point in Convex Polygon
Let's say the array that represents the convex polygon's x coordinates is px and the array that represents the convex polygon's y coordinates is py. Let's call our point we are testing p (x, y).
In order to use the Draw.Polygon procedure, you must have your coordinates in your arrays in order. Well, since we're dealing with a convex polygon, the points must go in a clockwise or counter-clockwise direction. Now, imagine each edge of the polygon as a vector so that the polygon creates either a clockwise or counter-clockwise path. If your path is clockwise, then all points inside of the polygon are to the right of each edge vector. If your path is counterclockwise, then all points inside the polygon are to the left of each edge vector. All points outside of the polygon are to the left of some edge vectors and to the right of others regardless if the path is clockwise or counter-clockwise.
Now, all we do is check if our point p is to the right of all the edges of the polygon or to the left of all the edges of our polygon using the method learned in the above section.
for each edge of the polygon
z-com = (y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)
where (x1, y1) is the start point (tail) of the edge vector and (x2, y2) is the ending point (tip) of the edge vector.
We check if all the z-components are the same sign (or 0; if we include a point on the polygon as inside). If all of the z-components are the same sign then the point is inside of the polygon. If at least one of them is not the same sign, then the point is outside of the convex polygon.
| code: | View.Set ("offscreenonly")
var px : array 1 .. 8 of int := init (100, 80, 80, 100, 120, 140, 140, 120)
var py : array 1 .. 8 of int := init (100, 120, 140, 160, 160, 140, 120, 100)
var x, y, button : int
fcn pointPolygon (px, py : array 1 .. * of int, x, y : real) : boolean
var n := upper (px)
var z : array 1 .. n of real
for i : 1 .. n - 1
z (i) := (y - py (i)) * (px (i + 1) - px (i)) - (x - px (i)) * (py (i + 1) - py (i))
end for
z (n) := (y - py (n)) * (px (1) - px (n)) - (x - px (n)) * (py (1) - py (n))
for i : 2 .. n
if sign (z (i)) not= sign (z (1)) and sign (z (i)) not= 0 then
result false
end if
end for
result true
end pointPolygon
loop
Mouse.Where (x, y, button)
Draw.Polygon (px, py, 8, blue)
put pointPolygon (px, py, x, y)
View.Update
delay (10)
cls
end loop |
Math Lesson : Projecting a point onto a line going through the origin
If we want to project a point p (x, y) onto a line going through (0, 0) called v(vX, vY), we can use this formula :
proj.x = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vx
proj.y = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vy
Note that what's in the square brackets is the same for both proj.x and proj.y, and can be said as the dot product of the position vector of the point p with the vector v, divided by v dot v.
Convex Polygon vs. Convex Polygon
If two polygons are not intersecting, there is always a line (with infinite length) that can be drawn between them. In fact, a line can be drawn between the polygons will actually be parallel to one edge of one of the polygons. If they are intersecting, then no such line can be drawn.
So, how do we test if a line parallel to one of the 2 polygons' edges will be able to separate the polygons? Well, let's start with the first edge of the first polygon. We take a line perpendicular to this and, for simplicity, let's have this line going through (0, 0). This line will act as an axis. If we project both polygons onto this axis and the projections of the polygons are not overlapping, then the first edge of the first polygon has a line parallel to it that can separate the polygons. Simply put, there is no intersection between the polygons.
We do this for every edge of both polygons. The instant that the projections of both polygons onto a perpendicular axis are not overlapping, then we know we have no collision between the two convex polygons. If the projections overlap on every perpendicular to every edge of both polygons, then there is an intersection between the polygons.
We have one more problem which you may or may have not figured out. What is meant by projecting a polygon onto a line (axis)? By this, I just mean project every point of the polygon onto the axis and join them with a line.
So, in psuedocode :
for each edge of the polygon
find perpendicular axis going through (0, 0)
project polygon 1 onto this axis
project polygon 2 onto this axis
check if the two projection lines are overlapping
| code: | View.Set ("offscreenonly")
var x1 : array 1 .. 6 of int := init (100, 70, 100, 130, 160, 130)
var y1 : array 1 .. 6 of int := init (100, 130, 160, 160, 130, 100)
var a : array 1 .. 8 of int := init (0, -30, -30, 0, 30, 60, 60, 30)
var b : array 1 .. 8 of int := init (0, 30, 60, 90, 90, 60, 30, 0)
var x2, y2 : array 1 .. upper (a) of int
var x, y, button : int
fcn Min (arr : array 1 .. *, 1 .. * of real, n : int) : real
var minimum := arr (n, 1)
for i : 2 .. upper (arr, 2)
if arr (n, i) < minimum then
minimum := arr (n, i)
end if
end for
result minimum
end Min
fcn Max (arr : array 1 .. *, 1 .. * of real, n : int) : real
var maximum := arr (n, 1)
for i : 2 .. upper (arr, 2)
if arr (n, i) > maximum then
maximum := arr (n, i)
end if
end for
result maximum
end Max
fcn polygonPolygon (x1, y1, x2, y2 : array 1 .. * of int) : boolean
var X11 : array 1 .. upper (x1), 1 .. upper (x1) of real
var X12 : array 1 .. upper (x1), 1 .. upper (x2) of real
var X21 : array 1 .. upper (x2), 1 .. upper (x1) of real
var X22 : array 1 .. upper (x2), 1 .. upper (x2) of real
for i : 1 .. upper (x1)
var nx1, ny1 : real
if i = upper (x1) then
nx1 := -1 / (x1 (1) - x1 (upper (x1)) + 1e-8)
ny1 := -1 / (y1 (1) - y1 (upper (y1)) + 1e-8)
else
nx1 := -1 / (x1 (i + 1) - x1 (i) + 1e-8)
ny1 := -1 / (y1 (i + 1) - y1 (i) + 1e-8)
end if
for j : 1 .. upper (x1)
X11 (i, j) := ((x1 (j) * nx1 + y1 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1
end for
for j : 1 .. upper (x2)
X12 (i, j) := ((x2 (j) * nx1 + y2 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1
end for
end for
for i : 1 .. upper (x1)
if Max (X11, i) < Min (X12, i) or Max (X12, i) < Min (X11, i) then
result false
end if
end for
for i : 1 .. upper (x2)
var nx, ny : real
if i = upper (x2) then
nx := -1 / (x2 (1) - x2 (upper (x2)) + 1e-8)
ny := -1 / (y2 (1) - y2 (upper (y2)) + 1e-8)
else
nx := -1 / (x2 (i + 1) - x2 (i) + 1e-8)
ny := -1 / (y2 (i + 1) - y2 (i) + 1e-8)
end if
for j : 1 .. upper (x1)
X21 (i, j) := ((x1 (j) * nx + y1 (j) * ny) / (nx ** 2 + ny ** 2)) * nx
end for
for j : 1 .. upper (x2)
X22 (i, j) := ((x2 (j) * nx + y2 (j) * ny) / (nx ** 2 + ny ** 2)) * nx
end for
end for
for i : 1 .. upper (x2)
if Max (X21, i) <= Min (X22, i) or Max (X22, i) <= Min (X21, i) then
result false
end if
end for
result true
end polygonPolygon
loop
Mouse.Where (x, y, button)
for i : 1 .. upper (a)
x2 (i) := a (i) + x
y2 (i) := b (i) + y
end for
Draw.Polygon (x1, y1, upper (x1), red)
Draw.Polygon (x2, y2, upper (x2), blue)
put polygonPolygon (x1, y1, x2, y2)
View.Update
delay (10)
cls
end loop
|
|
)
