LineIntersection returns the point where the line segments one and two intersect and true if there is intersection, nil and false when line segments one and two do not intersect
(one, two Line)
| 397 | // intersect and true if there is intersection, nil and false when line |
| 398 | // segments one and two do not intersect |
| 399 | func LineIntersection(one, two Line) (Point, bool) { |
| 400 | p := one.P1 |
| 401 | q := two.P1 |
| 402 | |
| 403 | r := one.P2 |
| 404 | r.Subtract(p) |
| 405 | s := two.P2 |
| 406 | s.Subtract(q) |
| 407 | |
| 408 | // t = (q − p) × s / (r × s) |
| 409 | // u = (q − p) × r / (r × s) |
| 410 | // So then we define |
| 411 | // qmp = (q - p) |
| 412 | // rcs = (r × s) |
| 413 | // and we get simply: |
| 414 | // t = qmp × s / rcs |
| 415 | // u = qmp × r / rcs |
| 416 | qmp := q |
| 417 | qmp.Subtract(p) |
| 418 | qmpcs := CrossProduct(qmp, s) |
| 419 | qmpcr := CrossProduct(qmp, r) |
| 420 | rcs := CrossProduct(r, s) |
| 421 | |
| 422 | t := qmpcs / rcs |
| 423 | u := qmpcr / rcs |
| 424 | // if rcs == 0 then it's either collinear or parallel. It'll be +/- inf, so it'll skip this statement and return at the end |
| 425 | if t >= 0 && t <= 1 && u >= 0 && u <= 1 { |
| 426 | // the two line segments meet at the point p + t r = q + u s. |
| 427 | return Point{p.X + t*r.X, p.Y + t*r.Y}, true |
| 428 | } |
| 429 | |
| 430 | return Point{}, false |
| 431 | } |
| 432 | |
| 433 | // LineTraceFraction returns the trace fraction of tracer through boundary |
| 434 | // 1 means no intersection |