0

I want to find a way to check whether two line segments intersects or not.I am using Xlib programming to implement this.

I checked on internet but i only found the ways to find the intersection point of two lines but not of two line segments.

How can i implement this using X lib programming?

Force.comBat
  • 235
  • 2
  • 3
  • 11

1 Answers1

1

You don't need Xlib for this. Let the two segments be

  • A1 = (x1, y1) -> B1 = (x1 + dx1, y1 + dy1) and
  • A2 = (x2, y2) -> B2 = (x2 + dx2, y2 + dy2).

Let

  • vp = dx1 * dy2 - dx2 * dy1

If vp == 0 the segments are parallel and there is no intersection.

Otherwise, let v = (vx, vy) be the vector between A1 and A2

  • vx = x2 - x1
  • vy = y2 - y1

Compute

  • k1 = (vx * dy2 - vy * dx2) / vp
  • k2 = (vx * dy1 - vy * dx1) / vp

If either k1 or k2 fall outside the [0, 1] interval, the segments don't intersect (but the underlying lines do intersect). Otherwise, the intersection is at

(x1 + k1 * dx1, y1 + k1 * dy1)

which incidentally, if you wonder about symmetry, will be the same point as

(x2 + k2 * dx2, y2 + k2 * dy2)

These formulas are basically similar to the answer on How do you detect where two line segments intersect? except coding from there would not necessarily be trivial for either a newbie or someone in a rush (like I have been myself many times).

Community
  • 1
  • 1
dan3
  • 2,528
  • 22
  • 20
  • "If vp == 0 the segments are parallel and there is no intersection" or they are parallel and part of the same line. In the second case, additionally testing is needed to see if the segments overlap. – chux - Reinstate Monica Nov 02 '13 at 08:23