# Inserting points along a linear interval between adjacent coordinates in an array

Say I have a list of coordinates in an array

{{0, 0}, {0, 1}, {1, 1}}


I'd like to create a new array where, between each pair of nearest-neighbor coordinates in the previous array, I place $k$ points equispaced on a linear interval between the points. For example, with $k = 3$ we would generate the array:

{{0, 0}, {0, 0.25}, {0, 0.5}, {0, 0.75}, {0, 1},
{0.25, 1}, {0.5, 1}, {0.75, 1}, {1, 1}}


Is there a nice one-liner for doing this?

• @user8646 Did you try Insert[]? – Rod Jul 20 '13 at 14:35

edit InterpolationFunction

list = {{0, 0}, {0, 1}, {1, 1}}
k = 3;
r = (k + 1) Length@list - k;
Interpolation[Transpose[{Range[1, r, k + 1], #}], x,InterpolationOrder -> 1
] &/@ Transpose[list] /. {x -> #} & /@ Range[r]

{{0, 0}, {0, 1/4}, {0, 1/2}, {0, 3/4}, {0, 1},
{1/4, 1}, {1/2, 1}, {3/4, 1}, {1, 1}}


old

This works but is suspiciously long:

list = {{0, 0}, {0, 1}, {1, 1}};
k=3;

{list[]}~Join~(
Sequence @@ Table[#1 + i (#2 - #1)/(k + 1), {i, 1, k + 1}] & @@@ Partition[list, 2, 1])

{{0, 0}, {0, 1/4}, {0, 1/2}, {0, 3/4}, {0, 1}, {1/4, 1}, {1/2, 1},
{3/4, 1}, {1, 1}}


I do not like Join there so this is interesting replacement with Riffle (the difference is also in iterator range):

Riffle[
Sequence @@ Table[#1 + i (#2 - #1)/(k + 1), {i, 1, k}] & @@@ Partition[list, 2, 1],
list,
{1, -1, k + 1}
]

• @user8646 Please, do not accept so fast, I'm sure something better will appear :). You can still upvote if you like it ;) – Kuba Jul 20 '13 at 14:39
• I am getting "Table::iterb: Iterator {i,1,1+k} does not have appropriate bounds. >>" while running this..any idea ? – Rorschach Jul 20 '13 at 15:11
• @Blackbird You have to set k=3 for example. OP wants to be able to change k. I should have posted it. – Kuba Jul 20 '13 at 15:15
• yes now I got it..thanks – Rorschach Jul 20 '13 at 15:23
• @Blackbird No, thank you :) – Kuba Jul 20 '13 at 15:24

A very neat one liner does exist, and it's done using the 3 argument form of Array. Observe the following:

Array[# &, 5, {{0, 1}, {1, 1}}]
(* {{0, 1}, {1/4, 1}, {1/2, 1}, {3/4, 1}, {1, 1}} *)


where the 5 is your desired number of inserts (3) plus the endpoints (2). Array automatically does the insertion in the appropriate coordinates. Now you just need to use this on consecutive pairs and remove duplicate endpoints.

insertPoints[coords_, k_] := Array[# &, k + 2, #] & /@ Partition[coords, 2, 1] /.
{h__, t_} /; Length@coords > 2 :> Join[Most /@ {h}, {t}] ~Flatten~ 1


insertPoints[{{0, 0}, {0, 1}, {1, 1}}, 3] // N
(* {{0., 0.}, {0., 0.25}, {0., 0.5}, {0., 0.75}, {0., 1.},
{0.25, 1.}, {0.5, 1.}, {0.75, 1.}, {1., 1.}} *)

• Very nice use of Array! – bill s Jul 20 '13 at 16:29
• +1 for 3rd Array's argument reminding. It's a pity, that even with Array, insertPoints can't be shorter. – Kuba Jul 20 '13 at 16:35
• @Kuba Well, I tend to go by functionality and not just # of characters alone. Here, the primary need is to linearly sample and insert points between two coordinates A and B, and that is achieved in one Array call. The others are mostly for changing the OP's input to a suitable form and changing the output to OP's desired form (someone else could have a different form). These could be functions in their own right (thus usable elsewhere) and moved outside in OP's actual code. So it might end up looking like insertPoints[#, 5]& /@ coordPairs@coords // removeDupeEndpoints, which is clean. – rm -rf Jul 20 '13 at 16:46
• @rm-rf Fantastic - – user8646 Jul 20 '13 at 16:56
• @rm-rf I agree, do not get me wrong, I like it more than mine since Array does the dirty job. :) – Kuba Jul 20 '13 at 17:04

One line, as requested:

BSplineFunction[{{0, 0}, {0, 1}, {1, 1}}, SplineDegree -> 1] /@ Range[0, 1, 1/8]

(* {{0., 0.}, {0., 0.25}, {0., 0.5}, {0., 0.75}, {0., 1.},
{0.25,  1.}, {0.5, 1.}, {0.75, 1.}, {1., 1.}}


More generally, as a function:

insertPoints[pts_?ArrayQ, k_Integer] :=
BSplineFunction[pts, SplineDegree -> 1] /@ Range[0, 1, 1/((k + 1) (Length@pts - 1))]

insertPoints[{{0, 0}, {0, 1}, {1, 1}}, 3]
(* same output as above *)

• I'm struggling with InterpolationFunction but this is far better. – Kuba Jul 20 '13 at 18:46
• @Kuba If you figure out how to interpolate between points (not just real numbers), please post. (You could use two Interpolations to interpolate x and y separately, of course.) – Michael E2 Jul 20 '13 at 19:18
• I know, I did, take a look at my edit :) (indeed double Interpolate) But is is not as handy as BSplineFunction – Kuba Jul 20 '13 at 19:23
• I see it now - Good - I responded to the comment ping without looking at anything else. – Michael E2 Jul 20 '13 at 23:42
• Nice approach! +1 – Mr.Wizard Jul 30 '13 at 1:29

This method is limited, only working for k values of the form $2^n - 1$, but I like the style:

Nest[# ~Riffle~ MovingAverage[#, 2] &, a, 2]

{{0, 0}, {0, 1/4}, {0, 1/2}, {0, 3/4}, {0, 1}, {1/4, 1}, {1/2, 1}, {3/4, 1}, {1, 1}}


On the upside this method is concise and faster even than BSplineFunction.

More practically, here is my own application of Interpolation:

linearFill[a_List, k_Integer] :=
Interpolation[MapIndexed[{#2, #} &, a], InterpolationOrder -> 1] /@
Range[1, Length@a, 1/(k + 1)]

linearFill[{{0, 0}, {0, 1}, {1, 1}}, 2]

{{0, 0}, {0, 1/3}, {0, 2/3}, {0, 1}, {1/3, 1}, {2/3, 1}, {1, 1}}


This function is faster than Kuba's code, but not as fast as insertPoints which is blazing fast but only returns machine precision numbers. (I could not test R.M's method in version 7.)

• Yes, that's the Interpolation I was looking for. I thought I tried it. Actually, I thought I remembered using it a while ago, and when I tried it here, no go. Must have goofed. Thanks. The first one is cute. – Michael E2 Jul 30 '13 at 4:35