### Author Topic: ==={challenge}=== Find farthest points  (Read 9017 times)

0 Members and 1 Guest are viewing this topic.

#### Jeremy

• Guest
##### ==={challenge}=== Find farthest points
« on: May 03, 2012, 10:03:09 PM »
Todays challenge children is when given a list of points to write a program that will return a list of the two points in the list that are farthest apart. My entry is a function called fast-farthest-pts. This algorithm represents an attempt at a fast algorithm that is designed to get very close very fast but not necessarily get the true answer. It works as follows:

1. Calculate the arithmetic mean of all the points and call that apt.
2. Find the point farthest from apt and call that fp1.
3. Find the point farthest from fp1 and call that fp2.
4. Return a list of fp1 and fp2.

Simple eh? I did test runs of a 100 with sets of 50 random points at a time and found that it could disagree with the correct answer as much as 74% of the runs or as little as 2%. That doesn't sound very reliable until you check the distances found. The greatest deviation from the true distance was only 1.8%! I also tried finding the centroid of the points rather than the average but the distance error rate crept up to 5%. So what is your ingenious solution going to be?

Code: [Select]
`;; 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)))`

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #1 on: May 04, 2012, 04:26:55 AM »
Of course the "brute force" method:
Code - Auto/Visual Lisp: [Select]
1. (defun furthest-points-brute-force  (ptlst /)
2.   (cdar
3.                (mapcar (function (lambda (p1) (mapcar (function (lambda (p2) (list (distance p1 p2) p1 p2))) ptlst)))
4.                        ptlst))
5.              (function (lambda (a b) (> (car a) (car b)))))))

But I'm guessing you're wanting only the fastest possible, not an order N*N function like above - although it would give the "correct" result. In that case, why do you use sorting? Isn't that an order N*Log(n) algorithm? A simple foreach with a state variable for last furthest point & last greatest distance would be an order N search.
Code - Auto/Visual Lisp: [Select]
1. (defun furthest-points-quick (ptlst / len pA p1 p2 d d1)
2.   (setq len (length ptlst)
3.         pA (mapcar (function (lambda (a) (/ a len)))
4.                    (apply 'mapcar (cons '+ ptlst))))
5.   (setq p1 (car ptlst) d (distance p1 pA))
6.   (foreach p ptlst (if (> (setq d1 (distance p pA)) d) (setq d d1 p1 p)))
7.   (setq p2 (car ptlst) d (distance p1 pA))
8.   (foreach p ptlst (if (> (setq d1 (distance p p1)) d) (setq d d1 p2 p)))
9.   (list p1 p2))
Perhaps do it 3 times, i.e. mean pt -> furthest1 from mean -> furthest2 from furthest1 -> furthest3 from furthest2.

But I can still see some strange point cloud shapes which would produce slightly erroneous results.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #2 on: May 04, 2012, 04:42:01 AM »
Actually "slightly" quicker brute force (well theoretically):
Code: [Select]
`(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).
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #3 on: May 04, 2012, 06:09:49 AM »
OK, here's some testing functions:

First the accuracy test:
Code - Auto/Visual Lisp: [Select]
1. (defun furthest-points-test  (len funclst / ptlst base val calclst)
2.   (repeat len
3.     (setq ptlst (cons (list (* 1000. (random nil)) (* 1000. (random nil)) (* 1000. (random nil))) ptlst)))
4.   (setq base (apply 'distance (furthest-points-brute-force ptlst)))
5.   (foreach func  funclst
6.     (setq val     ((eval func) ptlst)
7.           calclst (cons (list func (/ (abs (- base (apply 'distance val))) base 0.01)) calclst)))
8.   calclst)
9.
10. (defun furthest-points-test-multiple  (numTests len funclst / calclst oldTest)
11.   (setq calclst (mapcar '(lambda (lst) (list (car lst) (cadr lst) (cadr lst) (if (= (cadr lst) 0.) 0 1))) (furthest-points-test len funclst)))
12.   (repeat (1- numTests)
13.     (foreach newTest  (furthest-points-test len funclst)
14.       (setq oldTest (assoc (car newTest) calclst)
15.             calclst (subst (list (car newTest)
18.                                  (if (= (cadr newTest) 0.)
19.                                    (last oldTest)
20.                                    (1+ (last oldTest))))
21.                            oldTest
22.                            calclst))))
23.     (strcat "Testing furthest for " (itoa numTests) " tests on a list of " (itoa len) " length.\n"))
24.     "Function\tBest%\tWorst%\tFailed\n-------------------------------------------------------------------------------------\n")
25.   (foreach Test calclst
26.              (vl-princ-to-string (car Test))
27.              "\t"
28.              (rtos (cadr Test) 2 3)
29.              "%\t"
30.              (rtos (caddr Test) 2 3)
31.              "%\t"
32.              (itoa (fix (last Test)))
33.              "\n")))
34.   calclst)
Result thus far:
Code: [Select]
`Testing furthest for 100 tests on a list of 50 length.Function    Best%    Worst%    Failed-------------------------------------------------------------------------------------FAST-FARTHEST-PTS    0%    5.827%    30FURTHEST-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.

