Kết nối hai đoạn đường

Question

Cho hai đoạn đường 2D, A và B, làm cách nào để tính toán độ dài của đoạn đường ngắn nhất 2D, C, kết nối A và B?

Answer 1

Hãy xem xét hai dòng của bạn phân khúc hạng A và B để được đại diện bởi hai điểm mỗi (trong Fortran!):

đường A thể hiện bằng A1 (x, y), A2 (x, y)

Dòng B được biểu thị bằng B1 (x, y) B2 (x, y)

Trước tiên hãy kiểm tra xem hai dòng có giao nhau bằng thuật toán này hay không.

Nếu chúng cắt nhau, thì khoảng cách giữa hai dòng là 0 và đoạn đường nối với nhau là điểm giao nhau.

Nếu họ không giao nhau, Sử dụng phương pháp này: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/ để tính toán khoảng cách ngắn nhất giữa:

1. điểm A1 và dòng B
2. Point A2 và dòng B
3. điểm B1 và ​​dòng A
4. Điểm B2 và dòng A

Ngắn nhất trong bốn phân đoạn này là câu trả lời của bạn.

Answer 2

This page có thông tin bạn có thể đang tìm kiếm.

Answer 3

Gernot Hoffmann giấy (thuật toán và mã Pascal):

http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf

Answer 4

Mẹo: nếu bạn muốn so sánh khoảng cách dựa trên điểm, nó không phải là cần thiết để làm rễ vuông.

Ví dụ: để xem nếu P-to-Q là một khoảng cách nhỏ hơn Q-to-R, chỉ cần kiểm tra (giả):

square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y) 

Answer 5

This page có một mô tả ngắn đẹp cho việc tìm kiếm những khoảng cách ngắn nhất giữa hai dòng, mặc dù @ strager của liên kết bao gồm một số mã

Answer 6

Thế giới bên kia đã nói, "Trước tiên hãy kiểm tra xem hai dòng có giao nhau bằng thuật toán này không", nhưng anh không cho biết thuật toán của anh ta là gì. Rõ ràng, đó là giao lộ của các đoạn phân đoạn không phải là các dòng mở rộng quan trọng; bất kỳ phân đoạn đường không song song nào (ngoại trừ các điểm cuối trùng hợp không xác định đường thẳng) sẽ giao nhau, nhưng khoảng cách giữa các đoạn đường sẽ không nhất thiết là bằng không. Vì vậy, tôi cho rằng anh ta có nghĩa là "phân đoạn dòng" thay vì "dòng" ở đó.

Liên kết Afterlife đưa ra là một cách tiếp cận rất thanh lịch để tìm điểm gần nhất trên một đường thẳng (hoặc đoạn thẳng hoặc đường ray) đến một điểm tùy ý khác. Điều này làm việc để tìm khoảng cách từ mỗi điểm cuối đến đoạn đường khác (ràng buộc tham số được tính u không nhỏ hơn 0 cho một đoạn thẳng hoặc đường và không quá 1 cho một đoạn đường), nhưng nó không xử lý khả năng mà một điểm bên trong trên một đoạn thẳng gần hơn điểm cuối bởi vì chúng thực sự giao nhau, do đó cần kiểm tra thêm về giao lộ.Đối với thuật toán xác định giao điểm phân đoạn đường, một cách tiếp cận sẽ là tìm giao điểm của các đường mở rộng (nếu song song sau đó bạn đã hoàn thành), và sau đó xác định xem điểm đó có nằm trong cả hai đoạn đường hay không, như vậy bằng cách lấy dấu chấm của các vectơ từ điểm giao nhau, T, đến hai điểm cuối:

((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) ​​* (Ty - A2y))

Nếu điều này là âm (hoặc "không") thì T là giữa A1 và A2 (hoặc tại một điểm cuối). Kiểm tra tương tự cho đoạn đường khác. Nếu giá trị lớn hơn "0" thì các đoạn đường không giao nhau. Tất nhiên, điều này phụ thuộc vào việc tìm kiếm giao điểm của các đường mở rộng đầu tiên, mà có thể yêu cầu biểu diễn mỗi dòng như một phương trình và giải quyết hệ thống bằng cách giảm Gaussian (vv).

Nhưng có thể có cách trực tiếp hơn mà không cần phải giải quyết cho điểm giao nhau, bằng cách lấy sản phẩm chéo của vec-tơ (B1-A1) và (B2-A1) và sản phẩm chéo của vectơ (B1) -A2) và (B2-A2). Nếu các sản phẩm chéo này có cùng hướng, thì A1 và A2 nằm trên cùng một bên của đường B; nếu chúng theo hướng ngược lại, thì chúng nằm trên các cạnh đối diện của đường B (và nếu 0, thì một hoặc cả hai là trên đường dây B). Tương tự, kiểm tra các sản phẩm chéo của các vectơ (A1-B1) và (A2-B1) và (A1-B2) và (A2-B2). Nếu bất kỳ sản phẩm nào trong số này là "không" hoặc nếu các điểm cuối của cả hai đoạn đều nằm trên các cạnh đối diện của đường khác, thì các đoạn đường phải tự cắt nhau, nếu không chúng không giao nhau.

