# Interpolation

Our next step is to learn how to create smooth curves connecting points. The specific types of curves are known as interpolated splines. Interpolation means guessing at a value inbetween points. A spline is a specific type of function that will generate the smooth curve.

The example below sampling between 3 and 15 points from a parametric circle, and interpolating a curve from these points.

We can see that the curve more closely resembles a circle as we increase the number of points used to create it.

We use the `OpenPath.interpolatingSplice`

or `ClosedPath.interpolatingSpline`

method to interpolate a curve,
producing a `List[PathElement]`

.
The method expects a `List[Point]`

.
These lists are types made of two parts.
For example, `List[Point]`

consists of

`List`

, which is what's known as a container or collection, meaning it holds other values; and`Point`

, which is the type of the values inside the list.

(Notice that all the elements of a list must have the same type.)

Right now we only need to know how to create lists. In later chapters we'll learn a lot more about how to work with lists and other collections.

The simplest way to construct a list is by calling the `List`

constructor with the values we want in the list.
The example below creates a `List[Int]`

, with the elements `1`

, `2`

, and `3`

.

```
List(1, 2, 3)
// res0: List[Int] = List(1, 2, 3)
```

The order of the elements in the list is important, so the following two lists are different.

```
val oneToThree = List(1, 2, 3)
val threeToOne = List(3, 2, 1)
```

```
oneToThree == threeToOne
// res1: Boolean = false
```

This way of constructing lists requires we know all the elements in advance. More often we'll want to compute the elements as part of our program. This is exactly what we'll be doing here, as the elements of the list will be the points from our parametric curve.

There is a pattern for creating lists an element at a time. We either:

- create an empty list, using the expression
`List.empty`

; or - add an element to the front of an existing list, using an expression like
`anElement :: aList`

.

Here's a quick example, creating the same list as `List(1, 2, 3)`

.

```
1 :: 2 :: 3 :: List.empty
// res2: List[Int] = List(1, 2, 3)
```

Let's talk about the expression `anElement :: aList`

a little bit.
We know that in Scala we always interact with objects using method calls,
and we can write method calls in two styles:

- operator style:
`1 + 2`

; or - normal method call style:
`1.+(2)`

.

There is another rule to operator style.
A method that ends in a colon (`:`

) is *right-associative*.
This means that, in operator style, instead of writing `object method parameter`

we write `parameter method object`

.
So

`1 :: 2 :: 3 :: List.empty`

is the same as

`(1 :: (2 :: (3 :: List.empty)))`

which is the same as

`List.empty.::(3).::(2).::(1)`

Let's now see a bigger example. We will write a method that creates a list of natural numbers. This list will have as many elements as the natural number parameter passed to the method. The elements will decrease from left to right, ending at zero.

In other words, the method skeleton is

```
def range(count: Int): List[Int] =
???
```

and we want results like

```
range(0) == List.empty
range(3) == List(2, 1, 0)
range(5) == List(4, 3, 2, 1, 0)
```

Our first step is to recognize we have a structural recursion over the natural numbers.

```
def range(count: Int): List[Int] =
count match {
case 0 => ???
case n => ??? range(n - 1)
}
```

We can use our normal strategies for reasoning about structural recursion, alongside the pattern for creating lists. Let's walk through it.

The first step is to consider each case independently. We'll start with the base case. The pattern for creating lists tells us we must either use

`List.empty`

; or`anElement :: aList`

In this case the answer is `List.empty`

,
which we can tell from the method description.

Moving to the next case,
we have the recursion which produces a `List[Int]`

.
This suggests we should use the `anElement :: aList`

pattern.
We might guess that we should write

`case n => n :: range(n - 1)`

but this will give us a list that ends at 1, not 0. The solution is to instead use

`case n => (n - 1) :: range(n - 1)`

This gives us the full solution

```
def range(count: Int): List[Int] =
count match {
case 0 => List.empty
case n => (n - 1) :: range(n - 1)
}
```

We can check we have the correct solution by comparing the output to the examples above.

```
// Expect List.empty, also written List()
range(0)
// res6: List[Int] = List()
// Expect List(2, 1, 0)
range(3)
// res7: List[Int] = List(2, 1, 0)
// Expect List(4, 3, 2, 1, 0)
range(5)
// res8: List[Int] = List(4, 3, 2, 1, 0)
```

#### Exercise: Ranging About

In the example above the list elements decrease from left to right,
which is not how we usually order numbers.
Write an alternative method where the values *increase* from left to right.

We can use the same general structure as `range`

,
but we need an auxillary parameter to hold the current value to put into the list.
We then use a nested method so that the user doesn't have to deal with this additional parameter.

```
def rangeReversed(count: Int): List[Int] = {
def loop(count: Int, value: Int): List[Int] =
count match {
case 0 => List.empty
case n => value :: loop(n - 1, value + 1)
}
loop(count, 0)
}
```

```
rangeReversed(0)
// res9: List[Int] = List()
rangeReversed(3)
// res10: List[Int] = List(0, 1, 2)
rangeReversed(5)
// res11: List[Int] = List(0, 1, 2, 3, 4)
```

## Interpolating Parametric Curves

Now we can put all the pieces together:

- sample a
`List[Point]`

from a parametric curve; and - interpolate that
`List[Point]`

to produce a smooth curve.

The first part requires a method, which we'll call `sampleCurve`

, that is very similar to `drawCurve`

that we've used earlier.

#### Exercise: Getting to the Point

Implement `sampleCurve`

with the following skeleton

```
def sampleCurve(points: Int, curve: Angle => Point): List[Point] =
???
```

This is a modification of `drawCurve`

that produces a `List[Point]`

instead of an `Image`

.

```
def sampleCurve(points: Int, curve: Angle => Point): List[Point] = {
val turn = Angle.one / points
def loop(count: Int): List[Point] =
count match {
case 0 => List.empty
case n =>
val pt = curve(turn * n)
pt :: loop(n - 1)
}
loop(points)
}
```

To do the second part is to create the spline by calling the `interpolatingSpline`

method on either `ClosedPath`

or `OpenPath`

.
Remember that closed paths always have a line connecting the end to the start,
while open paths do not.
Which you should use depends on the curve you're drawing.
If we're drawing a spiral, for example, an open path is appropriate.
For a circle we'd use a closed path instead.
The example below shows this.

This image is created with the code

```
val nSamples = 350
Image
.path(
OpenPath.interpolatingSpline(
sampleCurve(nSamples, parametricSpiral.andThen(scale(100)))
)
)
.beside(
Image
.path(
ClosedPath.interpolatingSpline(
sampleCurve(nSamples, parametricCircle.andThen(scale(100)))
)
)
)
```

#### Exercise: The Spline of Your Life

Use `sampleCurve`

, interpolation, and the parametric curves we've created earlier to create your own masterpiece.
In addition to spirals and circles, we have seen rose and Lissajous curves in a previous chapter.

For many curves, such as a spiral, it's useful to sample over more than a full turn.
You might find it useful to add an additional parameter to `sampleCurve`

, to give the angle that should be covered by the samples.

Below is an example I created using Lissajous curves. (The dashed lines are created using the `strokeDash`

method.) I'm sure you can be a lot more creative.