TomWilson
asked on
How to tell if two lines have crossed over each other
I have a series of points stored in an array. The points form lines that have been drawn on the screen.
---
For example:
First Point: 0, 0
Second Point: 10, 20
Third Point: 30, 10
Fourth Point: 20, 10
The lines would be in the above case:
The first line would go from 0, 0 to 10, 20. The second line would go from 10, 20 to 30, 10 and the last line would go from 20, 30 to 20, 10.
So that the next line begins where the previous one ended.
---
The problem that I have is how to tell when two or more of the lines have crossed over each other..
---
For example:
First Point: 0, 0
Second Point: 10, 20
Third Point: 30, 10
Fourth Point: 20, 10
The lines would be in the above case:
The first line would go from 0, 0 to 10, 20. The second line would go from 10, 20 to 30, 10 and the last line would go from 20, 30 to 20, 10.
So that the next line begins where the previous one ended.
---
The problem that I have is how to tell when two or more of the lines have crossed over each other..
Consider the two straight lines:
y1=m1*x1 + b1
y2=m2*x2 + b2
If m1==m2, they are parallel, otherwise they must cross somewhere. That intersection will be at:
x3=(b2-b1)/(m1-m2).
If the x3 and its' derive y3 both fall within the x and y ranges of the line segments, then the segments intersect.
Do you know how to compute the parametric representation of the line defined by the endpoints of a segment?
y1=m1*x1 + b1
y2=m2*x2 + b2
If m1==m2, they are parallel, otherwise they must cross somewhere. That intersection will be at:
x3=(b2-b1)/(m1-m2).
If the x3 and its' derive y3 both fall within the x and y ranges of the line segments, then the segments intersect.
Do you know how to compute the parametric representation of the line defined by the endpoints of a segment?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Quite correct, but... Checking 2 segments intersection it is only a part of the problem. If you check intersections for all segments you get obviously _o_(n^2).
That can be improved to O( (n+k)logn ) (where k is the number of intersections), using sweep line algorithm. In the case when it is only need to check wether _any_ of segments from the set have crossed each over, it can be improved to nice O(nlogn) time (!).
Refer to "Michael I. Shamos and Dan Hoey. Geometric intersection problems. In 17th Annual Symposium on Foundations of Computer Science, pages 208-215, Houston, Texas, 25-27 October 1976. IEEE" for the segment intersection algorithms. In the "Cormen, T.H., Leiserson, C.E. and Rivest, R.L. Introduction to Algorithms. MIT Press 1990", the clear "ANY-SEGMENT-INTERSECT" O(nlogn) algorithm presentation can be found. Many web resources exist as well, but almost of implementations adapted for collecting intersection points rather than determining their existense. You can easily adapt such a code for your case, but you need some background about the algorithm itself.
That can be improved to O( (n+k)logn ) (where k is the number of intersections), using sweep line algorithm. In the case when it is only need to check wether _any_ of segments from the set have crossed each over, it can be improved to nice O(nlogn) time (!).
Refer to "Michael I. Shamos and Dan Hoey. Geometric intersection problems. In 17th Annual Symposium on Foundations of Computer Science, pages 208-215, Houston, Texas, 25-27 October 1976. IEEE" for the segment intersection algorithms. In the "Cormen, T.H., Leiserson, C.E. and Rivest, R.L. Introduction to Algorithms. MIT Press 1990", the clear "ANY-SEGMENT-INTERSECT" O(nlogn) algorithm presentation can be found. Many web resources exist as well, but almost of implementations adapted for collecting intersection points rather than determining their existense. You can easily adapt such a code for your case, but you need some background about the algorithm itself.
ASKER
Comment accepted as answer
-MasterGaurav