Finally the speed benchmark:
Code: [Select]
`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.

Even more pronounced on the brute-force methods (I've renamed the sorting brute-force to furthest-points-brute-force1 and the foreach brute-force to furthest-points-brute-force - since I'm using it in the accuracy test):
Code: [Select]
`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>`
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #4 on: May 04, 2012, 06:11:49 AM »
Oh, sorry, yes & my random function:
Code - Auto/Visual Lisp: [Select]
1. (defun Random  (seed /)
2.   (if (not seed)
3.     (setq seed (if *random:seed*
4.                  *random:seed*
5.                  (setq *random:seed* (getvar "DATE"))))
6.     (setq *random:seed* seed))
7.   (setq seed          (rem (+ (* 25173 seed) 13849) 65536)
8.         *random:seed* seed)
9.   (/ seed 65536))
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### pBe

• Bull Frog
• Posts: 402
##### Re: ==={challenge}=== Find farthest points
« Reply #5 on: May 04, 2012, 06:57:45 AM »
Farthest from given point:

Code: [Select]
`(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))`
Two points
Code: [Select]
`(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))      )`
Remove varialbe total
« Last Edit: May 04, 2012, 09:01:23 AM by pBe »

#### Lee Mac

• Seagull
• Posts: 12892
• London, England
##### Re: ==={challenge}=== Find farthest points
« Reply #6 on: May 04, 2012, 07:35:03 AM »
Mine, still brute-force...

Code - Auto/Visual Lisp: [Select]
1. (defun LM:GetFurthestApart ( lst / mx p1 p2 ds rslt )
2.     (setq mx 0.0)
3.     (while (setq p1 (car lst))
4.         (foreach p2 (setq lst (cdr lst))
5.             (if (< mx (setq ds (distance p1 p2))) (setq mx ds rslt (list p1 p2)))
6.         )
7.     )
8.     rslt
9. )

As used in this.

#### pBe

• Bull Frog
• Posts: 402
##### Re: ==={challenge}=== Find farthest points
« Reply #7 on: May 04, 2012, 08:33:20 AM »
Mine, still brute-force...

....(< mx (setq ds (distance p1 p2))) (setq mx ds rslt (list p1 p2)))....

As used in this.

But of course... :facepalm:
I made mine too complicated

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #8 on: May 04, 2012, 10:08:48 AM »
At least they give 100% correct results.
Code: [Select]
`Testing furthest for 100 tests on a list of 50 length.Function    Best%    Worst%    Failed-------------------------------------------------------------------------------------FAST-FARTHEST-PTS    0%    4.418%    33FURTHEST-POINTS-QUICK    0%    4.418%    33LM:GETFURTHESTAPART    0%    0%    0FARFROMPOINTS    0%    0%    0FURTHEST-POINTS-BRUTE-FORCE    0%    0%    0`
As for speed, they're the fastest brute force methods yet:
Code: [Select]
`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):
Code: [Select]
`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>`
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### pBe

• Bull Frog
• Posts: 402
##### Re: ==={challenge}=== Find farthest points
« Reply #9 on: May 04, 2012, 11:41:41 AM »
Oh, sorry, yes & my random function:
Code - Auto/Visual Lisp: [Select]
1. (defun Random  (seed /)
2.  ...........  (/ seed 65536))

