Naive ideas on basic 2D collision detection with simple shapes - Printable Version +- Save-Point (https://www.save-point.org) +-- Forum: Games Development (https://www.save-point.org/forum-4.html) +--- Forum: Tutorials (https://www.save-point.org/forum-19.html) +--- Thread: Naive ideas on basic 2D collision detection with simple shapes (/thread-5850.html)

Naive ideas on basic 2D collision detection with simple shapes - DoubleX - 07-05-2016 I'm only going to cover simple shapes like Points, Straight Lines, Circular Arcs, Circular Sectors and Simple Polygons, by using cartesian coordinates, basic algebra and Euclidean 2D geometry only. More complex shapes like ellipse and parabolas won't be covered, and more advanced maths like polar coordinates and affine spaces won't be used. No solid proofs will be covered as well. The below aims to always ensure 100% correctness, even for the teleportation cases, although it indeed fails a bit and badly when few and many shapes move quickly respectively. Points It's just an ordered x, y pair in the cartesian coordinate system. Straight Lines It's just the line between 2 specified points. The line will be represented by its corresponding linear equation in the form of y = mx + c. The rotation and translation offsets, valid x and y ranges and midpoint of the straight line will be used as well. Users only has to define those 2 specified points. The rest will be generated by scripts upon initializing the point. Circular Arcs A virtual circular sector will be used to implement a circular arc, which is the real shape. Check below for Circular Sectors. The midpoint is used in the circular arc as well. Circular Sectors It's a system of 3 inequalities in 2 unknowns, including 2 linear ones in the form of y >= mx + c, y > mx+ c, y <= mx+ c or y < mx+ c, and 1 inequality of circle in the form of (x - h) ^ 2 + (y - k) ^ 2 <= r ^ 2 or (x - h) ^ 2 + (y - k) ^ 2 < r ^ 2. The center, radius, rotation and translation offsets, and associated equations for those inequalities will be used as well. Note that the center is also the intersecting point of those 2 linear inequalities. Users only has to define the center, radius, and those 2 linear inequalities. The rest will be generated by scripts upon initializing the circular sector. Simple Polygons It's a system of linear inequalities in 2 unknowns. The number of inequalities is that of the edges. The vertexes, triangles of the polygon touching its edges and their incenters, an arbitrary center inside the polygon, the associated linear equations for those linear inequalities with their valid x and y ranges, the rotation and translation offsets, and the bounding rectangle or circular sector and inner circular sector or rectangle(analogous to inner circle) are used as well. Users only has to define the vertexes, an arbitrary center inside the polygon, and whether a rectangle or circular sector will be used to bound the simple polygon. The rest will be generated by scripts upon initializing the simple polygon. There are 5(5 + 1) / 2 = 15 possible cases: Points vs Points, Points vs Straight Lines, Points vs Circular Arcs, Points vs Circular Sectors, Points vs Simple Polygons, Straight Lines vs Straight Lines, Straight Lines vs Circular Arcs, Straight Lines vs Circular Sectors, Straight Lines vs Simple Polygons, Circular Arcs vs Circular Arcs, Circular Arcs vs Circular Sectors, Circular Arcs vs Simple Polygons, Circular Sectors vs Circular Sectors, Circular Sectors vs Simple Polygons, and Simple Polygons vs Simple Polygons. For all cases, the collision flag and relative positions between 2 shapes will be stored upon change per frame. If the relative positions between 2 shapes remains unchanged, it's certain that their collision flag doesn't need to change and can be used directly. The time complexity here's O(1). Points vs Points Just compare if they have both the same x and y coordinates. The time complexity's O(1). Points vs Straight Lines The point's reference point will be adjusted to be that of the straight line. The time complexity here's O(1). Then just check if the point's x and y coordinates are within the valid ranges of those of the straight line, and if that point's an solution to that linear equation. The time complexity here's O(1). The combined time complexity's O(1). Points vs Circular Arcs The point's reference point will be adjusted to be that of the circular arc. The time complexity here's O(1). Then just check if the distance between the point and the virtual center of the circular arc equals to the virtual radius of that circular arc, and if that point satisfies the 2 virtual linear inequalities in 2 unknowns.The time complexity here's O(1). The combined time complexity's O(1). Points vs Circular Sectors Same as Points vs Circular Arcs, except that whether the distance between the point and the center is less than or equal to, or less than, the radius is checked instead of checking against the equal condition. Points vs Simple Polygons The point's reference point will be adjusted to be that of the simple polygon. The time complexity here's O(1). The point will first the checked against the bounded rectangle or circular sector of the simple polygon. Checking a point against a circular sector goes to Points vs Circular Sectors, and that against a rectangle will be checking if both the x and y coordinates of the point lines between the minimum and maximum x and y coordinates of the rectangle. The time complexity here's O(1). If the point doesn't collide with the bounded rectangle or circular sector of the simple polygon, then that point isn't colliding with that simple polygon itself. The combined time complexity will be O(1). If that's not the case, then check the point against the inner rectangle or circular sector of the simple polygon, which is essentially the same as checking against the bounding ones. If the point collides with the inner rectangle or circular sector of the simple polygon, then so does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check if the point satisfies all the linear inequalities of the simple polygon. The time complexity here's O(E), where E is the number of edges. The combined time complexity will be O(E) in this case. Straight Lines vs Straight Lines Either straight line's reference point will be adjusted to be that of the other. The time complexity here's O(1). Then just check if the 2 linear equations has solutions and whether the they lie within the valid ranges of both straight lines. The time complexity here's O(1). The combined time complexity's O(1). Straight Lines vs Circular Arcs The straight line's reference point will be adjusted to be that of the circular arc. The time complexity here's O(1). Then just check if the linear equation and the equation of circle has solutions and whether they satisfy the valid ranges of the straight line, and the 2 linear inequalities of the circular arc. The time complexity here's O(1). Straight Lines vs Circular Sectors The straight line's reference point will be adjusted to be that of the circular sector. The time complexity here's O(1). The midpoint of the straight line will be checked against the circular sector. Checking a point against a circular sector goes to Points vs Circular Sectors. The time complexity here's O(1). If the midpoint collides with the circular sector, then so does the straight line. The combined time complexity will be O(1). If that's not the case, then it's certain that the straight line won't completely lie within the circular sector, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the straight line collides with the linear equations or equation of circle of the circular sector will suffice. They go to Straight Lines vs Straight Lines and Straight Lines vs Circular Arcs. The time complexity here's O(1). The combined time complexity will be O(1) in this case. Straight Lines vs Simple Polygons The straight line's reference point will be adjusted to be that of the simple polygon. The time complexity here's O(1). The straight line will be checked against the bounded rectangle or circular sector of the simple polygon. Checking a straight line against a circular sector goes to Straight Lines vs Circular Sectors. That against a rectangle will be checking the midpoint of the straight line against that rectangle. Checking a point against a simple polygon goes to Points vs Simple Polygons. If the midpoint collides with the rectangle, then so does the straight line. The time complexity will be O(1) but not O(E), as the number of edges of a rectangle's always 4. If that's not the case, then it's certain that the straight line won't completely lie within the rectangle, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the straight line collides with the linear equations of the rectangle will suffice. It goes to Straight Lines vs Straight Lines. The time complexity here's O(1). If the straight line doesn't collide with the bounded rectangle or circular sector, then neither does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the straight line against the inner rectangle or circular sector of the simple polygon, which is essentially the same as checking against the bounding ones. If the straight line collides with the inner rectangle or circular sector of the simple polygon, then so does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the midpoint of the straight line against the simple polygon. Checking a point against a simple polygon goes to Points vs Simple Polygons. If the midpoint collides with the simple polygon, then so does the straight line. The combined time complexity will be O(E). If that's not the case, then it's certain that the straight line won't completely lie within the simple polygon, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the straight line collides with the linear equations of the simple polygon will suffice. It goes to Straight Lines vs Straight Lines. The time complexity here's O(E) but not O(1), as E instead of 1 straight lines have to be checked against. The combined time complexity will be O(E) in this case. Circular Arcs vs Circular Arcs Either circular arc's reference point will be adjusted to be that of the other. The time complexity here's O(1). Then just check if the equation of circles has solutions and whether they satisfy all the 4 linear inequalities of the circular arcs. The time complexity here's O(1). Circular Arcs vs Circular Sectors The circular arc's reference point will be adjusted to be that of the circular sector. The time complexity here's O(1). The midpoint of the circular sector will be checked against the circular sector. Checking a point against a circular sector goes to Points vs Circular Sectors. The time complexity here's O(1). If the midpoint collides with the circular sector, then so does the circular arc. The combined time complexity will be O(1). If that's not the case, then it's certain that the circular arc won't completely lie within the circular sector, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the circular arc collides with the linear equations or equation of circle of the circular sector will suffice. They go to Straight Lines vs Circular Arcs and Circular Arcs vs Circular Arcs. The time complexity here's O(1). The combined time complexity will be O(1) in this case. Circular Arcs vs Simple Polygons The circular arc's reference point will be adjusted to be that of the simple polygon. The time complexity here's O(1). The circular arc will be checked against the bounded rectangle or circular sector of the simple polygon. Checking a circular arc against a circular sector goes to Circular Arcs vs Circular Sectors. That against a rectangle will be checking the midpoint of the circular arc against that rectangle. Checking a point against a simple polygon goes to Points vs Simple Polygons. If the midpoint collides with the rectangle, then so does the circular arc. The time complexity will be O(1) but not O(E), as the number of edges of a rectangle's always 4. If that's not the case, then it's certain that the circular arc won't completely lie within the rectangle, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the circular arc collides with the linear equations of the rectangle will suffice. It goes to Straight Lines vs Circular Arcs. The time complexity here's O(1). If the circular arc doesn't collide with the bounded rectangle or circular sector, then neither does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the circular arc against the inner rectangle or circular sector of the simple polygon, which is essentially the same as checking against the bounding ones. If the circular arc collides with the inner rectangle or circular sector of the simple polygon, then so does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the midpoint of the circular arc against the simple polygon. Checking a point against a simple polygon goes to Points vs Simple Polygons. If the midpoint collides with the simple polygon, then so does the circular arc. The combined time complexity will be O(E). If that's not the case, then it's certain that the circular arc won't completely lie within the simple polygon, meaning the former must intersect with the perimeter of the latter in order to collide. So checking whether the circular arc collides with the linear equations of the simple polygon will suffice. It goes to Straight Lines vs Circular Arcs. The time complexity here's O(E) but not O(1), as E instead of 1 straight lines have to be checked against. The combined time complexity will be O(E) in this case. Circular Sectors vs Circular Sectors Either circular sector's reference point will be adjusted to be that of the other. The time complexity here's O(1). The center of each circular sector will be checked against the other circular sector. Checking a point against a circular sector goes to Points vs Circular Sectors. The time complexity here's O(1). If either center collides with the other circular sector, then so do the circular sectors themselves. The combined time complexity will be O(1). If that's not the case, then it's certain that neither circular sector will lie within the other, meaning their perimeters must intersect in order to collide. So checking whether their linear equations or equation of circles collide will suffice. They go to Straight Lines vs Straight Lines, Straight Lines vs Circular Arcs and Circular Arcs vs Circular Arcs. The time complexity here's O(1). Circular Sectors vs Simple Polygons The circular sector's reference point will be adjusted to be that of the simple polygon. The time complexity here's O(1). The circular sector will be checked against the bounded rectangle or circular sector of the simple polygon. Checking a circular sector against a circular sector goes to Circular Sectors vs Circular Sectors. That against a rectangle will be checking the center of the circular sector against that rectangle and the arbitrary center of the simple polygon against that circular sector. Checking a point against a circular sector and simple polygon goes to Points vs Circular Sectors and Points vs Simple Polygons respectively. If the center of the circular sector collides with the rectangle or the arbitrary center of the simple polygon collides with the circular sector, then so do circular sector and the rectangle. The time complexity will be O(1) but not O(E), as the number of edges of a rectangle's always 4. If that's not the case, then it's certain that neither the circular sector nor the rectangle will completely lie within the other, meaning their perimeters must intersect in order to collide. So checking whether the linear equations or equation of circles of the circular sector will collide with the linear equations of the rectangle will suffice. It goes to Straight Lines vs Straight Lines and Straight Lines vs Circular Arcs. The time complexity here's O(1). If the circular sector doesn't collide with the bounded rectangle or circular sector, then neither does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the circular sector against the inner rectangle or circular sector of the simple polygon, which is essentially the same as checking against the bounding ones. If the circular sector collides with the inner rectangle or circular sector of the simple polygon, then so does the simple polygon. The combined time complexity will be O(1). If that's not the case, then check the center of the circular sector against the simple polygon, and the arbitrary center of the simple polygon against the circular sector. Checking a point against a circular sector and a simple polygon goes to Points vs Circular Sectors and Points vs Simple Polygons respectively. If the center of the circular sector collides with the simple polygon or the arbitrary center of the simple polygon collides with the circular sector, then so do the circular arc and simple polygon themselves. The combined time complexity will be O(E). If that's not the case, then it's certain that the neither the circular arc nor the simple polygon will completely lie within the other, meaning their perimeters must intersect in order to collide. So checking whether the linear equations or equation of circles of the circular sector will collide with the linear equations of the rectangle will suffice. It goes to Straight Lines vs Straight Lines and Straight Lines vs Circular Arcs. The time complexity here's O(E) but not O(1), as E instead of 1 straight lines have to be checked against. The combined time complexity will be O(E) in this case. Simple Polygon vs Simple Polygons The reference point of the one with fewer edges will be adjusted to be that of the other. The time complexity here's O(1). Their bounded rectangles or circular sectors will be checked against each other. Checking a circular sector against a circular sector and a circular sector against a simple polygon  goes to Circular Sectors vs Circular Sectors and Circular Sectors vs Simple Polygons respectively. Checking against 2 rectangles will be checking if the minimum and maximum x and y coordinates of one rectangle is less than or equal to and greater than or equal to the maximum and minimum x and y coordinates of the other respectively. The time complexity here's O(1). If their bounded rectangles or circular sector don't collide with each other, then neither do those simple polygons themselves. The combined time complexity will be O(1). If that's not the case, then check their inner rectangles or circular sectors against each other, which is essentially the same as checking the bounding ones against each other. If they collide, then so do those simple polygons. The combined time complexity will be O(1). If that's not the case, then check the arbitrary center of a simple polygon against the other simple polygon, which goes to Points vs Simple Polygons. If they collide, then so do the simple polygons. The combined time complexity will be O(E1 + E2), where E1 and E2 are the number of edges of those simple polygons respectively. If that's not the case, then it's certain that the neither simple polygon will completely lie within the other, meaning their perimeters must intersect in order to collide. So checking whether a triangle of a simple polygon touching its edges collide with that of the other simple polygon will suffice. As the number of triangles of a simple polygon touching its edges are E / 2 if E's even and (E + 1) / 2 if E's odd, both E1 and E2 are effectively reduced to E1_half and E2_half from now on. Check each triangle of a simple polygon touching its edges against the other's bounding rectangle or circular sector. Checking against the circular sector goes to Circular Sectors vs Simple Polygons. That against the rectangle will be checking the incenter of the triangle against the rectangle and the arbitrary center of the other simple polygon against the triangle, which goes to Points vs Simple Polygons. The time complexity will be O(1) but not O(E), as the number of edges of a rectangle's always 4. If the arbitrary center of the other simple polygon collide with the triangle of the simple polygon, then so do those simple polygons themselves. The combined time complexity will be O(E1_half + E2_half). If the incenter of a triangle of the polygon doesn't collide with the bounding rectangle or circular sector of the other simple polygon, then neither does the other simple polygon itself. The time complexity here will be O(E1_half + E2_half). Now both E1_half and E2_half will likely be further reduced significantly to E1_reduce and E2_reduce, making the last step, which costs O(E1_reduce * E2_reduce), much more efficient, meaning the added O(E1 + E2) and O(E1_half + E2_half) costs will probably be outweighed and the decreased O(E1_reduce * E2_reduce) cost. Finally check each triangle of the simple polygon touching its edges against those of the other, by checking each incenter against the other triangle, which goes to Circular Sectors vs Simple Polygons. If either collides with the other triangle, then so do those triangles, and thus the simple polygons themselves. The combined time complexity will be O(E1_reduce * E2_reduce). If that's not the case, then it's certain that neither triangle will completely lie within the other, meaning their perimeters must intersect in order to collide. So checking whether the edges of those triangles touching those of the simple polygons intersect will suffice. It goes to Straight Lines vs Straight Lines. The combined time complexity will be O(E1_reduce * E2_reduce) in this case. In practice, the average case, which is probably O(E1 + E2), are likely more realistic then the worst case. Shape Collision Detections On Maps Suppose there are n objects on a map. First use a aggregate bounding rectangle to bound those of all shapes. The time complexity here's O(n). Then partition the aggregate bounding rectangle into p parts, where p is the square number closest to n. Their difference should be small enough to treat p as n here, so the time complexity here's O(n). For each partition, check all shapes colliding with that partition to see if any of them collide with the others, by checking all their combinations. The time complexity here's O(n ^ 2) for the worst case, and O(1) for the best and average case, as most of the shapes usually won't concentrate in any single partition for a long time. It also means the average case's more meaningful here. The combined number of collision detections per frame's O(n) for the average and best case, and O(n ^ 2) for the worst case. The combined time complexity of all collision detections per frame's O(n) for the best case, O(n * E_avg), E_avg being the average number of edges of all simply polygons, for the average case, and O((n * E_max) ^ 2), E_max being the maximum number of edges of all simple polygons, for the worst case. Even myself feel and think that this algorithm's extremely dumb and incredibly ridiculous, but as I'm still really a computer science and maths nub, right now that's the best I can come up with. If you've any alternate algorithm, and/or comments on mine, just feel free to drop your 2 cents here.