0

I'm trying to implement the ClearPath pathfinding algorithm, that relys on velocity obstacles.
It is assumed, that both objects have a circular hull.
However, I do not understand how to calculate the minkowski sum of two objects.
Here's an excerpt from the paper

Apparently, the minkowski sum is simply the sum of two sets (here all possible velocities that yield a collision), but it is not explained how to calculate the set of those velocity vectors. It is only explained how to calculate a single velocity vector ( λ(p,v) ). Am I missing something ?

Also, what does this mean ?

let -A denote the object A reflected in its reference point

What is an objects reference point, and what does it mean to reflect said point ?

PAThePianoDude
  • 1
  • 1
    See https://en.wikipedia.org/wiki/Minkowski_addition for information about Minkowski sum. The Minkowski sum of two circular discs is another circular disc (see https://math.stackexchange.com/questions/444845/minkowski-sum-of-two-disks). If $-A$ means $A$ reflected in its reference point, then I think "reference point" just means the origin of the coordinate system you are using to represent $A$. – Rob Arthan Jul 29 '18 at 19:19
  • Hi, sorry for the late reply. But how does one compute the minkowski sum of 2 disks ? 2 convex polygons is easy, all you have to do, is to add up the vertices of both polygons. But how does that work with 2 disks ? I don't have vertices, all I have is the centrum as well as the radius. – PAThePianoDude Aug 27 '18 at 15:10
  • See the MSE link in my comment. – Rob Arthan Aug 27 '18 at 19:59
  • I have. If I understand it correctly, this is basically the set of a disk D(p,r)={p+u∣u∈D(0,r)} But how do I work with that set ? A polygon has a fixed amount of vertices, a disk, however, consists of an infinite amount of points. So, what do I actually add up when taking the minkowski sum of 2 disks ? – PAThePianoDude Aug 29 '18 at 13:54
  • You can represent the disc by the coordinates of the centre point $\mathbf{p}$ and the radius $r$. The formula in the MSE link shows you how you to combine two such representations to get the representation of the Minkowski sum. – Rob Arthan Aug 29 '18 at 20:13

0 Answers0