<p>Thanks for the <a href="https://computergraphics.stackexchange.com/questions/2140/intersection-between-line-segments-narrowed-precondition">suggestions</a>. Now I am doing it as follows:</p>

<p>First off it is identified if two line segments intersect or not. And I am using the algorithm described in the book - "Introduction to Algorithms" chapter 33 (Computational Geometry). </p>



<pre class="lang-cpp prettyprint-override"><code>int orientation(glm::i16vec2 &amp;p1,
                glm::i16vec2 &amp;p2,
                glm::i16vec2 &amp;p3)
{
   return (((p3.x - p1.x) * (p2.y - p1.y)) - ((p2.x - p1.x) * (p3.y - p1.y)));
}


bool onSegment(const glm::i16vec2 &amp;pi,
                 const glm::i16vec2 &amp;pj,
                 const glm::i16vec2 &amp;pk)
{
    if((std::min(pi.x,pj.x) &lt;= pk.x &amp;&amp; pk.x &lt;= std::max(pi.x,pj.x))  &amp;&amp;
    (std::min(pi.y,pj.y) &lt;= pk.y &amp;&amp; pk.y &lt;= std::max(pi.y,pj.y)))
        return true;
    else
        return false;
}

bool intersects(const glm::i16vec2 &amp;p1,const glm::i16vec2 &amp;p2,
                const glm::i16vec2 &amp;p3,const glm::i16vec2 &amp;p4)
{

    int d1 = orientation(p1,p2,p3);
    int d2 = orientation(p1,p2,p4);
    int d3 = orientation(p3,p4,p1);
    int d4 = orientation(p3,p4,p2);

    if(((d1 &gt; 0 &amp;&amp; d2 &lt; 0) || (d1 &lt; 0 &amp;&amp; d2 &gt; 0)) &amp;&amp;
        ((d3 &gt; 0 &amp;&amp; d4 &lt; 0) || (d3 &lt; 0 &amp;&amp; d4 &gt; 0)))
          return true;
    else if(d1 == 0 &amp;&amp; onSegment(p3,p4,p1))
          return true;
    else if(d2 == 0 &amp;&amp; onSegment(p3,p4,p2))
          return true;
    else if(d3 == 0 &amp;&amp; onSegment(p1,p2,p3))
          return true;
    else if(d4 == 0 &amp;&amp; onSegment(p1,p2,p4))
          return true;
    else
          return false;    
}

int main()
{
    glm::i16vec2 hs(5,1);  // p1
    glm::i16vec2 he(5,3); // p2

    glm::i16vec2 cs(5,1);   // p3
    glm::i16vec2 ce(5,3); // p4

    if(intersects(hs,he,cs,ce))
      std::cout &lt;&lt; "It has intersection" &lt;&lt; std::endl;
    else
      std::cout &lt;&lt; "No intersection" &lt;&lt; std::endl;
}
</code></pre>

<p>Once the boolean flag mentions that the intersection point is found, then the exact intersection point is extracted as follows:</p>

<pre class="lang-cpp prettyprint-override"><code>short int getXIntersection(float x1,
                           float y1,
                           float x2,
                           float y2,
                           float yPos)
{
    float t = (x2 - x1) / (y2 - y1);

    float xDbl = (static_cast&lt;double&gt;(yPos) - y1) * t + x1;

    return static_cast&lt;short int&gt;(std::floor(0.5+xDbl));

}
</code></pre>

<p>The above function snippet is for the case when one of the line segments is parallel to the X-axis and the other segment is of arbitrary orientation.</p>

<p>The other case is when one of the line segments is parallel to Y-axis and the other segment is of arbitrary orientation. For the sake of brevity, the code snippet is not written here. I hope you can imagine how it will be? Yet it is included in the following snippet as for some coordinate values I am having wrong output:</p>

