Collision Detection

Obstacles are really convenient to work with, because they provide an explicit description of the configuration space obstacles. Oftentimes, we don’t have this luxury and the obstacles are instead defined implicitly through a collision function. Here we can make use of the fact that triangles are convex polygons. In this circumstance, it means that we can test where the two triangles intersect by checking all of the sides on both triangles, and testing whether any of those sides act as separating lines, where all of the points from one triangle lie on one side of the line, and all of those from the other lie on the opposite side. If you can find such a separating edge, among the six edges among the two triangles, you have proved that the triangles don’t intersect.

Verifying if two triangles intersect

Collision detection is a key subroutine for most path planning algorithms, and it often boils down to computing the answer to some basic geometric questions. We can make use of the fact that triangles are convex polygons. In this circumstance, it means that we can test where the two triangles intersect by checking all of the sides on both triangles, and testing whether any of those sides act as separating lines, where all of the points from one triangle lie on one side of the line, and all of those from the other lie on the opposite side. If you can find such a separating edge, among the six edges among the two triangles, you have proved that the triangles don’t intersect.

Collision checking

"""
Array of circles. Count the number of collisions in a `count_collisions`
Each circle has three values (x,y, r)
 
Scenarios:
1. Circle2 is inside circle1
2. Circle1 is inside circle2
3. Circle2 has some overlap with circle1
4. No overlap
 
(x-h)^2 + (y-k)^2 < r^2
 
distance between origin of c1 and c2 < r1 + r2
 
rectangles = [(x,y,h, v),]
 
1. Rect1 is inside Rect2
2. Rect2 is inside Rect1
3. Rect1 has some overlap with Rect2
4. No overlap
 
Rectangle and circle
1. Rectangle is inside circle
2. Circle is inside rectangle
3. Some intersection of circle and rectangle
4. No intersection
 
 
 
"""
import math
 
def compute_euclidean_distance(x1, y1, x2, y2):
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
 
def check_point_within_rectangle(rectangle, point):
    x,y,h,v = rectangle
    return x < point[0] and point[0] < x + h and y < point[1] and point[1] < y + v
 
 
def generate_corners(rectangle):
    x,y,h,v = rectangle
    return [[x,y], [x+h, y], [x,y+v], [x+h, y+v]]
 
def check_rectangle_circle_collision(rectangle, circle):
    collision = False
 
    corners = generate_corners(rectangle)
    for 
 
 
def check_rectangle_collision(rectangle1, rectangle2):
    collision = False
 
    corners = generate_corners(rectangle2)
    # Check for rectangle 1
    for corner in corners:
        collision = collision or check_point_within_rectangle(rectangle1, corner)
 
    # Check for rectangle 2
    corners = generate_corners(rectangle1)
    for corner in corners:
        collision = collision or check_point_within_rectangle(rectangle2, corner)
 
    return collision
 
 
 
def check_circle_collision(circle1, circle2):
    distance_between_origins = compute_euclidean_distance(circle1[0], circle1[1], circle2[0], circle2[1])
    max_distance = circle1[2] + circle2[2]
    if distance_between_origins < max_distance:
        return True
    else:
        return False
 
def count_collisions(circles, rectangles):
# circles: List[[(x,y), r]]
    total_collisions = 0
 
    for first_circle_idx in range(len(circles)):
        for second_circle_idx in range(first_circle_idx +1, len(circles)):
            if (check_circle_collision(circles[first_circle_idx], circles[second_circle_idx])):
                total_collisions += 1
 
    for first_rect_idx in range(len(rectangles)):
        for second_rect_idx in range(first_rect_idx +1, len(rectangles)):
            if (check_rectangle_collision(rectangles[first_rect_idx], rectangles[second_rect_idx])):
                total_collisions += 1
 
    return total_collisions