# Line segment intersection test and find the point of intersection

Thanks for the suggestions. 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).

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:

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:

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

    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!

• is y2 - y1 close to 0? – ratchet freak Apr 27 '16 at 10:53
• 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 Apr 27 '16 at 11:28
• subtracting 2 nearly equal values and then dividing with it is generally bad for precision. – ratchet freak Apr 27 '16 at 11:37
• 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 Apr 27 '16 at 12:07
• I tried with several point values with the help of geogebra and I get valid result as you asked. – sajis997 Apr 27 '16 at 12:22