Reading these might be a bit confusing at first, but essentially these checks determine how the edges of the two rectangles are situated with respect to each other. Top bound of R2 less than bottom bound of R1 The intersection of two axis-aligned rectangles can then be verified when the following four conditions are fulfilled: In the next section we'll have a look at how this works! Axis-aligned Rectangle CollisionĪ rectangle can be represented by four numbers, two that represent it's x and y coordinate, usually indicating the top left corner, as well as two numbers that represent its width and height starting from that positional coordinate. Axis aligned bounding boxes (rectangles) are popularly utilised as such a broad phase algorithm, because their collision is relatively cheap to compute. A popular approach in video games is dividing the problem into two phases, a broad phase where we determine objects in the scene that could potentially collide, which are then doubled down on in the narrow phase where the actual collisions are detected. Collision detection is a rather common problem in video games, where it's often of crucial importance that the algorithm used to determine these collisions is fast. I've already mentioned this in a section of a previous article: A Simple Solution for Shape Packing in 2D, but axis-aligned rectangles are super useful when you need to determine collisions of some type in an efficient manner. Here's an example:ĭealing with axis-aligned rectangles greatly simplifies certain tasks, like determining if they intersect for example. Something that isn't axis aligned can occur with a different orientation such that it lies rotated with respect to the coordinate axes. For example an axis-aligned rectangle would have it's edges parallel to the x and y axes. The term axis-aligned indicates that a shape is aligned with the coordinate axes. Beyond Rectangles: Polygon Intersections.Here's a quick index to the different sections of the article: Quick Index The methods described in this post might not be the most efficient ones for larger numbers of rectangles, but make up for that in simplicity. Albeit this, the word collision implies movement on behalf of the two rectangles and is probably better suited in that context. Lastly a note on terminology, for the most part I'll be using the words intersection and collision interchangeably, since they essentially mean the same thing: that two rectangles are touching or overlapping in some manner. In that manner this post covers a lot of ground, but for the sake of completeness I didn't want to leave anything out. We will also have a look at how to compute the intersection of two line segments in addition to a method that can determine if a point is contained within a polygonal shape (point in polygon test), both of which are important components of the polygon intersection test. Hence I extended the post to include this information as well. While working on a recent project however, I discovered that this intersection test can be extended to not only return the polygonal shape that is formed by the intersection of two non-axis aligned rectangles but also that of two convex polygons. This article initially began as a short post discussing strategies that can determine rectangle intersections and collisions, for both axis-aligned rectangles as well as arbitrarily rotated rectangles. Shoutout to Dave for all the helpful discussions over on discord! We'll also a method for intersections between axis-aligned rectangles, a function that can determine the intersection of two line segments, as well as a point in polygon test. In this post we'll work our way towards an algorithm that can compute convex polygon intersections.
0 Comments
Leave a Reply. |