2D Vector Library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

interp.go 1.4KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
  1. package vector
  2. import (
  3. "errors"
  4. "fmt"
  5. )
  6. // explicitly implements Neville's algorithm for three points at very
  7. // particular parameter values: ts[]{0, 1/3, 2/3}, extrapolate to 1.
  8. func Extrapolate(P []Point2d) (*Point2d, error) {
  9. if len(P) != 3 {
  10. return nil, errors.New("only works for len(P) == 3")
  11. }
  12. // P_{01} = -2 * P_0 + 3 * P_1
  13. p01 := P[0].ToVector().Scale(-2.0).ToPoint().Add(P[1].ToVector().Scale(3.0))
  14. // P_{12} = -1 * P_1 + 2 * P_2
  15. p12 := P[1].ToVector().Scale(-1.0).ToPoint().Add(P[2].ToVector().Scale(2.0))
  16. // P_{012} = 1/2 * P_{01} + 3/2 * P_{12}
  17. p012 := p01.ToVector().Scale(-1.0 / 2.0).ToPoint().Add(p12.ToVector().Scale(3.0 / 2.0))
  18. return &p012, nil
  19. }
  20. // Implements Neville's Algorithm for a slice of points (P) at parameter
  21. // values(ts), to parameter value (t). Returns the point and an error
  22. func Neville(P []Point2d, ts []float64, t float64) (*Point2d, error) {
  23. if len(P) != len(ts) {
  24. return nil, errors.New(
  25. fmt.Sprintf(
  26. "Incompatable slice lengths len(P): %d != len(ts): %d",
  27. len(P),
  28. len(ts),
  29. ),
  30. )
  31. }
  32. Q := []Point2d(P)
  33. order := len(P) - 1
  34. for i := 0; i < order; i++ {
  35. for j := 0; j < order-i; j++ {
  36. tLeft := ts[i+j+1] - t
  37. tRight := t - ts[j]
  38. Q[j] = Q[j].ToVector().Scale(tLeft).ToPoint().Add(P[j+1].ToVector().Scale(tRight))
  39. Q[j] = Q[j].ToVector().Scale(1.0 / (ts[i+j+1] - ts[j])).ToPoint()
  40. }
  41. }
  42. return &Q[0], nil
  43. }