-1

I'm using this code that was posted as an answer to this question: How do you detect where two line segments intersect?

It is my understanding that this function only returns an intersection point if the two line segments exactly intersect. I need to modify this function to include a tolerance so it returns an intersection point if the line segments nearly intersect (i.e. within a 0.01 range). I don't really understand the maths that underpins this function so I was hoping that someone could help.

Thanks

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

EDIT: for clarification, the image below depicts the sort of scenario whereby two line segments would nearly intersect.

Nearly intersecting lines - image

titanicsaled
  • 21
  • 4
  • Please specify, what you mean by nearly intersect. On a 2d plane, I have no clue how this should look like. – schorsch312 Sep 26 '17 at 13:16
  • Perhaps this is of interrest: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect – Support Ukraine Sep 26 '17 at 13:20
  • The references in the linked Q&A should have the answer/s you need. – Martin James Sep 26 '17 at 13:20
  • @4386427 the lines are of a defined length, so one line could stop just short of intersecting the other. – Martin James Sep 26 '17 at 13:21
  • Quote form @Some programmer dude Welcome to stackoverflow.com. Please take some time to read the help pages, especially the sections named "What topics can I ask about here?" and "What types of questions should I avoid asking?". Also please take the tour and read about how to ask good questions. Lastly please learn how to create a Minimal, Complete, and Verifiable Example. – schorsch312 Sep 26 '17 at 13:22
  • I have added an image that depicts a line that nearly intersects with another line for clarification. – titanicsaled Sep 26 '17 at 13:34
  • The code you posted looks like it potentially performs division by zero. – davmac Sep 26 '17 at 14:13
  • So the function are called with the endpoints of the two line segments - it that it? – Support Ukraine Sep 26 '17 at 15:32

2 Answers2

1

I am not a graphics expert, but this is what I would do:

For each endpoint: See if a circle centered on the endpoint with a radius of threshold intersects the other line segment. Then the lines nearly intersect.

bolov
  • 72,283
  • 15
  • 145
  • 224
  • 1
    This is a very good idea. If two straight segments do not intersect, then the minimum distance between them is reached in one of the 4 endpoints. It is still necessary to check the possibility of the segments intersecting though. Also, I don't see a trivial way to check if a segment intersects a circle – Nevado Sep 26 '17 at 14:26
  • @Nevado determine the intersection point(s) between the circle and the line. Then see if those points (if any) are on the line segment. – bolov Sep 26 '17 at 14:32
  • I think that given a line (with two points) and a circle (with point and and radius), finding if they intersect is not a trivial task. It is certainly possible, but it is worth commenting a solution, as its difficulty is almost the same as the original problem. – Nevado Sep 26 '17 at 14:52
  • 1
    @Nevado https://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm – bolov Sep 26 '17 at 14:55
0

It's still not clear precisely what you want to count as a "near intersection". In your example image you could find an intersection by extending each line (in both directions) by the chosen tolerance amount, and then checking for an (exact) intersection between the extended lines.

If you want to detect intersections of lines at more acute angles, you could expand each line into a rectangular area (with a width determined by the tolerance) and then check for overlap between the rectangular regions.

In both cases the tolerance amount would mean something slightly different. You didn't define it in your question. What precisely does the tolerance value mean? Is it the amount by which one of the lines needs to be extended to form an intersection with the other? Is it a maximum distance between any point on each line that can be considered an intersection? etc.

davmac
  • 20,150
  • 1
  • 40
  • 68