<pre class="lang-cpp prettyprint-override"><code>short int getYIntersection(float x1,
                           float y1,
                           float x2,
                           float y2,
                           float xPos)
{
    float t = (y2 - y1)/(x2 - x1);

    float yDbl = (static_cast&lt;double&gt;(xPos) - x1) * t + y1;

    return static_cast&lt;short int&gt;(std::floor(0.5+yDbl));

}
</code></pre>

<p>RECENT : Lets a line segment that is parallel to the Y-axis and it has the following coordinates as start and end point.</p>

<p>hs(3124,-3168)
he(3124,-3094)</p>

<p>The other arbitrarily oriented line segment has the following coordinates:</p>

<p>cs(3124,-3168)
ce(3125,-3116)</p>

<p>Since the line segment parallel to Y-axis has the constant X-value, should not the function getYIntersection() get the correct Y-value . But I am not getting it- instead I am getting -3213 as the Y-intersection value. Is there anything I am missing here ? The Y-value of the intersection must be within both the line segment, unfortunately it is not.</p>

<p>Can you imagine any loop hole in this overall algorithm? In practice, I am getting some huge intersection point value that is way out of the region.
The intersection point is saved as</p>

<pre class="lang-cpp prettyprint-override"><code>    short int
</code></pre>

<p>And I am getting the  X-intersection value -32768. This value is way out of the bounding area where all the intersection points must lie within.</p>

<p>Any thoughts?</p>

<p>After several comments and one answer , some adjustments is made within the code. It is found that with overlapping line segments the algorithm return true. It is not intended in my case, all overlapping line segments must not be flagged as intersection. Some hint would be nice. The issue of getting the intersection point is still in the pipeline. I believe that I missed the part that must be done after the initial true/false algorithm - that is to test if the calculated intersectin point lies within both the line segments or not. If it does, only then we eventually have the true intersection otherwise no intersection at all. </p>

<p>Some feed-back would be great! </p>

CC BY-SA 3.0
2016-04-27T10:53:42.743Z
is `y2 - y1` close to 0?
ratchet freak
CC BY-SA 3.0
2016-04-27T11:28:13.740Z
it is already checked that y2 != y1. One more issue may be to check how the algorithm behaves when both the line segments overlap. I checked that the algorithm does not filter it out. Should it be a intersection in this case ?
sajis997
CC BY-SA 3.0
2016-04-27T11:37:38.387Z
subtracting 2 nearly equal values and then dividing with it is generally bad for precision.
ratchet freak
CC BY-SA 3.0
2016-04-27T12:07:49.303Z
Initially it just returns if the two line segments does intersect or not and the algorithm is edited. If there any intersection I proceed with next part of the algorithm to find the point where it intersects and then I use getXIntersection(..) function. I am afraid that the issue of two overlapped line segments are not identified in the initial part of the algorithm . What do you think ? Do you suggest any changes in the initial part ?
sajis997
CC BY-SA 3.0
2016-04-27T12:22:56.343Z
I tried with several point values with the help of geogebra and I get valid result as you asked.
sajis997
CC BY-SA 3.0
2016-04-27T21:23:03.610Z
I've deleted my answer now that I understand that the initial step checks for segment intersection, not just line intersection. Sorry for the confusion. I've checked the pseudocode in the book and your code seems to match it. So your code for both steps looks correct to me. Since I can't see what is wrong, could you include the values you are testing with, showing the input values and returned result? The segment end points in the code appear to be identical (the same segment twice, rather than distinct segments): (5,1),(5,3) and (5,1),(5,3) again.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-27T21:34:02.133Z
The result shows that it has the intersection with those points you mentioned - in other words overlapping line segments intersects. In my case loverlapping line segments must not be decided as intersection and I , believe that I have to add some extra condition to it. Need some hint on those conditions. At last but not the least, once the initial test mentions that there is intersection between the line segments, Do I have test if the calculated intersection point reside on both the line segments ?
sajis997
CC BY-SA 3.0
2016-04-27T22:25:30.363Z
Could you share the input values that result in your X-intersection value of -32768?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-27T22:26:07.070Z
No, if the initial test confirms that the segments intersect, then the intersection point automatically lies on both segments.
trichoplax is on Codidact now
CC BY-SA 3.0
2016-04-27T22:48:44.470Z
Lets name the line segments. Surrogate Segment - (0,1762)---(1057,1762) and Axis Aligned Segment - (1066,1762)----(1038,1762). As you can see both the segments overlap each other. The current algorithm does not deal with these type of scenarios
sajis997
CC BY-SA 3.0
2016-04-28T08:50:19.533Z
Does your code work correctly for segments that do not overlap (that is, segments that do not share the same line)? If so, then the original question is solved and you can ask about detecting overlapping segments as a new question. If not, then overlapping segments is best left until the code is fixed - let's get it working before adding extra exceptions. Please don't change the aim of a question - feel free to ask a new question for a new problem.
trichoplax is on Codidact now
<mathematics>
Line segment intersection test and find the point of intersection
sajis997
# Line segment intersection test and find the point of intersection