Very nice Irneb

#### Lee Mac

• Seagull
• Posts: 12892
• London, England
##### Re: ==={challenge}=== Find farthest points
« Reply #10 on: May 04, 2012, 11:49:54 AM »
Here is a much faster method eliminating many of the candidate points using the Convex Hull of the set, although this method is restricted to a 2D point set.

Convex Hull function from here, implementing Graham Scan algorithm.

Code - Auto/Visual Lisp: [Select]
1. (defun LM:GetFurthestApart-Hull ( lst / mx p1 p2 ds rslt )
2.     (setq mx 0.0
3.           lst (LM:ConvexHull lst)
4.     )
5.     (while (setq p1 (car lst))
6.        (foreach p2 (setq lst (cdr lst))
7.            (if (< mx (setq ds (distance p1 p2))) (setq mx ds rslt (list p1 p2)))
8.        )
9.    )
10.    rslt
11. )
12.
13. ;; Convex Hull  -  Lee Mac
14. ;; Implements the Graham Scan Algorithm to return the
15. ;; Convex Hull of a list of points.
16.
17. (defun LM:ConvexHull ( lst / hul p0 )
18.     (cond
19.         (   (< (length lst) 4)
20.             lst
21.         )
22.         (   t
23.             (setq p0 (car lst))
24.             (foreach p1 (cdr lst)
25.                 (if (or (< (cadr p1) (cadr p0))
26.                         (and (equal (cadr p1) (cadr p0) 1e-8) (< (car p1) (car p0)))
27.                     )
28.                     (setq p0 p1)
29.                 )
30.             )
31.             (setq lst
32.                 (vl-sort lst
33.                         (lambda ( a b / c d )
34.                             (if (equal (setq c (angle p0 a)) (setq d (angle p0 b)) 1e-8)
35.                                 (< (distance p0 a) (distance p0 b))
36.                                 (< c d)
37.                             )
38.                         )
39.                     )
40.                 )
41.             )
42.             (setq hul (list (caddr lst) (cadr lst) (car lst)))
43.             (foreach pt (cdddr lst)
44.                 (setq hul (cons pt hul))
45.                 (while (and (caddr hul) (LM:Clockwise-p (caddr hul) (cadr hul) pt))
46.                     (setq hul (cons pt (cddr hul)))
47.                 )
48.             )
49.             hul
50.         )
51.     )
52. )
53.
54. ;; Clockwise-p  -  Lee Mac
55. ;; Returns T if p1,p2,p3 are clockwise oriented or collinear
56.
57. (defun LM:Clockwise-p ( p1 p2 p3 )
58.     (<  (-  (* (- (car  p2) (car  p1)) (- (cadr p3) (cadr p1)))
59.             (* (- (cadr p2) (cadr p1)) (- (car  p3) (car  p1)))
60.         )
61.         1e-8
62.     )
63. )
64.

My test function:

