Prequisite: Minkowski sum.
When I was solving the problem yesterday, I came up with a simple solution. I hadn't seen it published by anyone else, so I decided to write a blog myself.
Given two convex polygon $$$A$$$ and $$$B$$$, their minimum distance is equal to the minimum distance from the origin point $$$(0, 0)$$$ to their Minkowski sum $$$C = A + (-B)$$$. $$$-B$$$ means to negate all the vectors in $$$B$$$.
Heuristic proof: We want to know the minimum of distances of every pair vector $$$(a, b) s.t. a \in A, b \in B$$$. That equals to $$$\min(|a - b|) \forall a, b$$$. And that's the distance from the origin point to the Minkowski sum of $$$A$$$ and $$$-B$$$.
Note: This should also work for non-convex polygons, but I don't know how to do Minkowski sum (with good time complexity) for them.
The basic idea is similar to GJK algorithm (which is often used to detect object collision), but it is way easier to implement and can return the distance rather than a bool.
There will be no implementation here, because:
- Left as an exercise for reader.
- It's very easy, and template for Minkowski sum can be easily found.
- I'm lazy.
Some random murmur
While searching about GJK algorithm, I found that many people refer to $$$A + (-B)$$$ as "Minkowski difference." This isn't correct (at least to my knowledge), because there isn't really a point to make a new name if it's just adding the nagative thing. Instead, Minkowski difference of $$$A$$$ and $$$B$$$ should be $$$C$$$ such that $$$C + B = A$$$ (the $$$+$$$ denotes Minkowski sum), in other words, the inverse operation of Minkowski sum. I don't know why so many people say that the GJK algorithm uses minkowski difference while the original paper doesn't seems to mention any Minkowski thing.
I can't find a practice problem for this (perhaps TIOJ 1041, but it's only in traditional chinese and has bad testdata.) If you happen to know one, please leave it in the comments.
Last but not least, I want upvotes. If you learned something, please give me one. Don't hesitate, just poke that button!
