Skip to content

Instantly share code, notes, and snippets.

@niko86
Last active June 10, 2019 23:52
Show Gist options
  • Save niko86/651303a0ff8abe025b2d015fef6f3cf6 to your computer and use it in GitHub Desktop.
Save niko86/651303a0ff8abe025b2d015fef6f3cf6 to your computer and use it in GitHub Desktop.
Working DouglasPeucker algorithm, implemented in Excel VBA. Three things are required in a spreadsheet, one a named range "Epsilon", two a "Table1" on "Sheet1" and three "Table2" on "Sheet2".
483 83
483 78
479 75
474 73
467 72
462 72
456 73
450 74
444 76
437 78
430 79
424 80
415 84
410 85
405 87
399 90
393 92
386 95
380 97
374 100
369 102
364 103
359 107
349 112
342 118
337 122
331 125
325 131
320 134
315 138
309 143
305 147
301 150
295 155
290 158
285 161
281 166
277 170
272 174
269 178
265 183
260 187
256 190
253 195
249 200
246 204
241 209
238 213
236 218
234 223
233 228
231 233
231 239
231 246
231 251
231 256
233 263
234 270
235 275
239 284
242 291
245 295
248 300
251 304
255 309
258 313
264 318
272 322
278 325
283 327
288 329
294 331
299 333
305 335
313 337
320 337
326 337
332 337
337 338
342 339
349 340
355 340
360 339
366 339
371 340
376 340
383 341
391 343
397 343
402 345
407 347
412 348
417 349
424 349
430 350
437 353
445 355
450 357
455 361
460 363
466 367
472 370
478 374
483 377
487 380
496 385
501 389
506 393
510 398
514 402
519 409
523 415
527 420
530 425
532 431
535 435
537 440
539 445
540 451
540 456
540 461
540 467
539 476
537 484
535 489
532 493
530 498
527 503
522 509
518 513
515 517
510 522
505 527
498 528
491 531
485 534
477 536
471 539
466 541
458 542
452 543
444 543
438 543
432 543
426 543
420 543
413 543
406 543
399 543
390 543
383 543
374 543
366 544
360 544
351 545
344 545
336 545
327 545
320 545
314 545
306 545
298 546
292 546
280 547
272 548
267 548
258 549
251 550
246 550
238 552
231 553
225 554
218 555
212 556
205 559
199 560
193 564
188 567
179 572
171 574
167 578
161 583
157 588
153 592
150 598
147 602
144 606
141 610
141 615
140 620
139 625
139 631
139 636
140 641
142 646
145 650
148 654
Sub MultiColumnTable_To_Array()
Dim pointList As Variant
Dim rowCount As Integer
Dim result As Variant
Dim epsilon As Double
Call ClearOutput
pointList = Sheets("Sheet1").Range("Table1")
rowCount = UBound(pointList)
epsilon = Sheets("Sheet1").Range("epsilon")
result = DouglasPeucker(pointList, epsilon, rowCount)
WriteResult (result)
End Sub
Function DouglasPeucker(pointList As Variant, epsilon As Double, rowCount As Integer) As Variant
Dim dMax As Double
Dim Index As Integer
Dim d As Double
Dim arrResults1 As Variant
Dim arrResults2 As Variant
Dim resultList As Variant
Dim recResults1 As Variant
Dim recResults2 As Variant
' Find the point with the maximum distance
dMax = 0
Index = 0
For i = 2 To (rowCount)
d = Abs((pointList(rowCount, 1) - pointList(1, 1)) * (pointList(1, 2) - pointList(i, 2)) - (pointList(1, 1) - pointList(i, 1)) * (pointList(rowCount, 2) - pointList(1, 2))) / Sqr((pointList(rowCount, 1) - pointList(1, 1)) ^ 2 + (pointList(rowCount, 2) - pointList(1, 2)) ^ 2)
If d > dMax Then
Index = i
dMax = d
End If
Next i
'Testing if can stop cut going to index 0
If Index > 1 Then
arrResults1 = Cut_Array(pointList, 1, Index)
arrResults2 = Cut_Array(pointList, Index, rowCount)
' If max distance is greater than epsilon, recursively simplify
If (dMax > epsilon) Then
' Recursive call
recResults1 = DouglasPeucker(arrResults1, epsilon, UBound(arrResults1))
recResults2 = DouglasPeucker(arrResults2, epsilon, UBound(arrResults2))
' Build the result list
resultList = Join_Array(recResults1, recResults2)
Else
ReDim resultList(1 To 2, 1 To 2)
resultList(1, 1) = pointList(1, 1)
resultList(1, 2) = pointList(1, 2)
resultList(2, 1) = pointList(rowCount, 1)
resultList(2, 2) = pointList(rowCount, 2)
End If
Else
resultList = pointList
End If
' Return the result
DouglasPeucker = resultList
End Function
Function Cut_Array(arr As Variant, arrStart As Integer, arrEnd As Integer) As Variant
Dim resultList As Variant
ReDim resultList(1 To (arrEnd - arrStart) + 1, 1 To 2)
For i = arrStart To arrEnd
For j = 1 To 2
resultList((i - arrStart) + 1, j) = arr(i, j)
Next j
Next i
Cut_Array = resultList
End Function
Function Join_Array(arr1 As Variant, arr2 As Variant) As Variant
Dim resultList As Variant
Dim arr1Length As Integer
Dim arr2Length As Integer
arr1Length = UBound(arr1) - 1
arr2Length = UBound(arr2)
newArrLength = arr1Length + arr2Length
ReDim resultList(1 To newArrLength, 1 To 2)
For i = 1 To arr1Length
For j = 1 To 2
resultList(i, j) = arr1(i, j)
Next j
Next i
For i = 1 To arr2Length
For j = 1 To 2
resultList(i + arr1Length, j) = arr2(i, j)
Next j
Next i
Join_Array = resultList
End Function
Sub WriteResult(result As Variant)
Dim Table2 As ListObject
Set Table2 = Sheets("Sheet2").ListObjects("Table2")
'Copy information loop
For i = 1 To UBound(result)
For j = 1 To UBound(result, 2)
Table2.Range.Cells(i + 1, j).Value = result(i, j)
Next j
Next i
End Sub
Sub ClearOutput()
Dim OutputTable As ListObject
Dim StartRow As Integer
Set OutputTable = Sheets("Sheet2").ListObjects("Table2")
StartRow = OutputTable.Range.Cells(1, 1).Row + 1
If Not OutputTable.InsertRowRange Is Nothing Then
'Pass
Else
Sheets("Sheet2").Rows(StartRow & ":" & (OutputTable.DataBodyRange.Rows.Count + StartRow)).Delete
End If
End Sub
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment