https://www.particleincell.com/2013/cubic-line-intersection/
(zs Intersections, l0, l1, p0, p1, p2 Point)
| 366 | |
| 367 | // https://www.particleincell.com/2013/cubic-line-intersection/ |
| 368 | func intersectionLineQuad(zs Intersections, l0, l1, p0, p1, p2 Point) Intersections { |
| 369 | if l0.Equals(l1) { |
| 370 | return zs // zero-length Close |
| 371 | } |
| 372 | |
| 373 | // write line as A.X = bias |
| 374 | A := Point{l1.Y - l0.Y, l0.X - l1.X} |
| 375 | bias := l0.Dot(A) |
| 376 | |
| 377 | a := A.Dot(p0.Sub(p1.Mul(2.0)).Add(p2)) |
| 378 | b := A.Dot(p1.Sub(p0).Mul(2.0)) |
| 379 | c := A.Dot(p0) - bias |
| 380 | |
| 381 | roots := []float64{} |
| 382 | r0, r1 := solveQuadraticFormula(a, b, c) |
| 383 | if !math.IsNaN(r0) { |
| 384 | roots = append(roots, r0) |
| 385 | if !math.IsNaN(r1) { |
| 386 | roots = append(roots, r1) |
| 387 | } |
| 388 | } |
| 389 | |
| 390 | dira := l1.Sub(l0).Angle() |
| 391 | horizontal := math.Abs(l1.Y-l0.Y) <= math.Abs(l1.X-l0.X) |
| 392 | for _, root := range roots { |
| 393 | if Interval(root, 0.0, 1.0) { |
| 394 | var s float64 |
| 395 | pos := quadraticBezierPos(p0, p1, p2, root) |
| 396 | if horizontal { |
| 397 | s = (pos.X - l0.X) / (l1.X - l0.X) |
| 398 | } else { |
| 399 | s = (pos.Y - l0.Y) / (l1.Y - l0.Y) |
| 400 | } |
| 401 | if Interval(s, 0.0, 1.0) { |
| 402 | deriv := quadraticBezierDeriv(p0, p1, p2, root) |
| 403 | dirb := deriv.Angle() |
| 404 | endpoint := Equal(root, 0.0) || Equal(root, 1.0) || Equal(s, 0.0) || Equal(s, 1.0) |
| 405 | if endpoint { |
| 406 | // deviate angle slightly at endpoint when aligned to properly set Into |
| 407 | deriv2 := quadraticBezierDeriv2(p0, p1, p2) |
| 408 | if (0.0 <= deriv.PerpDot(deriv2)) == (Equal(root, 0.0) || !Equal(root, 1.0) && Equal(s, 0.0)) { |
| 409 | dirb += Epsilon * 2.0 // t=0 and CCW, or t=1 and CW |
| 410 | } else { |
| 411 | dirb -= Epsilon * 2.0 // t=0 and CW, or t=1 and CCW |
| 412 | } |
| 413 | dirb = angleNorm(dirb) |
| 414 | } |
| 415 | zs = zs.add(pos, s, root, dira, dirb, endpoint || Equal(A.Dot(deriv), 0.0), false) |
| 416 | } |
| 417 | } |
| 418 | } |
| 419 | return zs |
| 420 | } |
| 421 | |
| 422 | // https://www.particleincell.com/2013/cubic-line-intersection/ |
| 423 | func intersectionLineCube(zs Intersections, l0, l1, p0, p1, p2, p3 Point) Intersections { |