Last active
June 10, 2019 23:52
-
-
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".
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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