CODEWITHSUNDEEP
c++geometrylinecomputational-geometryintersection
dazedviper
dazedviper

Reputation: 1022

Intersection of a line with a line segment in C++

The following is C++ code taken from CP3, which calculates the point of intersection between the line that passes through a and b, and the line segment defined by p and q, assuming the intersection exists. Can someone explain what it is doing and why it works (geometrically)?

// line segment p-q intersect with line A-B.
point lineIntersectSeg(point p, point q, point A, point B) {
  double a = B.y - A.y;
  double b = A.x - B.x;
  double c = B.x * A.y - A.x * B.y;
  double u = fabs(a * p.x + b * p.y + c);
  double v = fabs(a * q.x + b * q.y + c);
  return point((p.x * v + q.x * u) / (u+v), (p.y * v + q.y * u) / (u+v));
}

Note that this solution seems to be different to that explained here or in the Wikipedia page since this solution makes use of the absolute value function.

I've expanded the expressions that result for the point of intersection (x, y):

Upvotes: 0

Views: 3952

Answers (1)

Jonathan Mee
Jonathan Mee

Reputation: 38909

A good starting point would be to understand what to do to find line intersection yourself: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

  • Line Segment: y = ax + c
  • Line: y = bx + d
  • Intersection and

Now we'll just need to get a and c in terms of p and q and b and d in terms of A and B.

We know both of our slopes:

  • a = (p.y - q.y) / (p.x - q.x)
  • b = (A.y - B.y) / (A.x - B.x)

I tend to use the Point-Slope Form to find the y-intercept:

  • y -p.y= a(x -p.x) which will simplify to y = ax - (p.x * q.y - p.y * q.x) / (p.x - q.x)
  • y -A.y= a(x -B.x) which will simplify to y = ax - (A.x * B.y - A.y * B.x) / (A.x - B.x)

So if you'll permit me to mix our variables into math notation so simplification is simpler, our final equation for our intersection components is:

Once the fractions in the numerators and denominators have been combined into a single fraction, the denominator for both is seen to be (A.x - B.x)(p.x - q.x) So both denominators can be removed yielding:

Upvotes: 1

Related Questions