Code - Auto/Visual Lisp: [Select]
1. (defun c:test ( / _rand l )
2.
3.     (defun _rand ( / mod )
4.         (/ (setq mod 4294967296.0 seed (rem (1+ (* 1664525.0 (cond (seed) ((getvar 'DATE))))) mod)) mod)
5.     )
6.     (repeat 500
7.         (setq l (cons (list (* 1000.0 (_rand)) (* 1000.0 (_rand)) 0.0) l))
8.     )
9.     (Benchmark '((LM:GetFurthestApart-Hull l) (LM:GetFurthestApart l)))
10.     (princ)
11. )

Results for set of 100 points:

Code - Auto/Visual Lisp: [Select]
1. Elapsed milliseconds / relative speed for 512 iteration(s):
2.
3.     (LM:GETFURTHESTAPART-HULL L).....1435 / 2.73 <fastest>
4.     (LM:GETFURTHESTAPART L)..........3916 / 1 <slowest>

Results for set of 500 points:

Code - Auto/Visual Lisp: [Select]
1. Elapsed milliseconds / relative speed for 64 iteration(s):
2.
3.     (LM:GETFURTHESTAPART-HULL L)......1045 / 11.54 <fastest>
4.     (LM:GETFURTHESTAPART L)..........12059 / 1 <slowest>

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #11 on: May 05, 2012, 04:24:58 AM »
Great, that's the fastest producing 100% accurate results. On 2D list of 50 points:
Code: [Select]
`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--------------------------------------------------------------------------------`
On 2d list of 500 points:
Code: [Select]
`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.

BTW, I've re-implemented the benchmarking routine to not take ages when there's one or more statements just taking a huge amount of time:
Code - Auto/Visual Lisp: [Select]
1.
2. (defun quickbench  (statements / maxinc _printformat _rtodec)
3.   (princ "Benchmarking ")
4.   (setq statements (mapcar '(lambda (statement / inc time start stop)
5.                               (princ ".")
6.                               (setq inc 1 time 0.)
7.                               (while (< time 1000)
8.                                 (setq inc   (* inc 2)
9.                                       start (getvar "MilliSecs"))
10.                                 (repeat (/ inc 2) (eval statement))
11.                                 (setq stop (getvar "MilliSecs"))
12.                                 (setq time (+ time (- stop start))))
13.                               (list statement (/ inc 2) time))
14.                            statements)
15.         maxinc     (cadar statements))
16.   (foreach statement  (cdr statements)
17.     (if (< maxinc (cadr statement))
18.       (setq maxinc (cadr statement))))
19.   (setq statements
20.          (vl-sort (mapcar '(lambda (statement /)
21.                              (append statement (list (* (last statement) (/ maxinc (cadr statement))))))
22.                           statements)
23.                   '(lambda (a b) (< (last a) (last b)))))
24.   (princ (strcat " done for "
25.                  (rtos (float maxinc) 2 0)
26.                  " iterations. Sorted from fastest.\n"
27.                  "Statement                                Increment  Time(ms) Normalize  Relative\n"
28.                  "--------------------------------------------------------------------------------\n"))
29.   (setq maxinc (float (last (last statements))))
30.   (defun _rtodec (val d / p)
31.     (setq val (rtos val 2 d))
32.     (cond ((> d 0)
33.            (if (not (setq p (vl-string-search "." val))) (setq p (strlen val) val (strcat val ".")))
34.            (repeat (- d (- (strlen val) p) -1) (setq val (strcat val "0")))))
35.     val)
36.   (defun _printformat (statement / a v p)
37.     (princ (if (> (strlen (setq a (vl-princ-to-string (car statement)))) 40)
38.              (setq a (strcat (substr a 1 36) "...)"))
39.              a))
40.     (repeat (- 40 (strlen a)) (princ " "))
41.     (setq a (rtos (float (cadr statement)) 2 0))
42.     (repeat (- 10 (strlen a)) (princ " "))
43.     (princ a)
44.     (setq a (rtos (float (caddr statement)) 2 0))
45.     (repeat (- 10 (strlen a)) (princ " "))
46.     (princ a)
47.     (setq a (rtos (setq v (float (last statement))) 2 0))
48.     (repeat (- 10 (strlen a)) (princ " "))
49.     (princ a)
50.     (setq a (_rtodec (/ maxinc v) 2))
51.     (repeat (- 10 (strlen a)) (princ " "))
52.     (princ a)
53.     (princ "\n"))
54.   (foreach statement statements (_printformat statement))
55.   (princ "--------------------------------------------------------------------------------")
56.   (princ))
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #12 on: May 05, 2012, 04:34:36 AM »
Now I'm wondering if implementing a 3D convex hull would help much: http://www.cse.unsw.edu.au/~lambert/java/3d/incremental.html

I'm thinking for huge amounts of points there might be a benefit. But the overhead of calculating facet normals and seeing if a point is outside / inside the temporary hull might take away quite a lot efficiency. Not to mention those 3D calcs give me headaches
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #13 on: May 05, 2012, 07:56:55 AM »
Ok, tried another "trick" to get the estimation function closer to the truth:
Code - Auto/Visual Lisp: [Select]
1. (defun furthest-point-from (ptlst pt / len dist ptF distT)
2.   (setq len (length ptlst) dist (distance (setq ptF (car ptlst)) pt))
3.   (foreach ptT (cdr ptlst) (if (> (setq distT (distance ptT pt)) dist) (setq dist distT ptF ptT)))
4.   ptF)
5.
6. (defun average-point (ptlst / len)
7.   (setq len (length ptlst))
8.   (mapcar (function (lambda (a) (/ a len))) (apply 'mapcar (cons '+ ptlst))))
9.
10. (defun furthest-~-points (ptlst pt variance / dist result)
11.   (setq dist (distance (furthest-point-from ptlst pt) pt)
12.         dist (- dist (* dist variance)))
13.   (foreach ptT ptlst (if (> (distance ptT pt) dist) (setq result (cons ptT result))))
14.   result)
15.
16. (defun furthest-points-quick-2 (ptlst / variance %pts d pA pB d2)
17.   (setq variance (/ 0.1 (/ (length ptlst) 100.)))
18.   (cond ((< (length ptlst) 3) ptlst)
19.         ((= (length (setq %pts (furthest-~-points ptlst (average-point ptlst) variance))) 1) (cons (furthest-point-from ptlst (car %pts)) %pts))
20.         ((= (length %pts) 2) %pts)
21.         (t
22.          (setq d -1.)
23.          (foreach p1 %pts (foreach p2 %pts (if (> (setq d2 (distance p1 p2)) d) (setq d d2 pA p1 pB p2))))
24.          (list pA pB))))
Testing the accuracy it seems to work fine for all the tests I've done (using LM:GetFurthestApart as test function). Here's one of the worst cases I could get at:
Code: [Select]
`Testing furthest for 100 tests on a list of 100 length.Function    Best%    Worst%    Failed-------------------------------------------------------------------------------------FURTHEST-POINTS-QUICK    0%    12.77389330283525%    40FAST-FARTHEST-PTS    0%    12.77389330283525%    40FURTHEST-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.

Best of all, it's still quite fast, on 50 points:
Code: [Select]
`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--------------------------------------------------------------------------------`
On 500 points:
Code: [Select]
`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--------------------------------------------------------------------------------`
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1569
• Moscow (Russia)
##### Re: ==={challenge}=== Find farthest points
« Reply #14 on: May 05, 2012, 10:11:00 AM »
my variant:
Code - Auto/Visual Lisp: [Select]
1. (defun eea-f (l p / D P1)
2.   (while l
3.     (if (< d (distance p (car l)))
4.       (setq p1 (car l)
5.             d  (distance p (car l))
6.             l  (cdr l)
7.       )
8.       (setq l (cdr l))
9.     )
10.   )
11.   (list p1 p)
12. )
13. (defun eea-test (l)
14.   (eea-f l
15.          (car (eea-f l
16.                      ((lambda (a b) (list (/ (+ (car a) (car b)) 2) (/ (+ (cadr a) (cadr b)) 2)))
17.                        (apply (function mapcar) (cons (function min) l))
18.                        (apply (function mapcar) (cons (function max) l))
19.                      )
20.               )
21.          )
22.   )
23. )

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1569
• Moscow (Russia)
##### Re: ==={challenge}=== Find farthest points
« Reply #15 on: May 05, 2012, 10:21:07 AM »
variant 2 - delete Z:
Code - Auto/Visual Lisp: [Select]
1. (defun eea-f (l p / D P1)
2.   (while l
3.     (if (< d (distance p (car l)))
4.       (setq p1 (car l)
5.             d  (distance p (car l))
6.             l  (cdr l)
7.       )
8.       (setq l (cdr l))
9.     )
10.   )
11.   (list p1 p)
12. )
13. (defun eea-test (l)
14.   (eea-f (setq l (cons (list (caar l) (cadar l)) (cdr l)))
15.          (car (eea-f l
16.                      ((lambda (a b) (list (/ (+ (car a) (car b)) 2) (/ (+ (cadr a) (cadr b)) 2)))
17.                        (apply (function mapcar) (cons (function min) l))
18.                        (apply (function mapcar) (cons (function max) l))
19.                      )
20.               )
21.          )
22.   )
23. )
« Last Edit: May 05, 2012, 10:48:06 AM by ElpanovEvgeniy »

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #16 on: May 06, 2012, 11:05:44 AM »
Nice, though it seems your codes are slightly more inaccurate than Jeremy's and mine.
Code: [Select]
`Testing furthest for 100 tests on a list of 50 length.Function    Best%    Worst%    Failed-------------------------------------------------------------------------------------EEA-TEST    0%    4.019544548602627%    35EEA-TEST0    0%    4.019544548602627%    37FAST-FARTHEST-PTS    0%    3.833381699189351%    70FURTHEST-POINTS-QUICK    0%    3.833381699189351%    70FURTHEST-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.

The speed is very close to the same speed as my original "quick" version. For 50 points:
Code: [Select]
`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:
Code: [Select]
`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--------------------------------------------------------------------------------`
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### irneb

• Water Moccasin
• Posts: 1794
• ACad R9-2016, Revit Arch 6-2016
##### Re: ==={challenge}=== Find farthest points
« Reply #17 on: May 06, 2012, 11:26:59 AM »
Performing a compile also helps quite a lot, especially on mine since they use foreach (which is much better when compiled).

Standard compiled on 500 points:
Code: [Select]
`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--------------------------------------------------------------------------------`
LSM compiled:
Code: [Select]
`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--------------------------------------------------------------------------------`
LSA compiled:
Code: [Select]
`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--------------------------------------------------------------------------------`
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

#### Jeremy

• Guest
##### Re: ==={challenge}=== Find farthest points
« Reply #18 on: May 06, 2012, 03:19:04 PM »
Here is another thought for a possible fast approximation:

1. Calculate the arithmetic mean of the points and call it cp.
2. Order the points by their angle relative to cp as the origin.
3. Iterate through the points and find the point that is closest to 180 deg away from the point under consideration.
4. Find the distance between the points and if it is greater than the previous pair then set those points as the new best choice.
5. Run through half the list that way and return the result.

This algorithm would eliminate two points with every iteration and exploits the general observation that the farthest points are probably going to be fairly opposite the arithmetic mean point. Guess I better figure it out

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: ==={challenge}=== Find farthest points
« Reply #19 on: May 27, 2012, 04:48:43 AM »
here is my code:
Code - Auto/Visual Lisp: [Select]
1. ;;;====================================================================
2. ;;;Function : Find the farthest points from a list of points
3. ;;;Arguments : A CCW HULL
4. ;;;Return: the farthest points and its distance
5. ;;;====================================================================
6. (defun Max-distance (H / D M MAXD P PAIR Q U V W)
7.   (setq Q (cdr (append H H (list (car H)))))                            ;to construct a cycling from the hull
8.   (setq MaxD 0.0)                                                       ;set the maximum distance as zero
9.   (foreach U H                                                          ;foreach every side of hull
10.     (setq V (car Q))                                                    ;1st point of the cycling
11.     (setq W (cadr Q))                                                   ;2nd point of the cycling
12.     (setq M (mid-pt V W))                                               ;the midpoint of these two points
13.     (while (> (dot M U V) 0.0)                                          ;if the angle between them is less than 90 degrees
14.       (setq Q (cdr Q))                                                  ;then push points
15.       (setq V (car Q))                                                  ;get the next points
16.       (setq W (cadr Q))                                                 ;the next next points
17.       (setq M (mid-pt V W))                                             ;the midpoint of these two points
18.     )
19.     (setq D (distance U V))                                             ;the distance after "while"
20.     (if (> D MaxD)                                                      ;if it is greater than the previous distance
21.       (setq MaxD D                                                      ;then substitute the distance
22.             Pair (list U V)                                             ;and its points
23.       )
24.     )
25.   )
26.   (cons Pair MaxD)                                                      ;return the farthest points and its distance
27. )
28.

for Graham Scan:
Code - Auto/Visual Lisp: [Select]
1. ;;;=====================================================================
2. ;;;Convex Hull  -  HighflyingBird
3. ;;;Function : Find the hull form a list of points
4. ;;;Algorithm: Graham Scan
5. ;;;Return : Convex Hull of a list of points.
6. ;;;=====================================================================
7. (defun Graham-scan (ptSet / H maxXpt sortPt P Q)
8.   (if (< (length ptSet) 3)                                              ;3 points
9.     ptSet                                                               ;return itself
10.       (setq maxXpt (assoc (apply 'max (mapcar 'car ptSet)) ptSet))      ;maximum  X value of the points
11.       (setq sortPt (sort-by-angle-distance ptSet maxXpt))               ;sort the points
12.       (setq H (list (cadr sortPt) maxXpt))                              ;two points at the beginning
13.       (foreach n (cddr sortPt)                                          ;start from the third point
14.         (setq H (cons n H))                                             ;add the point from the sorted point
15.         (setq P (cadr H))                                               ;the point - next H
16.         (setq Q (caddr H))                                              ;the point - next H
17.         (while (and Q (> (det n P Q) -1e-6))                            ;if turn left
18.           (setq H (cons n (cddr H)))                                    ;delete point H,and get a new one
19.           (setq P (cadr H))                                             ;new point P
20.           (setq Q (caddr H))                                            ;new point Q
21.         )
22.       )
23.       (reverse H)                                                       ;retuen the hull
24.     )
25.   )
26. )
27.
28.
other code:
Code - Auto/Visual Lisp: [Select]
1. ;;;sort the point set according to angle and distance from a basepoint.
2. (defun sort-by-angle-distance (ptlist pt / )
3.   (vl-sort ptlist
4.              (lambda (e1 e2 / ang1 ang2 )
5.                (setq ang1 (angle pt e1))
6.                (setq ang2 (angle pt e2))
7.                (if (= ang1 ang2)
8.                  (< (distance pt e1) (distance pt e2))
9.                  (< ang1 ang2)
10.                )
11.              )
12.            )
13.   )
14. )
15.
16. ;;;The midpoint of a pair of points
17. (defun mid-pt (p1 p2)
18.   (list
19.     (* (+ (car p1) (car p2)) 0.5)
20.     (* (+ (cadr p1) (cadr p2)) 0.5)
21.   )
22. )
23.
24. ;;; DOT product (according to three points)
25. (defun dot (p1 p2 p3 / x1 y1)
26.   (setq x1 (car p1)
27.         y1 (cadr p1)
28.   )
29.   (+ (* (- (car p2) x1) (- (car p3) x1))
30.      (* (- (cadr p2) y1) (- (cadr p3) y1))
31.   )
32. )
33.
34. ;;; across product (according to three points)
35. (defun det (p1 p2 p3 / x2 y2)
36.   (setq x2 (car p2)
37.         y2 (cadr p2)
38.   )
39.   (- (* (- x2 (car p3)) (- y2 (cadr p1)))
40.      (* (- x2 (car p1)) (- y2 (cadr p3)))
41.   )
42. )
43.

The complete code is in this attachment.
« Last Edit: May 27, 2012, 05:29:54 AM by HighflyingBird »
I am a bilingualist,Chinese and Chinglish.

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: ==={challenge}=== Find farthest points
« Reply #20 on: May 27, 2012, 05:00:42 AM »
it maybe  take a very long time if  use "brute force" method:
especially  in this case:
all  the points are on a curve (e.g, a circle or a spline) and the number of points is very huge.
I am a bilingualist,Chinese and Chinglish.

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: ==={challenge}=== Find farthest points
« Reply #21 on: May 27, 2012, 07:12:43 PM »
This is a test on my old machine,just for Lee-mac's and mine. I didn't test others.

Benchmarking . done for 1 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(MAX-DISTANCE (GRAHAM-SCAN PTSET))               1      1125      1125      1.00
--------------------------------------------------------------------------------
Benchmarking . done for 1 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(LM:GETFURTHESTAPART-HULL PTSET)                 1    279344     279344      1.00
--------------------------------------------------------------------------------
I am a bilingualist,Chinese and Chinglish.

#### Lee Mac

• Seagull
• Posts: 12892
• London, England
##### Re: ==={challenge}=== Find farthest points
« Reply #22 on: May 28, 2012, 06:30:34 AM »
Impressive Highflyingbird

I haven't studied your method in detail, but I assume you used the rotating calipers method?

#### highflyingbird

• Bull Frog
• Posts: 415
• Later equals never.
##### Re: ==={challenge}=== Find farthest points
« Reply #23 on: May 28, 2012, 06:52:37 AM »
Impressive Highflyingbird

I haven't studied your method in detail, but I assume you used the rotating calipers method?
Yes,I did.
see here
I am a bilingualist,Chinese and Chinglish.