There are two arrays of points that form two broken lines. Is there an algorithm for finding the intersection points of these two lines?

The search for the intersection of each of the segments of both lines comes to mind.

  • Wow, curves ... you can, for example, if these curves correspond to some graphs of functions (and not necessarily the same). - AseN
  • @ 0xFFh doesn’t correspond to the graphs of the function - andrew68
  • one
    I am afraid, then, if it is easy with the help of mathematics, then there is no other way. - AseN
  • 2
    An array of points cannot describe a curve, only a broken line. Cases 2: 1) Suppose the approximation corresponds to the situation "1 point = 1 pixel". Then the "curves" intersect at points with the same coordinates. 2) For approximation of a curve, adjacent points are connected by segments. Then we iterate over the pairs of neighboring points for the "curves", and see if the segments connecting them intersect. - user6550
  • @klopp did not say so. Polyline And yes, I think, just going through all the segments will save me. - andrew68

1 answer 1

The classic textbook algorithm for finding all intersections in a set of segments is the sweep line algorithm. The fact that in your case we are dealing not with an arbitrary set of segments, but with two broken lines, as it seems to me, does not greatly change the situation.

Another thing, if you know in advance any additional information about your broken lines.

For example, if you know in advance that your broken lines are monotonous along a general direction, then in such a situation you can search for all intersections by a simple linear passage along the broken line.

  • And can you add a link to the algorithm, or even its schematic description? - VladD