// interpolatePolynomial takes N sample points and returns
// the value at a given x using a lagrange interpolation.
197706
func interpolatePolynomial(x_samples, y_samples []uint8, x uint8) uint8 {
	limit := len(x_samples)
	var result, basis uint8
	for i := 0; i < limit; i++ {
		basis = 1
		for j := 0; j < limit; j++ {
			if i == j {
				continue
			}
			num := add(x, x_samples[j])
			denom := add(x_samples[i], x_samples[j])
			term := div(num, denom)
			basis = mult(basis, term)
		}
		group := mult(y_samples[i], basis)
		result = add(result, group)
	}
	return result
}
1023036
func interpolationFuncDistinct() ast.Function {
	return ast.Function{
		ArgTypes:     []ast.Type{ast.TypeList},
		ReturnType:   ast.TypeList,
		Variadic:     true,
		VariadicType: ast.TypeList,
		Callback: func(args []interface{}) (interface{}, error) {
			var list []string

			if len(args) != 1 {
				return nil, fmt.Errorf("accepts only one argument.")
			}

			if argument, ok := args[0].([]ast.Variable); ok {
				for _, element := range argument {
					if element.Type != ast.TypeString {
						return nil, fmt.Errorf(
							"only works for flat lists, this list contains elements of %s",
							element.Type.Printable())
					}
					list = appendIfMissing(list, element.Value.(string))
				}
			}

			return stringSliceToVariableValue(list), nil
		},
	}
}
121403
func (p *Path) Interpolate(percent float64) *Point {

	if percent <= 0 {
		return p.First()
	} else if percent >= 1 {
		return p.Last()
	}

	destination := p.Distance() * percent
	travelled := 0.0

	for i := 0; i < len(p.PointSet)-1; i++ {
		seg := NewLine(&p.PointSet[i], &p.PointSet[i+1])
		segDistance := seg.Distance()
		if (travelled + segDistance) > destination {
			var remainder = destination - travelled
			return seg.Interpolate(remainder / segDistance)
		}
		travelled += segDistance
	}

	return p.First()
}
1283655
func Poly(xvalues, yvalues []float64, degree int) ([]float64, error) {
	if len(xvalues) != len(yvalues) {
		return nil, ErrPolyRegArraysSameLength
	}

	m := len(yvalues)
	n := degree + 1
	y := New(m, 1, yvalues...)
	x := Zero(m, n)

	for i := 0; i < m; i++ {
		ip := float64(1)
		for j := 0; j < n; j++ {
			x.Set(i, j, ip)
			ip *= xvalues[i]
		}
	}

	q, r := x.QR()
	qty, err := q.Transpose().Times(y)
	if err != nil {
		return nil, err
	}

	c := make([]float64, n)
	for i := n - 1; i >= 0; i-- {
		c[i] = qty.Get(i, 0)
		for j := i + 1; j < n; j++ {
			c[i] -= c[j] * r.Get(i, j)
		}
		c[i] /= r.Get(i, i)
	}

	return c, nil
}
1001359
func interpolationFuncElement() ast.Function {
	return ast.Function{
		ArgTypes:   []ast.Type{ast.TypeList, ast.TypeString},
		ReturnType: ast.TypeString,
		Callback: func(args []interface{}) (interface{}, error) {
			list := args[0].([]ast.Variable)
			if len(list) == 0 {
				return nil, fmt.Errorf("element() may not be used with an empty list")
			}

			index, err := strconv.Atoi(args[1].(string))
			if err != nil || index < 0 {
				return "", fmt.Errorf(
					"invalid number for index, got %s", args[1])
			}

			resolvedIndex := index % len(list)

			v := list[resolvedIndex]
			if v.Type != ast.TypeString {
				return nil, fmt.Errorf(
					"element() may only be used with flat lists, this list contains elements of %s",
					v.Type.Printable())
			}
			return v.Value, nil
		},
	}
}
1223676
func (s *RadialSimplifier) MultiPolygon(mp orb.MultiPolygon) orb.MultiPolygon {
	return multiPolygon(s, mp)
}
1263451
func Interpolate(a, b *T, t float32) T {
	t1 := 1 - t
	return T{
		a[0]*t1 + b[0]*t,
		a[1]*t1 + b[1]*t,
		a[2]*t1 + b[2]*t,
	}
}
171636
func interpolationFuncTitle() ast.Function {
	return ast.Function{
		ArgTypes:   []ast.Type{ast.TypeString},
		ReturnType: ast.TypeString,
		Callback: func(args []interface{}) (interface{}, error) {
			toTitle := args[0].(string)
			return strings.Title(toTitle), nil
		},
	}
}
1203377
func (c *Config) InterpolatedVariables() map[string][]InterpolatedVariable {
	result := make(map[string][]InterpolatedVariable)
	for source, rc := range c.rawConfigs() {
		for _, v := range rc.Variables {
			result[source] = append(result[source], v)
		}
	}
	return result
}
931243
func interpolationFuncConcat() ast.Function {
	return ast.Function{
		ArgTypes:     []ast.Type{ast.TypeList},
		ReturnType:   ast.TypeList,
		Variadic:     true,
		VariadicType: ast.TypeList,
		Callback: func(args []interface{}) (interface{}, error) {
			var outputList []ast.Variable

			for _, arg := range args {
				for _, v := range arg.([]ast.Variable) {
					switch v.Type {
					case ast.TypeString:
						outputList = append(outputList, v)
					case ast.TypeList:
						outputList = append(outputList, v)
					case ast.TypeMap:
						outputList = append(outputList, v)
					default:
						return nil, fmt.Errorf("concat() does not support lists of %s", v.Type.Printable())
					}
				}
			}

			// we don't support heterogeneous types, so make sure all types match the first
			if len(outputList) > 0 {
				firstType := outputList[0].Type
				for _, v := range outputList[1:] {
					if v.Type != firstType {
						return nil, fmt.Errorf("unexpected %s in list of %s", v.Type.Printable(), firstType.Printable())
					}
				}
			}

			return outputList, nil
		},
	}
}
792950
func (g *Geometry) LineInterpolatePoint(dist float64) (*Geometry, error) {
	// This code ported from LWGEOM_line_interpolate_point in postgis,
	// by jsunday@rochgrp.com and strk@refractions.net.

	if dist < 0 || dist > 1 {
		return nil, ErrLineInterpolatePointDist
	}

	typ, err := g.Type()
	if err != nil {
		return nil, err
	}
	if typ != LINESTRING {
		return nil, ErrLineInterpolatePointType
	}

	empty, err := g.IsEmpty()
	if err != nil {
		return nil, err
	}
	if empty {
		pt, err := NewPoint()
		if err != nil {
			return nil, err
		}
		return pt, nil
	}

	// If distance is one of two extremes, return the point on that end.
	if dist == 0.0 || dist == 1.0 {
		var (
			pt  *Geometry
			err error
		)
		if dist == 0.0 {
			pt, err = g.StartPoint()
		} else {
			pt, err = g.EndPoint()
		}
		if err != nil {
			return nil, err
		}
		return pt, nil
	}

	// Interpolate a point on the line.

	nsegs, err := g.NPoint()
	if err != nil {
		return nil, err
	}
	nsegs--

	length, err := g.Length()
	if err != nil {
		return nil, err
	}

	var tlength float64

	for i := 0; i < nsegs; i++ {
		a, err := g.Point(i)
		if err != nil {
			return nil, err
		}
		b, err := g.Point(i + 1)
		if err != nil {
			return nil, err
		}

		// Find the relative length of this segment.
		slength, err := a.Distance(b)
		if err != nil {
			return nil, err
		}
		slength /= length

		if dist < tlength+slength {
			dseg := (dist - tlength) / slength
			pt, err := interpolatePoint2D(a, b, dseg)
			if err != nil {
				return nil, err
			}
			return pt, nil
		}
		tlength += slength
	}

	// Return the last point on the line. This shouldn't happen, but could if
	// there's some floating point rounding errors.
	return g.EndPoint()
}
504082
func interpolationFuncMin() ast.Function {
	return ast.Function{
		ArgTypes:     []ast.Type{ast.TypeFloat},
		ReturnType:   ast.TypeFloat,
		Variadic:     true,
		VariadicType: ast.TypeFloat,
		Callback: func(args []interface{}) (interface{}, error) {
			min := args[0].(float64)

			for i := 1; i < len(args); i++ {
				min = math.Min(min, args[i].(float64))
			}

			return min, nil
		},
	}
}
670350
func (p *Path) ResampleWithInterval(dist float64) *Path {
	if dist <= 0 {
		p.PointSet = make([]Point, 0)
		return p
	}

	// precomputes the total distance and intermediate distances
	total, dists := precomputeDistances(p.PointSet)

	totalPoints := int(total/dist) + 1
	if p.resampleEdgeCases(totalPoints) {
		return p
	}

	p.resample(dists, total, totalPoints)
	return p
}
1187221
func interpolationFuncIndex() ast.Function {
	return ast.Function{
		ArgTypes:   []ast.Type{ast.TypeList, ast.TypeString},
		ReturnType: ast.TypeInt,
		Callback: func(args []interface{}) (interface{}, error) {
			haystack := args[0].([]ast.Variable)
			needle := args[1].(string)
			for index, element := range haystack {
				if needle == element.Value {
					return index, nil
				}
			}
			return nil, fmt.Errorf("Could not find '%s' in '%s'", needle, haystack)
		},
	}
}
1181703
func interpolationFuncCoalesceList() ast.Function {
	return ast.Function{
		ArgTypes:     []ast.Type{ast.TypeList},
		ReturnType:   ast.TypeList,
		Variadic:     true,
		VariadicType: ast.TypeList,
		Callback: func(args []interface{}) (interface{}, error) {
			if len(args) < 2 {
				return nil, fmt.Errorf("must provide at least two arguments")
			}
			for _, arg := range args {
				argument := arg.([]ast.Variable)

				if len(argument) > 0 {
					return argument, nil
				}
			}
			return make([]ast.Variable, 0), nil
		},
	}
}
740234
func (l *Line) Interpolate(percent float64) *Point {
	return &Point{
		l.a[0] + percent*(l.b[0]-l.a[0]),
		l.a[1] + percent*(l.b[1]-l.a[1]),
	}
}
1140580
func interpolationFuncFormatList() ast.Function {
	return ast.Function{
		ArgTypes:     []ast.Type{ast.TypeAny},
		Variadic:     true,
		VariadicType: ast.TypeAny,
		ReturnType:   ast.TypeList,
		Callback: func(args []interface{}) (interface{}, error) {
			// Make a copy of the variadic part of args
			// to avoid modifying the original.
			varargs := make([]interface{}, len(args)-1)
			copy(varargs, args[1:])

			// Verify we have some arguments
			if len(varargs) == 0 {
				return nil, fmt.Errorf("no arguments to formatlist")
			}

			// Convert arguments that are lists into slices.
			// Confirm along the way that all lists have the same length (n).
			var n int
			listSeen := false
			for i := 1; i < len(args); i++ {
				s, ok := args[i].([]ast.Variable)
				if !ok {
					continue
				}

				// Mark that we've seen at least one list
				listSeen = true

				// Convert the ast.Variable to a slice of strings
				parts, err := listVariableValueToStringSlice(s)
				if err != nil {
					return nil, err
				}

				// otherwise the list is sent down to be indexed
				varargs[i-1] = parts

				// Check length
				if n == 0 {
					// first list we've seen
					n = len(parts)
					continue
				}
				if n != len(parts) {
					return nil, fmt.Errorf("format: mismatched list lengths: %d != %d", n, len(parts))
				}
			}

			// If we didn't see a list this is an error because we
			// can't determine the return value length.
			if !listSeen {
				return nil, fmt.Errorf(
					"formatlist requires at least one list argument")
			}

			// Do the formatting.
			format := args[0].(string)

			// Generate a list of formatted strings.
			list := make([]string, n)
			fmtargs := make([]interface{}, len(varargs))
			for i := 0; i < n; i++ {
				for j, arg := range varargs {
					switch arg := arg.(type) {
					default:
						fmtargs[j] = arg
					case []string:
						fmtargs[j] = arg[i]
					}
				}
				list[i] = fmt.Sprintf(format, fmtargs...)
			}
			return stringSliceToVariableValue(list), nil
		},
	}
}