A segment and a ray are given by coordinates (a segment by the coordinates of the ends, a ray by the coordinates of the beginning and an arbitrary point). How to check whether they will intersect? thanks for the help

  • one
    You get the point of intersection of the lines, check whether it belongs to the segment and the ray. - Yura Ivanov

2 answers 2

Usually they do this: first find the point of intersection of the lines

struct pt { double x, y; }; struct line { double a, b, c; }; const double EPS = 1e-9; double det (double a, double b, double c, double d) { return a * d - b * c; } bool intersect (line m, line n, pt & res) { double zn = det (ma, mb, na, nb); if (abs (zn) < EPS) return false; res.x = - det (mc, mb, nc, nb) / zn; res.y = - det (ma, mc, na, nc) / zn; return true; }

http://e-maxx.ru/algo/lines_intersection

Then check that this point lies on the segment. for example

res.x >= x0 && res.x <= x1 && res.y >= y0 && res.y <= y1

Then check that on the right side on the beam. for example

(res.x > x0) == (x1 > x0) && (res.y > y0) == (y1 > y0) .

In general, this is all pure mathematics.

  • The verification of the side of the ray is not quite clear) But I will do it through the scalar product of 2 vectors (if> 0, then co-directed, then a point on the ray). Thanks more for the help! - Limmy
  • @Limmy says there that our x coordinate lies on the same side of the starting point as the 2 coordinate of the ray. Similarly for y . - pavel

L (xy) is the beginning of a ray, Lp (xy) is a ray of a point, A (xy), B (xy). result -?

 boolean a = By < Lpy// при Lpx = Bx boolean b = Ay < Lpy// при Lpy = Ax result = !(a ^ b)
  • cool, but nothing depends on L(xy) ? - Igor
  • L (xy) is needed to find Lpy, the task is not to find the point, but to find out if it is peresikat. - Mikhail Kolomiyets
  • Where is the rationale for this algorithm? Or could you explain what is happening here? - ampawd 5:06
  • @ MikhailKolomiets - Please! Do not delete or edit your previous comment! :) - Igor
  • The first line is the initial data. 2 - look for the y coordinate of the ray at the x coordinate = the x coordinate of the B point of the line. 4 - if both expressions are the same - the results do not intersect - Mikhail Kolomiets