;; transpose a list
(defun transpose (lst)
(apply 'mapcar (cons 'list lst))
)
;;sum the elements of a vector
(defun sum (lst)(apply '+ lst))
;;divide a vector by a scalar
(defun sca/ (lst n)(mapcar '(lambda (x)(/ x n)) lst))
;; find the mean of a list of points
(defun pt-amean (pts)
(sca/ (mapcar 'sum (transpose pts))
(length pts)))
;; Given a point and a list of points return the point in the list farthest
;; away from the given point.
(defun farthest-pt (p ptlst)
(cadar (vl-sort
(mapcar '(lambda (x)(list (distance p x) x))
ptlst)
'(lambda (e1 e2)(> (car e1)(car e2)))
)))
;; Given a list of points a list of the two points that are farthest apart from
;; each other is returned. This is a fast algorithm that is not always correct
;; but is correct most of the time.
(defun fast-farthest-pts (ptlst / fp)
(list (setq fp (farthest-pt (pt-amean ptlst) ptlst))
(farthest-pt fp ptlst)))
(defun furthest-points-brute-force2 (ptlst / d pt)
(setq ptlst (apply 'append (mapcar (function (lambda (p1) (mapcar (function (lambda (p2) (list (distance p1 p2) p1 p2))) ptlst))) ptlst))
d 0.)
(foreach p ptlst (if (> (car p) d) (setq d (car p) pt (cdr p))))
pt)
Now it's order N*N*2 instead of N*N*Log(N*N).
Testing furthest for 100 tests on a list of 50 length.
Function Best% Worst% Failed
-------------------------------------------------------------------------------------
FAST-FARTHEST-PTS 0% 5.827% 30
FURTHEST-POINTS-QUICK 0% 5.827% 30
Seems to be the same results for both functions. I've run it several times, found the worst case to be between 0% and 8%, with the number of failures to be between 20 and 45.Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
(FURTHEST-POINTS-QUICK PTLST).....1669 / 2.88 <fastest>
(FAST-FARTHEST-PTS PTLST).........4805 / 1 <slowest>
So using a normal foreach instead of sort is quite a lot faster.Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):
(FURTHEST-POINTS-BRUTE-FORCE PTLST)......1404 / 4.04 <fastest>
(FURTHEST-POINTS-BRUTE-FORCE1 PTLST).....5678 / 1 <slowest>
(Defun farfrompoint (pt pts / p B e)
(while (setq p (car pts))
(if (> (setq B (distance pt p))
(cadr e))
(setq e (list p B)))
(setq pts (cdr pts)))
(car e))
(defun farfrompoints (ptlst / p B e pts)
(foreach pt ptlst
(setq pts ptlst)
(while (setq p (car pts))
(if (> (setq B (distance pt p))
(caddr e))
(setq e (list p pt B)))
(setq pts (cdr pts)))
)
(list (cadr e)(Car e))
)
Mine, still brute-force...
....(< mx (setq ds (distance p1 p2))) (setq mx ds rslt (list p1 p2)))....
As used in this (http://lee-mac.com/autoblockbreak.html).
Testing furthest for 100 tests on a list of 50 length.
Function Best% Worst% Failed
-------------------------------------------------------------------------------------
FAST-FARTHEST-PTS 0% 4.418% 33
FURTHEST-POINTS-QUICK 0% 4.418% 33
LM:GETFURTHESTAPART 0% 0% 0
FARFROMPOINTS 0% 0% 0
FURTHEST-POINTS-BRUTE-FORCE 0% 0% 0
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
(LM:GETFURTHESTAPART PTLST).............3978 / 1.67 <fastest>
(FARFROMPOINTS PTLST)...................5663 / 1.18
(FURTHEST-POINTS-BRUTE-FORCE PTLST).....6662 / 1 <slowest>
Though still a way off the quick estimate method (if you don't mind a possible 10% error):Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
(FURTHEST-POINTS-QUICK PTLST)......1264 / 18.67 <fastest>
(LM:GETFURTHESTAPART PTLST).......11014 / 2.14
(FARFROMPOINTS PTLST).............23603 / 1 <slowest>
Oh, sorry, yes & my random function:Code - Auto/Visual Lisp: [Select]
........... (/ seed 65536))
Benchmarking ....... done for 2048 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PTLST) 2048 1575 1575 112.80
(FAST-FARTHEST-PTS PTLST) 512 1155 4620 38.46
(LM:GETFURTHESTAPART-HULL PTLST) 256 1077 8616 20.62
(LM:GETFURTHESTAPART PTLST) 256 1716 13728 12.94
(FARFROMPOINTS PTLST) 128 1841 29456 6.03
(FURTHEST-POINTS-BRUTE-FORCE PTLST) 64 1451 46432 3.83
(FURTHEST-POINTS-BRUTE-FORCE1 PTLST) 16 1388 177664 1.00
--------------------------------------------------------------------------------
Benchmarking ....... done for 256 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PTLST) 256 1420 1420 1265.58
(FAST-FARTHEST-PTS PTLST) 64 1607 6428 279.58
(LM:GETFURTHESTAPART-HULL PTLST) 32 1622 12976 138.50
(LM:GETFURTHESTAPART PTLST) 4 2200 140800 12.76
(FARFROMPOINTS PTLST) 2 2090 267520 6.72
(FURTHEST-POINTS-BRUTE-FORCE PTLST) 2 2948 377344 4.76
(FURTHEST-POINTS-BRUTE-FORCE1 PTLST) 1 7020 1797120 1.00
--------------------------------------------------------------------------------
So if you simply want to estimate the furthest distance, you can do so 10 times faster than the hull method on 2D lists.Testing furthest for 100 tests on a list of 100 length.
Function Best% Worst% Failed
-------------------------------------------------------------------------------------
FURTHEST-POINTS-QUICK 0% 12.77389330283525% 40
FAST-FARTHEST-PTS 0% 12.77389330283525% 40
FURTHEST-POINTS-QUICK-2 0% 0% 38
I.e. it was accurate to 8 decimal places on distance (though it found slightly wrong points as compared to the brute force method) on 38% of the cases.Benchmarking ..... done for 4096 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 4096 1607 1607 16.93
(FURTHEST-POINTS-QUICK-2 PT2D) 4096 1778 1778 15.30
(FAST-FARTHEST-PTS PT2D) 512 1061 8488 3.20
(LM:GETFURTHESTAPART-HULL PT2D) 1024 2808 11232 2.42
(LM:GETFURTHESTAPART PT2D) 256 1700 27200 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 4096 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 4096 2199 2199 9.20
(FURTHEST-POINTS-QUICK-2 PT2D) 1024 1124 4496 4.50
(FAST-FARTHEST-PTS PT2D) 1024 1217 4868 4.15
(LM:GETFURTHESTAPART-HULL PT2D) 512 1466 11728 1.72
(LM:GETFURTHESTAPART PT2D) 256 1264 20224 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 512 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK-2 PT2D) 256 1138 2276 105.28
(FURTHEST-POINTS-QUICK PT2D) 512 2387 2387 100.38
(FAST-FARTHEST-PTS PT2D) 128 1233 4932 48.58
(LM:GETFURTHESTAPART-HULL PT2D) 32 1404 22464 10.67
(LM:GETFURTHESTAPART PT2D) 4 1872 239616 1.00
--------------------------------------------------------------------------------
Benchmarking .... done for 512 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT3D) 512 2340 2340 96.44
(FURTHEST-POINTS-QUICK-2 PT3D) 256 1420 2840 79.46
(FAST-FARTHEST-PTS PT3D) 64 1217 9736 23.18
(LM:GETFURTHESTAPART PT3D) 4 1763 225664 1.00
--------------------------------------------------------------------------------
Testing furthest for 100 tests on a list of 50 length.
Function Best% Worst% Failed
-------------------------------------------------------------------------------------
EEA-TEST 0% 4.019544548602627% 35
EEA-TEST0 0% 4.019544548602627% 37
FAST-FARTHEST-PTS 0% 3.833381699189351% 70
FURTHEST-POINTS-QUICK 0% 3.833381699189351% 70
FURTHEST-POINTS-QUICK-2 0% 0% 81
At least as to the % error, but yours appears to make an accurate estimate more often. At least with a random list of points. It seems using the average point as base gives a smaller error, but using a edge point as base makes less errors. Perhaps a combination of the 2 would give even greater possibilities.Benchmarking ...... done for 4096 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 4096 1888 1888 9.91
(EEA-TEST PT2D) 4096 1903 1903 9.83
(FURTHEST-POINTS-QUICK-2 PT2D) 2048 1826 3652 5.12
(FAST-FARTHEST-PTS PT2D) 1024 1732 6928 2.70
(LM:GETFURTHESTAPART-HULL PT2D) 512 1544 12352 1.51
(LM:GETFURTHESTAPART PT2D) 256 1169 18704 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 2048 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT3D) 2048 1013 1013 8.98
(EEA-TEST0 PT3D) 2048 1030 1030 8.83
(FURTHEST-POINTS-QUICK-2 PT3D) 2048 1340 1340 6.79
(FAST-FARTHEST-PTS PT3D) 1024 1746 3492 2.60
(LM:GETFURTHESTAPART PT3D) 256 1137 9096 1.00
--------------------------------------------------------------------------------
And for 500 points:Benchmarking ...... done for 512 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(EEA-TEST PT2D) 512 1794 1794 100.25
(FURTHEST-POINTS-QUICK PT2D) 512 1796 1796 100.13
(FURTHEST-POINTS-QUICK-2 PT2D) 512 1843 1843 97.58
(FAST-FARTHEST-PTS PT2D) 64 1279 10232 17.58
(LM:GETFURTHESTAPART-HULL PT2D) 32 1123 17968 10.01
(LM:GETFURTHESTAPART PT2D) 4 1405 179840 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 512 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK-2 PT3D) 512 1824 1824 101.75
(EEA-TEST0 PT3D) 512 1856 1856 100.00
(FURTHEST-POINTS-QUICK PT3D) 512 1856 1856 100.00
(FAST-FARTHEST-PTS PT3D) 64 1294 10352 17.93
(LM:GETFURTHESTAPART PT3D) 4 1450 185600 1.00
--------------------------------------------------------------------------------
Benchmarking ...... done for 1024 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 1024 1965 1965 96.47
(FURTHEST-POINTS-QUICK-2 PT2D) 512 1030 2060 92.02
(EEA-TEST PT2D) 512 1512 3024 62.69
(FAST-FARTHEST-PTS PT2D) 64 1450 23200 8.17
(LM:GETFURTHESTAPART-HULL PT2D) 64 1871 29936 6.33
(LM:GETFURTHESTAPART PT2D) 8 1481 189568 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 1024 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK-2 PT3D) 1024 1935 1935 91.95
(FURTHEST-POINTS-QUICK PT3D) 1024 1964 1964 90.59
(EEA-TEST0 PT3D) 512 1418 2836 62.74
(FAST-FARTHEST-PTS PT3D) 64 1404 22464 7.92
(LM:GETFURTHESTAPART PT3D) 8 1390 177920 1.00
--------------------------------------------------------------------------------
Benchmarking ...... done for 2048 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 2048 1763 1763 90.68
(FURTHEST-POINTS-QUICK-2 PT2D) 2048 2807 2807 56.95
(EEA-TEST PT2D) 512 1077 4308 37.11
(FAST-FARTHEST-PTS PT2D) 128 1263 20208 7.91
(LM:GETFURTHESTAPART-HULL PT2D) 128 1498 23968 6.67
(LM:GETFURTHESTAPART PT2D) 16 1249 159872 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 2048 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK-2 PT3D) 2048 1748 1748 90.22
(FURTHEST-POINTS-QUICK PT3D) 2048 1778 1778 88.69
(EEA-TEST0 PT3D) 1024 1280 2560 61.60
(FAST-FARTHEST-PTS PT3D) 128 1294 20704 7.62
(LM:GETFURTHESTAPART PT3D) 16 1232 157696 1.00
--------------------------------------------------------------------------------
Benchmarking ...... done for 1024 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT2D) 1024 1155 1155 75.19
(FURTHEST-POINTS-QUICK-2 PT2D) 1024 1186 1186 73.23
(EEA-TEST PT2D) 1024 1560 1560 55.67
(LM:GETFURTHESTAPART-HULL PT2D) 64 1044 16704 5.20
(FAST-FARTHEST-PTS PT2D) 64 1419 22704 3.83
(LM:GETFURTHESTAPART PT2D) 16 1357 86848 1.00
--------------------------------------------------------------------------------
Benchmarking ..... done for 1024 iterations. Sorted from fastest.
Statement Increment Time(ms) Normalize Relative
--------------------------------------------------------------------------------
(FURTHEST-POINTS-QUICK PT3D) 1024 1249 1249 75.94
(FURTHEST-POINTS-QUICK-2 PT3D) 1024 1325 1325 71.58
(EEA-TEST0 PT3D) 1024 1716 1716 55.27
(FAST-FARTHEST-PTS PT3D) 64 1419 22704 4.18
(LM:GETFURTHESTAPART PT3D) 16 1482 94848 1.00
--------------------------------------------------------------------------------
Impressive Highflyingbird :-)Yes,I did.
I haven't studied your method in detail, but I assume you used the rotating calipers method?