7
\$\begingroup\$

Given two line segments, determine if the line segments intersect and if so, where. In the case that the two given line segments are co-linear and overlap, determine the midpoint of the overlapping segment. Lines will be specified in pairs of (x, y) coordinates.

Examples

  • [(-1, -1), (1, 1)], [(-1, 1), (1, -1)] => (0, 0)
  • [(-1, -1), (1, -1)], [(-1, 1), (1, 1)] => No intersection
  • [(-2, 0), (1, 1.32)], [(-1, 0.44), (2, 1.76)] => (0, 0.88)
  • [(-2, -2), (0, 0)], [(1, -1), (1, 1)] => No intersection

Rules

  • Standard rules and loopholes apply
  • Input and output may be in any convenient format. Please state your convention along with your solution.
    • Examples for output conventions would be null for no intersection and a point for an intersection; a boolean and a tuple; string output in (x, y) format or "no intersection"; x and y will be NaN for no intersection. Other conventions are allowed, but these may give you a good starting point.
  • A minimum of 2 decimal places (or equivalent) precision is required.
  • Final results should be accurate to within 0.01 when at a scale of -100 - +100. (32-bit floats will be more than accurate enough for this purpose)
  • This is , so shortest code wins.

Related: This is not a duplicate of 2D Collision Detection because it only concerns line-line tests and requires an intersection point for intersecting line segments. This is also not a duplicate of Intersection of Two Lines because this concerns line segments specified with two endpoints rather than functions.

\$\endgroup\$
  • \$\begingroup\$ Its only me or 3rd test case does not have intersection? Maybe I'm wrong \$\endgroup\$ – Luis felipe De jesus Munoz Jul 16 '18 at 18:09
  • \$\begingroup\$ @LuisfelipeDejesusMunoz they coincide when x is between -1 and 1. \$\endgroup\$ – ngm Jul 16 '18 at 18:43
2
\$\begingroup\$

R, 95 bytes

function(m,a=c(1,3),r=range){plot(0,,"n",r(m[a,]),r(m[-a,]));segments(m[1,],m[2,],m[3,],m[4,])}

Try it online!

Here's a graphical solution as an appetizer while I'm working on a full-blown solution. TIO link will not plot anything.

enter image description here

\$\endgroup\$
1
\$\begingroup\$

C (gcc -lm), 225 bytes

#define T 20000
#define N double
N sqrt(N);N D(a,b){N x=a%T-b%T,y=a/T-b/T;return sqrt(x*x+y*y);}F,L,P;f(a,b,c,d){F=L=-1;for(P=0;++P<T*T;L=(D(a,P)+D(P,b)-D(a,b)<0.001&&D(c,P)+D(P,d)-D(c,d)<0.001)?(F=(F<0?P:F)),P:L);a=(F+L)/2;}

Try it online!

Very slow. Input format is endpoints packed into ints as coordinate multiplied by 100 (to an integer) and 10000 added to it (to a natural). Y coordinate is multiplied by an additional 20000 to pack it next to X coordinate. No collision is signaled by the point (-100.01,-100).

Thus the X coordinate of a point A is ((A%20000)-10000)/100.0 and the Y coordinate is ((A/20000)-10000)/100.0.

Rationale

Thanks to the question providing no time limit and specifying a desired precision accurately, a non-optimal solution can be used to reduce code size. Thus instead of actually computing the collision points, then doing some additional logic if the lines are coincident, this checks every single point of the given precision and sees if it is a collision.

This collision check is much shorter (code-wise) than the collision computation. In particular to check if a point collides with a line segment just check if the distance to each endpoint adds up to the length of the segment. If a point collides with both line segments individually, then it is a point where the line segments intersect.

Using this strategy the code finds the endpoints of the collision and returns their midpoint. Initially they are set to -1, so if there is no collision it returns -1 (-1+-1/2) which when translated back is a number just out of range. If there's only one collision point, it is stored in both endpoints, so it is itself returned (x+x/2). Finally, if there is an overlap the overlap must be a line, returning the average of the line's endpoints will yield the midpoint.

Algorithm

As such, the algorithm in pseudo-code would be:

collision (AB,CD):
    start and end = -1
    for each point P:
        if P is in both line segments AB and CD
            if start = -1, start = P
            end = P
    return (start+end)/2

is P in line segment AB:
    return distance(A,P) + distance(P,B) = distance(A,B)

Description

The annotated source is thus:

#define T 20000             // We use 20000 a lot
#define N double            // We use double a lot
N sqrt(N);                  // We need to prototype sqrt or it will be assumed to be int(int)
N D(a,b){                   // D defines the distance function
    N x=a%T-b%T,            // x is delta x
      y=a/T-b/T;            // y is delta y
    return sqrt(x*x+y*y);}  // standard distance formula: sqrt(dx^2+dy^2)
F,                          // F is the first point of collision
L,                          // L is the last point of collision
P;                          // P is the current test point
f(a,b,c,d){                 // f takes the 4 segment end-points
    F=L=-1;                 // Initialize both collision points to -1 (invalid)
    for(P=0;++P<T*T;        // Loop P over each point
    L=                      // Set the last collision point based on a ternary
    (D(a,P)+D(P,b)-D(a,b)   // We have to use an epsilon check due to floating point rounding errors
     <0.001                 // This accuracy is definitionally good enough
     &&                     // The previous check was for collision with AB
     D(c,P)+D(P,d)-D(c,d)   // now we have to check for collision with CD
     <0.001)?               // if both collide - we have a collision point!
      (F=(F<0?P:F)),        // if the first collision point isn't set, this is it
      P                     // set the last collision point no matter what
      :                     // they don't both collide, ignore this point
      L);                   // the expression is assigned to L, so keep L the same
    a=                      // return by assigning to the first argument
      (F+L)/2;}             // the average of the first and last points
                            // Luckily the packing of the points fits with enough space so we 
                            // don't have to worry about averaging each coordinate separately
\$\endgroup\$
  • \$\begingroup\$ F=(F<0?P:F) => F=F<0?P:F for -2 bytes \$\endgroup\$ – Zacharý Nov 16 '18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.