https://www.geometrictools.com/GTE/Mathematics/IntrLine2Circle2.h
(zs Intersections, l0, l1, center Point, radius, theta0, theta1 float64)
| 531 | |
| 532 | // https://www.geometrictools.com/GTE/Mathematics/IntrLine2Circle2.h |
| 533 | func intersectionLineCircle(zs Intersections, l0, l1, center Point, radius, theta0, theta1 float64) Intersections { |
| 534 | if l0.Equals(l1) { |
| 535 | return zs // zero-length Close |
| 536 | } |
| 537 | |
| 538 | // solve l0 + t*(l1-l0) = P + t*D = X (line equation) |
| 539 | // and |X - center| = |X - C| = R = radius (circle equation) |
| 540 | // by substitution and squaring: |P + t*D - C|^2 = R^2 |
| 541 | // giving: D^2 t^2 + 2D(P-C) t + (P-C)^2-R^2 = 0 |
| 542 | dir := l1.Sub(l0) |
| 543 | diff := l0.Sub(center) // P-C |
| 544 | length := dir.Length() |
| 545 | D := dir.Div(length) |
| 546 | |
| 547 | // we normalise D to be of length 1, so that the roots are in [0,length] |
| 548 | a := 1.0 |
| 549 | b := 2.0 * D.Dot(diff) |
| 550 | c := diff.Dot(diff) - radius*radius |
| 551 | |
| 552 | // find solutions for t ∈ [0,1], the parameter along the line's path |
| 553 | roots := []float64{} |
| 554 | r0, r1 := solveQuadraticFormula(a, b, c) |
| 555 | if !math.IsNaN(r0) { |
| 556 | roots = append(roots, r0) |
| 557 | if !math.IsNaN(r1) && !Equal(r0, r1) { |
| 558 | roots = append(roots, r1) |
| 559 | } |
| 560 | } |
| 561 | |
| 562 | // handle common cases with endpoints to avoid numerical issues |
| 563 | // snap closest root to path's start or end |
| 564 | if 0 < len(roots) { |
| 565 | if pos := l0.Sub(center); Equal(pos.Length(), radius) { |
| 566 | if len(roots) == 1 || math.Abs(roots[0]) < math.Abs(roots[1]) { |
| 567 | roots[0] = 0.0 |
| 568 | } else { |
| 569 | roots[1] = 0.0 |
| 570 | } |
| 571 | } |
| 572 | if pos := l1.Sub(center); Equal(pos.Length(), radius) { |
| 573 | if len(roots) == 1 || math.Abs(roots[0]-length) < math.Abs(roots[1]-length) { |
| 574 | roots[0] = length |
| 575 | } else { |
| 576 | roots[1] = length |
| 577 | } |
| 578 | } |
| 579 | } |
| 580 | |
| 581 | // add intersections |
| 582 | dira := dir.Angle() |
| 583 | tangent := len(roots) == 1 |
| 584 | for _, root := range roots { |
| 585 | pos := diff.Add(dir.Mul(root / length)) |
| 586 | angle := math.Atan2(pos.Y*radius, pos.X*radius) |
| 587 | if Interval(root, 0.0, length) && angleBetween(angle, theta0, theta1) { |
| 588 | pos = center.Add(pos) |
| 589 | dirb := ellipseDeriv(radius, radius, 0.0, theta0 <= theta1, angle).Angle() |
| 590 | zs = addLineArcIntersection(zs, pos, dira, dirb, root, 0.0, length, angle, theta0, theta1, tangent) |
no test coverage detected