|
|
Computer Graphics |
|
Minkowski sums ...
|
... and finally, the robot's path is found as a simple polyline connecting its centre of gravity to the target location via some of the vertices of the obstacle's extent. |
|
|
|
Computer Graphics |
|
Minkowski sums ...
|
... and finally, the robot's path is found as a simple polyline connecting its centre of gravity to the target location via some of the vertices of the obstacle's extent. |
|
But the the really fascinating feature of the Minkowski sum
algorithm is that we can use a merge technique to combine the
robot contour (a convex polygon consisting of N vertices) and the
obstacle contour (a convex polygon consisting of M vertices) into an
obstacle extent (a convex polygon consisting of N+M vertices) in
O(N+M) steps by scanning them according to the same clockwise
traversal scheme.
This is what computational geometry is all about: combining
knowledge of geometry and algorithms in order to build robust and
efficient procedures for computer graphics, robotics, operations
research, etc.