Tất nhiên, bạn cần một công thức tiện dụng để tính toán sản phẩm chéo của hai vectơ từ tọa độ của chúng. Hoặc nếu bạn có thể xác định các góc (là dương hoặc âm), bạn sẽ không cần sản phẩm chéo thực sự, vì nó là hướng của các góc giữa các vectơ mà chúng ta thực sự quan tâm (hoặc sin của góc, thực sự) . Nhưng tôi nghĩ rằng công thức cho chéo sản phẩm (trong 2-D) chỉ đơn giản là:

Cross (V1, V2) = (V1x * V2y) - (V2x * V1y)

Đây là trục z thành phần của vector sản phẩm chéo 3-D (trong đó các thành phần x và y phải bằng không, vì các vectơ ban đầu nằm trong mặt phẳng z = 0), vì vậy bạn chỉ cần nhìn vào dấu (hoặc "số không").

Vì vậy, bạn có thể sử dụng một trong hai phương pháp này để kiểm tra giao lộ phân đoạn dòng trong thuật toán Afterlife mô tả (tham chiếu liên kết).

Answer 7

Sử dụng ý tưởng chung của các thuật toán Afterlife's và Rob Parker's ở trên, đây là phiên bản C++ của tập hợp các phương pháp để có khoảng cách tối thiểu giữa 2 phân đoạn 2D tùy ý. Điều này sẽ xử lý các phân đoạn chồng chéo, phân đoạn song song, phân đoạn giao nhau và không giao nhau. Ngoài ra, nó sử dụng các giá trị epsilon khác nhau để bảo vệ chống lại sự không chính xác của dấu phẩy động. Cuối cùng, ngoài việc trả về khoảng cách tối thiểu, thuật toán này sẽ cho bạn điểm trên đoạn 1 gần nhất với đoạn 2 (cũng là điểm giao nhau nếu các đoạn giao nhau). Nó sẽ là khá tầm thường để cũng trở lại điểm trên [p3, p4] gần nhất [p1, p2] nếu muốn, nhưng tôi sẽ để nó như một bài tập cho người đọc :)

// minimum distance (squared) between vertices, i.e. minimum segment length (squared) 
#define EPSILON_MIN_VERTEX_DISTANCE_SQUARED 0.00000001 

// An arbitrary tiny epsilon. If you use float instead of double, you'll probably want to change this to something like 1E-7f 
#define EPSILON_TINY 1.0E-14 

// Arbitrary general epsilon. Useful for places where you need more "slop" than EPSILON_TINY (which is most places). 
// If you use float instead of double, you'll likely want to change this to something like 1.192092896E-04 
#define EPSILON_GENERAL 1.192092896E-07 

bool AreValuesEqual(double val1, double val2, double tolerance) 
{ 
    if (val1 >= (val2 - tolerance) && val1 <= (val2 + tolerance)) 
    { 
     return true; 
    } 

    return false; 
} 


double PointToPointDistanceSquared(double p1x, double p1y, double p2x, double p2y) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    return (dx * dx) + (dy * dy); 
} 


double PointSegmentDistanceSquared(double px, double py, 
            double p1x, double p1y, 
            double p2x, double p2y, 
            double& t, 
            double& qx, double& qy) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    double dp1x = px - p1x; 
    double dp1y = py - p1y; 
    const double segLenSquared = (dx * dx) + (dy * dy); 
    if (AreValuesEqual(segLenSquared, 0.0, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)) 
    { 
     // segment is a point. 
     qx = p1x; 
     qy = p1y; 
     t = 0.0; 
     return ((dp1x * dp1x) + (dp1y * dp1y)); 
    } 
    else 
    { 
     t = ((dp1x * dx) + (dp1y * dy))/segLenSquared; 
     if (t <= EPSILON_TINY) 
     { 
      // intersects at or to the "left" of first segment vertex (p1x, p1y). If t is approximately 0.0, then 
      // intersection is at p1. If t is less than that, then there is no intersection (i.e. p is not within 
      // the 'bounds' of the segment) 
      if (t >= -EPSILON_TINY) 
      { 
       // intersects at 1st segment vertex 
       t = 0.0; 
      } 
      // set our 'intersection' point to p1. 
      qx = p1x; 
      qy = p1y; 
      // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if 
      // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). 
     } 
     else if (t >= (1.0 - EPSILON_TINY)) 
     { 
      // intersects at or to the "right" of second segment vertex (p2x, p2y). If t is approximately 1.0, then 
      // intersection is at p2. If t is greater than that, then there is no intersection (i.e. p is not within 
      // the 'bounds' of the segment) 
      if (t <= (1.0 + EPSILON_TINY)) 
      { 
       // intersects at 2nd segment vertex 
       t = 1.0; 
      } 
      qx = p2x; 
      qy = p2y; 
      // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if 
      // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). 
     } 
     else 
     { 
      // The projection of the point to the point on the segment that is perpendicular succeeded and the point 
      // is 'within' the bounds of the segment. Set the intersection point as that projected point. 
      qx = ((1.0 - t) * p1x) + (t * p2x); 
      qy = ((1.0 - t) * p1y) + (t * p2y); 
      // for debugging 
      //ASSERT(AreValuesEqual(qx, p1x + (t * dx), EPSILON_TINY)); 
      //ASSERT(AreValuesEqual(qy, p1y + (t * dy), EPSILON_TINY)); 
     } 
     // return the squared distance from p to the intersection point. 
     double dpqx = px - qx; 
     double dpqy = py - qy; 
     return ((dpqx * dpqx) + (dpqy * dpqy)); 
    } 
} 