(Asked by: username_0 on 2016-04-27)

Thanks for the [suggestions](https://computergraphics.stackexchange.com/questions/2140/intersection-between-line-segments-narrowed-precondition). Now I am doing it as follows:

First off it is identified if two line segments intersect or not. And I am using the algorithm described in the book - "Introduction to Algorithms" chapter 33 (Computational Geometry).

```cpp
int orientation(glm::i16vec2 &p1,
                glm::i16vec2 &p2,
                glm::i16vec2 &p3)
{
   return (((p3.x - p1.x) * (p2.y - p1.y)) - ((p2.x - p1.x) * (p3.y - p1.y)));
}

bool onSegment(const glm::i16vec2 &pi,
                 const glm::i16vec2 &pj,
                 const glm::i16vec2 &pk)
{
    if((std::min(pi.x,pj.x) <= pk.x && pk.x <= std::max(pi.x,pj.x))  &&
    (std::min(pi.y,pj.y) <= pk.y && pk.y <= std::max(pi.y,pj.y)))
        return true;
    else
        return false;
}

bool intersects(const glm::i16vec2 &p1,const glm::i16vec2 &p2,
                const glm::i16vec2 &p3,const glm::i16vec2 &p4)
{

    int d1 = orientation(p1,p2,p3);
    int d2 = orientation(p1,p2,p4);
    int d3 = orientation(p3,p4,p1);
    int d4 = orientation(p3,p4,p2);

    if(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
          return true;
    else if(d1 == 0 && onSegment(p3,p4,p1))
          return true;
    else if(d2 == 0 && onSegment(p3,p4,p2))
          return true;
    else if(d3 == 0 && onSegment(p1,p2,p3))
          return true;
    else if(d4 == 0 && onSegment(p1,p2,p4))
          return true;
    else
          return false;    
}

int main()
{
    glm::i16vec2 hs(5,1);  // p1
    glm::i16vec2 he(5,3); // p2

    glm::i16vec2 cs(5,1);   // p3
    glm::i16vec2 ce(5,3); // p4

    if(intersects(hs,he,cs,ce))
      std::cout << "It has intersection" << std::endl;
    else
      std::cout << "No intersection" << std::endl;
}

```

Once the boolean flag mentions that the intersection point is found, then the exact intersection point is extracted as follows:

```cpp
short int getXIntersection(float x1,
                           float y1,
                           float x2,
                           float y2,
                           float yPos)
{
    float t = (x2 - x1) / (y2 - y1);

    float xDbl = (static_cast<double>(yPos) - y1) * t + x1;

    return static_cast<short int>(std::floor(0.5+xDbl));

}

```

The above function snippet is for the case when one of the line segments is parallel to the X-axis and the other segment is of arbitrary orientation.

The other case is when one of the line segments is parallel to Y-axis and the other segment is of arbitrary orientation. For the sake of brevity, the code snippet is not written here. I hope you can imagine how it will be? Yet it is included in the following snippet as for some coordinate values I am having wrong output:

```cpp
short int getYIntersection(float x1,
                           float y1,
                           float x2,
                           float y2,
                           float xPos)
{
    float t = (y2 - y1)/(x2 - x1);

    float yDbl = (static_cast<double>(xPos) - x1) * t + y1;

    return static_cast<short int>(std::floor(0.5+yDbl));

}

```

RECENT : Lets a line segment that is parallel to the Y-axis and it has the following coordinates as start and end point.

hs(3124,-3168)
he(3124,-3094)

The other arbitrarily oriented line segment has the following coordinates:

cs(3124,-3168)
ce(3125,-3116)

Since the line segment parallel to Y-axis has the constant X-value, should not the function getYIntersection() get the correct Y-value . But I am not getting it- instead I am getting -3213 as the Y-intersection value. Is there anything I am missing here ? The Y-value of the intersection must be within both the line segment, unfortunately it is not.

Can you imagine any loop hole in this overall algorithm? In practice, I am getting some huge intersection point value that is way out of the region.
The intersection point is saved as

```cpp
    short int

```

And I am getting the X-intersection value -32768. This value is way out of the bounding area where all the intersection points must lie within.

Any thoughts?

After several comments and one answer , some adjustments is made within the code. It is found that with overlapping line segments the algorithm return true. It is not intended in my case, all overlapping line segments must not be flagged as intersection. Some hint would be nice. The issue of getting the intersection point is still in the pipeline. I believe that I missed the part that must be done after the initial true/false algorithm - that is to test if the calculated intersectin point lies within both the line segments or not. If it does, only then we eventually have the true intersection otherwise no intersection at all.

Some feed-back would be great!

**Tags:** mathematics

> **Comments:**
> **username_1**: is `y2 - y1` close to 0?  
> **username_0**: it is already checked that y2 != y1. One more issue may be to check how the algorithm behaves when both the line segments overlap. I checked that the algorithm does not filter it out. Should it be a intersection in this case ?  
> **username_1**: subtracting 2 nearly equal values and then dividing with it is generally bad for precision.  
> **username_0**: Initially it just returns if the two line segments does intersect or not and the algorithm is edited. If there any intersection I proceed with next part of the algorithm to find the point where it intersects and then I use getXIntersection(..) function. I am afraid that the issue of two overlapped line segments are not identified in the initial part of the algorithm . What do you think ? Do you suggest any changes in the initial part ?  
> **username_0**: I tried with several point values with the help of geogebra and I get valid result as you asked.  
> **username_2**: I've deleted my answer now that I understand that the initial step checks for segment intersection, not just line intersection. Sorry for the confusion. I've checked the pseudocode in the book and your code seems to match it. So your code for both steps looks correct to me. Since I can't see what is wrong, could you include the values you are testing with, showing the input values and returned result? The segment end points in the code appear to be identical (the same segment twice, rather than distinct segments): (5,1),(5,3) and (5,1),(5,3) again.  
> **username_0**: The result shows that it has the intersection with those points you mentioned - in other words overlapping line segments intersects. In my case loverlapping line segments must not be decided as intersection and I , believe that I have to add some extra condition to it. Need some hint on those conditions. At last but not the least, once the initial test mentions that there is intersection between the line segments, Do I have test if the calculated intersection point reside on both the line segments ?  
> **username_2**: Could you share the input values that result in your X-intersection value of -32768?  
> **username_2**: No, if the initial test confirms that the segments intersect, then the intersection point automatically lies on both segments.  
> **username_0**: Lets name the line segments. Surrogate Segment - (0,1762)---(1057,1762) and Axis Aligned Segment - (1066,1762)----(1038,1762). As you can see both the segments overlap each other. The current algorithm does not deal with these type of scenarios  
> **username_2**: Does your code work correctly for segments that do not overlap (that is, segments that do not share the same line)? If so, then the original question is solved and you can ask about detecting overlapping segments as a new question. If not, then overlapping segments is best left until the code is fixed - let's get it working before adding extra exceptions. Please don't change the aim of a question - feel free to ask a new question for a new problem.  

---

## 0 answers

