1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook