Sunday, July 6, 2014

Distance between two polygons in Java

I looked everywhere for a nice, clean, simple, easy to understand algorithm that would compute the minimum distance between two polygons. I had no luck, but I did gain an understanding of the problem. In a nutshell the minimal distance between two polygons P and Q is the minimum of

  1. the distances between each of the vertices of P and the vertices of Q,
  2. the distances between the vertices of P and the edges of Q,
  3. the distances between the vertices of Q and the edges of P.

It is quite possible for the two closest vertices to be further apart than the two closest edges. And no, contrary to my usual practice, this code is far from optimal. It is O(N2) not O(log n+log m), which is possible. But you figure it out. I just don't have the time, and none of the papers I read had any sample code.