19

I want to find the minimum distance between two polygons with million number of vertices(not the minimum distance between their vertices). I have to find the minimum of shortest distance between each vertex of first shape with all of the vertices of the other one. Something like the Hausdorff Distance, but I need the minimum instead of the maximum.

Pouya BCD
  • 991
  • 4
  • 11
  • 23
  • Could you update your question to mention that polygons may have millions of points, and whether they are convex/concave, and whether they can overlap. – brainjam Sep 13 '10 at 15:29
  • Yeah, the polygons have millions of points and they are non-convex. Actually an algorithm which works for two sets of points is preferred more. – Pouya BCD Sep 14 '10 at 11:52
  • 7
    the minimum distance between two polyogns is not always the minimum distance between the verticies in each polygon. which do you really want – jk. Sep 14 '10 at 15:05
  • You are right. Sometimes, the minimum distance is between a vertex and a segment. But it cannot be between two segments. By the way, the most naive algorithm to find this is checking each vertex with the other polygon and doing it for both polygons. – Pouya BCD Sep 21 '10 at 13:58
  • Please ensure coherence between the title and the question. – Yves Daoust May 23 '23 at 07:06

3 Answers3

25

Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) "Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets" by Toussaint and Bhattacharya:

It is shown in this paper that the minimum distance between two finite planar sets if [sic] n points can be computed in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced to O(n).

If the two polygons are crossing convex ones, perhaps you should also check out (PDF warning! Again, the order of the pages is reversed) "An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons" by Toussaint:

Let P = {p1, p2,..., pm} and Q = {q1, q2,..., qn} be two intersecting polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m + n) algorithm is presented for computing the minimum euclidean distance between a vertex pi in P and a vertex qj in Q.

Yaser Sulaiman
  • 3,311
  • 2
  • 28
  • 25
1

There is a simple algorithm that uses Minkowski Addition that allows calculating min-distance of two convex polygonal shapes and runs in O(n + m).
Links:
algoWiki, boost.org, neerc.ifmo.ru (in russian).

If Minkowski subtraction of two convex polygons covers (0, 0), then they intersect

urmat abdykerimov
  • 427
  • 1
  • 7
  • 17
  • Great, but how does this answer `What is the fastest algorithm to calculate the minimum distance between two sets of points?` Moreover `the polygons [are] non-convex`. – greybeard Jul 05 '21 at 06:02
  • It's unclear to me how Minkowski sum relates to distance between polygons. – oarfish Sep 24 '21 at 12:31
  • @oarfish Lets say, _A_ first set of points, _B_ second, _B'_ is _B_ inverted relatively to (0, 0); `dist(A, B) = min of |a - b|` (where a ∈ A, b ∈ B) `= min of |a + b| ` (where a ∈ A, b ∈ B') `= min of |c| (where c ∈ (A + B'));` A + B' can be found using Minkowski sum; – urmat abdykerimov Sep 25 '21 at 12:47
  • What does "inverted relatively to (0, 0)" mean? – oarfish Sep 28 '21 at 11:45
  • I realize though that this question is concerned with minimal distances between points, not points and edges, that was my confusion. – oarfish Sep 28 '21 at 11:47
  • In my comment inverted relatively (0,0) means that coordinates of given point are multiplied by -1. – urmat abdykerimov Sep 29 '21 at 13:35
  • Thanks @oarfish. Yes the problem is about points but I knowing this is so helpful and educative. – Pouya BCD Feb 27 '23 at 17:13
-1

I would pose this a bipartite graph matching problem. There is a nice library in python called networkx to solve this matching efficiently. Hope this helps!

Achyut Sarma
  • 119
  • 7