Say I have an array with 60 elements, and I want to select 40 elements from this array. The subset should consist of elements with evenly spaced indices. In theory I would need to select every 1.5th point, which is obviously not possible.
I tried doing it with a recursive function, kind of a divide & conquer approach. It selects the point in the middle between two boundaries and adds it to the result, then it splits this range up into two sub-ranges and executes the function again for these ranges:
Private Sub AddMiddlePoint(ByRef data() As Double, ByRef Result As List(Of Double), Lowerindex As Integer, Upperindex As Integer, MaxVals As Integer, MinSize As Integer) Dim middle As Integer = CInt((Upperindex + Lowerindex) / 2) Dim newBorderLower1 As Integer = Lowerindex Dim newBorderUpper1 As Integer = middle Dim newBorderLower2 As Integer = middle + 1 Dim newBorderUpper2 As Integer = Upperindex If Result.Count < MaxVals Then Result.Add(data(middle)) If newBorderUpper1 - newBorderLower1 > MinSize Then AddMiddlePoint(data, Result, newBorderLower1, newBorderUpper1, MaxVals, MinSize) If newBorderUpper2 - newBorderLower2 > MinSize Then AddMiddlePoint(data, Result, newBorderLower2, newBorderUpper2, MaxVals, MinSize) End If End Sub
I call this function like this:
Private Function ThinOutData(source() As Double, Percentage As Integer) As Double() Dim newData As New List(Of Double) Dim amount As Integer = CInt(Percentage / 100 * source.Count) AddMiddlePoint(source, newData, 0, source.Count - 1, amount, CInt(Int(1 / Percentage) + 1)) Return newData.ToArray End Function
It basically works, but the subset that is selected isn't very evenly spaced. Some huge gaps, some small gaps and so on.
Does anyone have a suggestion how this can be improved? I am of course aware that you can't get perfectly even spacing for fractional steps, but my method returns uneven points even if it needs to pull every second or third value from the array.
My code is in VB.NET but feel free to use other languages that you are familiar with. It shouldn't be too hard to translate, I guess.