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.