Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Distance between line segments: near parallel case TOO

  1. Oct 28, 2014 #1
    Does anyone know a good algorithm for calculating the closest points/distance between two line segments? I use some pretty general code:


    which works in most cases but fails horribly when line segments are nearly parallel. I've been messing with the SMALL_NUM value for division overflow to no avail. The calculated distance can still vary widely when nearly parallel.
  2. jcsd
  3. Oct 29, 2014 #2
    I managed to isolate a specific incident where this happens in my code. The distance between segments P1P2 and Q1Q2 changed abruptly in one timestep from 1.05 mm to 0.90 mm (yarn radius = 1 mm), causing abrupt compression spikes. In reality the distance in the original timestep is definitely also around 0.90 mm but is not calculated as such. I find that the values of s and t (s=0 for P1, 1 for P2, t=0 for Q1, 1 for Q2) for the closest points are originally 0 and 0 (as well as in the previous time steps) and then change abruptly to 0 and around 0.29 in the new time step. What it should be, I still need to check out.

    P1 = (0.012711 ,-0.000688 ,-0.001097);
    P2 = (0.012895 ,-0.000686 ,-0.001133);
    Q1 = (0.012676 ,-0.000689 ,-0.000999);
    Q2 = (0.012859 ,-0.000687 ,-0.001034);

    P1new = (0.012712, -0.000689, -0.001095);
    P2new = (0.012895, -0.000687, -0.001131);
    Q1new = (0.012676, -0.000690, -0.000996);
    Q2new = (0.012859, -0.000688, -0.001032);

    Results when calculating self contact of 15000 line segments in a few tens of fibers, one big mess:

    http://users.ugent.be/~skdmeule/Fibers.jpg [Broken]

    Does anyone have a decent algorithm that also gives good results for nearly parallel lines?
    Last edited by a moderator: May 7, 2017
  4. Oct 30, 2014 #3
    I have decided to contact Dr. David H. Eberly, which is referenced as the source upon which the author in the first link I provided based himself upon. Dr. Eberly was kind enough to write an extensive reply. If I may quote part of it:

    I already asked for that sample source code and am yet to hear back from him. Meanwhile, I have downloaded the Geometric Tools engine source code from:


    And looked at the code for segment to segment distance calculation, adjusted it to fit into my code and now it works fine using double's everywhere. I am still going to look into how to implement this "arbitrary precision arithmetic", I want to ask whether and where this arithmetic is necessary and still have some questions about some issues. I have however currently a temporary solution that seems to be working a lot better already.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Distance between line segments: near parallel case TOO
  1. Line segment (Replies: 3)