Distance between two polylines

Question

I want to calculate the distance d between two polylines:

Obviously I could check the distance for all pairs of line-segments and choose the smallest distance, but this ways the algorithmn would have a runtime of O(n²). Is there any better approach?

Answer 1

Divide and conquer:

• Define a data structure representing a pair of polylines and the minimun distance between their axis-aligned minimum bounding boxes (AAMBB):pair = (poly_a, poly_b, d_ab))

• Create an empty queue for pair data estructures, using the distance d_ab as the key.

• Create a pair data estructure with the initial polylines and push it into the queue.

• We will keep a variable with the minimum distance between the polylines found so far (min_d). Set it to infinite.

• Repeat:

  • Pop from the queue the element with minimum distance d_ab.

  • If d_ab is greater than min_d we are done.

  • If any of the polylines poly_a or poly_b contains an only segment:

    • Use brute force to find the minimal distance between then and update min_d accordingly.

  • Otherwise:

    • Divide both polylines poly_a and poly_b in half, for instance:

      (1-7) --> { (1-4), (4-7) }

      (8-12) --> { (8-10), (10-12) }

    • Make the cross product of both sets, create 4 new pair data structures and push then into the queue Q.

On the average case, complexity is O(N * log N), worst case may be O(N²).

Update: The algorithm implemented in Perl.

Answer 2

The "standard" way for such problems is to construct the Voronoi diagram of the geometric entities. This can be done in time O(N Log N).

But the construction of such diagrams for line segments is difficult and you should resort to ready made solutions such as in CGAL.