ajecc's blog

Intersection of 2 line segments
By ajecc, history, 6 years ago, In English

Can somebody explain how we can find the intersection of 2 line segments using only integer arithmetic (like this solution to a problem in a recent round 42626026)? I know how we can test if they intersect (with cross product), but I can't figure out how to find the exact point.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

What do you mean only integer arithmetic? Then you should probably represent the answer as rational number. The idea is as follows. Consider intersection of lines instead of intersection of segments (then check if point lies on both segments). Assume first line is given as set of points which look like and second line is solution of equation . Then you can find that for intersection point holds . After that you simply return for the value t you found.

Switching between distinct representations of lines should be an easy exercise for you.

P.S. You can also find the intersection point in algebraic way, solving system of two linear equations. This is straightforward but may yield a bit more of code.

P.P.S. You may refer to this article for more detailed explanation of basic analytic geometry stuff, including your question.

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

If you represent lines as equations like

ax + by = c
dx + ey = f

then intersection is the solution of the equation syste, which you can find using Cramer's rule, which means that you need to calculate 3 2x2 determinants A, B, C, and answers are A/C, B/C. Lines are parallel (or coincide) iff C=0

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is so easy to understand. now i feel a little dumb for asking this question. thank you

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For real? Like, this method was clearly mentioned in my answer alongside, with the one which needs only one line of code and assumes geometric approach and you think, this one is better? :\

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's just that I totally forgot that you could represent a line with ax+by=c instead of the classical representation with mx+n=y and the comment made sense right away. Stupid of me, i know. I'm sorry if I dissapointed you in any way.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Ok, sorry for being too emotional. I really was a bit disappointed since I mentioned system of linear equations method in my reply and that article. But no worries :)

          Anyway, you should probably avoid representing line as since it conceals true meaning of this equation, which is, of course, in coordinate form, where is normal vector to the line and is arbitrary point lying on the line.

          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        ofc this one is better — no thinking required

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          I didn't ask for opinion of a person who despises geometry and thinking. Get lost.

          → Reply