Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart).

And I am supposed to find the shortest distance between these two shapes.

First thing that came to my mind was to use bruteforce methods, ie find all the elements of shape A's perimeter (Let it be set X) and same for B's perimeter (Let it be Y ). Then find distance between all possible combinations ( excluding repetitions) of elements of X and Y and take the minimum value in it.

But I am sure it will take a lot of time.

Is there any other better way to do this ?

share|cite|improve this question
up vote 3 down vote accepted

You can find lots of literature via the key phrase collision detection. For example, the 2004 paper, "Efficient Collision Detection between 2D Polygons" (PDF download link), or another 2004 paper, "Kinetic collision detection for two simple polygons" (author link). I even ran across a recent patented(!) algorithm: "Collision detection of concave bodies using art gallery problem and cube maps," 2010 (patent link).

And here is some older literature: "Efficient distance computation between non-convex objects," 1994 (IEEE link). From any of these papers, you could search forward in time via Google Scholar.

share|cite|improve this answer
+1 - I didn't know its name is Collision detection. Thank you. I will have a look at the links. – Abid Rahman K Jul 14 '12 at 16:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.