CODEWITHSUNDEEP
geometryintersectionlines
borchero
borchero

Reputation: 6032

Line segment intersection

I found this code snippet on raywenderlich.com, however the link to the explanation wasn't valid anymore. I "translated" the answer into Swift, I hope you can understand, it's actually quite easy even without knowing the language. Could anyone explain what exactly is going on here? Thanks for any help.

class func linesCross(#line1: Line, line2: Line) -> Bool {
    let denominator = (line1.end.y - line1.start.y) * (line2.end.x - line2.start.x) -
        (line1.end.x - line1.start.x) * (line2.end.y - line2.start.y)

    if denominator == 0 { return false } //lines are parallel

    let ua = ((line1.end.x - line1.start.x) * (line2.start.y - line1.start.y) -
        (line1.end.y - line1.start.y) * (line2.start.x - line1.start.x)) / denominator
    let ub = ((line2.end.x - line2.start.x) * (line2.start.y - line1.start.y) -
        (line2.end.y - line2.start.y) * (line2.start.x - line1.start.x)) / denominator

    //lines may touch each other - no test for equality here
    return ua > 0 && ua < 1 && ub > 0 && ub < 1
}

Upvotes: 2

Views: 469

Answers (3)

Leandro Caniglia
Leandro Caniglia

Reputation: 14843

This is what the code is doing.

Every point P in the segment AB can be described as:

P = A + u(B - A)

for some constant 0 <= u <= 1. In fact, when u=0 you get P=A, and you getP=B when u=1. Intermediate values of u will give you intermediate values of P in the segment. For instance, when u = 0.5 you will get the point in the middle. In general, you can think of the parameter u as the ratio between the lengths of AP and AB.

enter image description here

Now, if you have another segment CD you can describe the points Q on it in the same way, but with a different u, which I will call v:

Q = C + v(D - C)

Again, keep in mind that Q lies between C and D if, and only if, 0 <= v <= 1 (same as above for P).

To find the intersection between the two segments you have to equate P=Q. In other words, you need to find u and v, both between 0 and 1 such that:

A + u(B - A) = C + v(D - C)

So, you have this equation and you have to see if it is solvable within the given constraints on u and v.

Given that A, B, C and D are points with two coordinates x,y each, you can open the equation above into two equations:

ax + u(bx - ax) = cx + v(dx - cx)
ay + u(by - ay) = cy + v(dy - cy)

where ax = A.x, ay = A.y, etc., are the coordinates of the points.

Now we are left with a 2x2 linear system. In matrix form:

|bx-ax  cx-dx| |u| = |cx-ax|
|by-ay  cy-dy| |v|   |cy-ay|

The determinant of the matrix is

det = (bx-ax)(cy-dy) - (by-ay)(cx-dx)

This quantity corresponds to the denominator of the code snippet (please check).

Now, multiplying both sides by the cofactor matrix:

|cy-dy  dx-cx|
|ay-by  bx-ax|

we get

det*u = (cy-dy)(cx-ax) + (dx-cx)(cy-ay)
det*v = (ay-by)(cx-ax) + (bx-ax)(cy-ay)

which correspond to the variables ua and ub defined in the code (check this too!)

Finally, once you have u and v you can check whether they are both between 0 and 1 and in that case return that there is intersection. Otherwise, there isn't.

Upvotes: 1

Joseph O&#39;Rourke
Joseph O&#39;Rourke

Reputation: 4406

You can find a detailed segment-intersection algorithm in the book Computational Geometry in C, Sec. 7.7. The SegSegInt code described there is available here. I recommend avoiding slope calculations.

There are several "degenerate" cases that require care: collinear segments overlapping or not, one segment endpoint in the interior of the other segments, etc. I wrote the code to return an indication of these special cases.

Upvotes: 2

Uri Goren
Uri Goren

Reputation: 13700

For a given line the slope is

m=(y_end-y_start)/(x_end-x_start)

if two slopes are equal, the lines are parallel

m1=m1

(y1_end-y_start)/(x1_end-x1_start)=(y2_end-y2_start)/(x2_end-x2_start)

And this is equivalent to checking that the denominator is not zero,

Regarding the rest of the code, find the explanation on wikipedia under "Given two points on each line"

Upvotes: 0

Related Questions