CODEWITHSUNDEEP
calgorithmcomputational-geometryxlibx11
Force.comBat
Force.comBat

Reputation: 245

How to find whether two line segment(not two straight lines) intersect

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?

Upvotes: 0

Views: 1033

Answers (1)

dan3
dan3

Reputation: 2559

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

Upvotes: 1

Related Questions