4
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 - I didn't know its name is Collision detection. Thank you. I will have a look at the links. $\endgroup$ – Abid Rahman K Jul 14 '12 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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