double SegmentSegmentDistanceSquared( double p1x, double p1y, 
             double p2x, double p2y, 
             double p3x, double p3y, 
             double p4x, double p4y, 
             double& qx, double& qy) 
{ 
    // check to make sure both segments are long enough (i.e. verts are farther apart than minimum allowed vert distance). 
    // If 1 or both segments are shorter than this min length, treat them as a single point. 
    double segLen12Squared = PointToPointDistanceSquared(p1x, p1y, p2x, p2y); 
    double segLen34Squared = PointToPointDistanceSquared(p3x, p3y, p4x, p4y); 
    double t = 0.0; 
    double minDist2 = 1E+38; 
    if (segLen12Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     qx = p1x; 
     qy = p1y; 
     if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
     { 
      // point to point 
      minDist2 = PointToPointDistanceSquared(p1x, p1y, p3x, p3y); 
     } 
     else 
     { 
      // point - seg 
      minDist2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y); 
     } 
     return minDist2; 
    } 
    else if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     // seg - point 
     minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
     return minDist2; 
    } 

    // if you have a point class and/or methods to do cross products, you can use those here. 
    // This is what we're actually doing: 
    // Point2D delta43(p4x - p3x, p4y - p3y); // dir of p3 -> p4 
    // Point2D delta12(p1x - p2x, p1y - p2y); // dir of p2 -> p1 
    // double d = delta12.Cross2D(delta43); 
    double d = ((p4y - p3y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p3x)); 
    bool bParallel = AreValuesEqual(d, 0.0, EPSILON_GENERAL); 

    if (!bParallel) 
    { 
     // segments are not parallel. Check for intersection. 
     // Point2D delta42(p4x - p2x, p4y - p2y); // dir of p2 -> p4 
     // t = 1.0 - (delta42.Cross2D(delta43)/d); 
     t = 1.0 - ((((p4y - p3y) * (p4x - p2x)) - ((p4y - p2y) * (p4x - p3x)))/d); 
     double seg12TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen12Squared); 
     if (t >= -seg12TEps && t <= (1.0 + seg12TEps)) 
     { 
      // inside [p1,p2]. Segments may intersect. 
      // double s = 1.0 - (delta12.Cross2D(delta42)/d); 
      double s = 1.0 - ((((p4y - p2y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p2x)))/d); 
      double seg34TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen34Squared); 
      if (s >= -seg34TEps && s <= (1.0 + seg34TEps)) 
      { 
       // segments intersect! 
       minDist2 = 0.0; 
       qx = ((1.0 - t) * p1x) + (t * p2x); 
       qy = ((1.0 - t) * p1y) + (t * p2y); 
       // for debugging 
       //double qsx = ((1.0 - s) * p3x) + (s * p4x); 
       //double qsy = ((1.0 - s) * p3y) + (s * p4y); 
       //ASSERT(AreValuesEqual(qx, qsx, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       //ASSERT(AreValuesEqual(qy, qsy, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       return minDist2; 
      } 
     } 
    } 

    // Segments do not intersect. Find closest point and return dist. No other way at this 
    // point except to just brute-force check each segment end-point vs opposite segment. The 
    // minimum distance of those 4 tests is the closest point. 
    double tmpQx, tmpQy, tmpD2; 
    minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
    tmpD2 = PointSegmentDistanceSquared(p4x, p4y, p1x, p1y, p2x, p2y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = tmpQx; 
     qy = tmpQy; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p1x; 
     qy = p1y; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p2x, p2y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p2x; 
     qy = p2y; 
     minDist2 = tmpD2; 
    } 

    return minDist2; 
}