0

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):

Community
  • 1
  • 1
dazedviper
  • 992
  • 1
  • 9
  • 17
  • 1
    Possible duplicate of [How do you detect where two line segments intersect?](http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) – Andreas Fester Dec 22 '15 at 12:22
  • 1
    Seems like it is essentially the same method as [the formula in Wikipedia](https://en.m.wikipedia.org/wiki/Line%E2%80%93line_intersection#Intersection%20of%20two%20lines), though written slightly differently. – Lie Ryan Dec 22 '15 at 12:27

1 Answers1

1

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:

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • You don't explain the `fabs` in the supplied equation. I suspect it's something clever to do with avoiding division-by-zero errors. Your simple formula will blow up if (for example) Ax=Bx. – Martin Bonner supports Monica Dec 22 '15 at 13:42
  • This is correct as long as none of the lines are vertical. This doesn't explain the use of `fabs`. – dazedviper Dec 22 '15 at 14:13
  • @hallaplay835 That's a good call, note that the original equation doesn't handle them either. It will return a valid number for non-intersecting lines: http://ideone.com/t1hzRD – Jonathan Mee Dec 22 '15 at 14:30
  • The original code works **as long as the intersection exists**. One of the lines can be vertical, though. – dazedviper Dec 22 '15 at 14:37
  • @hallaplay835 Wait this is with a line segment as well, so how would we check if an intersection existed? – Jonathan Mee Dec 22 '15 at 14:46
  • 1
    Doing vector cross-product. If `ab x ap` has different sign as `ab x aq`, then one of the points `p`, `q` lies on one side of the line, and the other point on the other side. – dazedviper Dec 22 '15 at 14:51