nemesis's blog

Intersection Problem
By nemesis, history, 9 years ago, In English

  • We have got two line.And we know the line's start and end point cordinate. And if they intersect we will write "Yes" or if they dont intersect write "No" .

  • Forexample line1 start (-2,2) and end (2,2) line2 start (-3,-2) and end (2,3)

  • The lines are intersect. We will write "Yes".
  • Input : -2 2 2 2 -3 -2 2 3

  • Output : "Yes"

- I need this problem's solution . Thanks.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nemesis (previous revision, new revision, compare).

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

I think there are formulas which can help you.

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

The top answer in this link helps me evertime:

http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

This tells you where they collide, which is more information than you need. If you want a simpler one, there is a simpler approach with only 4 cross products.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Consider two segments — (A,B) and (C,D). Let S(P1,P2,P3) be the oriented area of triangle (P1,P2,P3). It's easy to see that if the segments intersect, then A and B should be in different half-planes about line (C,D) and C and D should be in different half-planes about line (A,B) (I am not sure if "about" is the right word, I am sorry if I am wrong and I guess I am). So we want S(A,B,C)*S(A,B,D)<0 and S(C,D,A)*S(C,D,B)<0, of course it may be <=0 depending on what you call intersection :)

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

Thanks ...

→ Reply