Topic: ==={challenge}=== Find farthest points

[Jeremy]

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]

Of course the "brute force" method:

Code - Auto/Visual Lisp: [Select]

1. (defun furthest-points-brute-force  (ptlst /)
2.   (cdar
3.     (vl-sort (apply 'append
4.                (mapcar (function (lambda (p1) (mapcar (function (lambda (p2) (list (distance p1 p2) p1 p2))) ptlst)))
5.                        ptlst))
6.              (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.

[irneb]

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).

[irneb]

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)
16.                                  (min (cadr oldTest) (cadr newTest))
17.                                  (max (cadr oldTest) (cadr newTest))
18.                                  (if (= (cadr newTest) 0.)
19.                                    (last oldTest)
20.                                    (1+ (last oldTest))))
21.                            oldTest
22.                            calclst))))
23.   (princ
24.     (strcat "Testing furthest for " (itoa numTests) " tests on a list of " (itoa len) " length.\n"))
25.   (princ
26.     "Function\tBest%\tWorst%\tFailed\n-------------------------------------------------------------------------------------\n")
27.   (foreach Test calclst
28.     (princ (strcat
29.              (vl-princ-to-string (car Test))
30.              "\t"
31.              (rtos (cadr Test) 2 3)
32.              "%\t"
33.              (rtos (caddr Test) 2 3)
34.              "%\t"
35.              (itoa (fix (last Test)))
36.              "\n")))
37.   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%    30
FURTHEST-POINTS-QUICK    0%    5.827%    30Seems 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>

[irneb]

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))

[pBe]

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

[Lee Mac]

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]

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]

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%    33
FURTHEST-POINTS-QUICK    0%    4.418%    33
LM:GETFURTHESTAPART    0%    0%    0
FARFROMPOINTS    0%    0%    0
FURTHEST-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>

[pBe]

Oh, sorry, yes & my random function:

Code - Auto/Visual Lisp: [Select]

1. (defun Random  (seed /)
2.  ...........  (/ seed 65536))

Very nice Irneb 

[Lee Mac]

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.                     (function
34.                         (lambda ( a b / c d )
35.                             (if (equal (setq c (angle p0 a)) (setq d (angle p0 b)) 1e-8)
36.                                 (< (distance p0 a) (distance p0 b))
37.                                 (< c d)
38.                             )
39.                         )
40.                     )
41.                 )
42.             )
43.             (setq hul (list (caddr lst) (cadr lst) (car lst)))
44.             (foreach pt (cdddr lst)
45.                 (setq hul (cons pt hul))
46.                 (while (and (caddr hul) (LM:Clockwise-p (caddr hul) (cadr hul) pt))
47.                     (setq hul (cons pt (cddr hul)))
48.                 )
49.             )
50.             hul
51.         )
52.     )
53. )
54.  
55. ;; Clockwise-p  -  Lee Mac
56. ;; Returns T if p1,p2,p3 are clockwise oriented or collinear
57.                  
58. (defun LM:Clockwise-p ( p1 p2 p3 )
59.     (<  (-  (* (- (car  p2) (car  p1)) (- (cadr p3) (cadr p1)))
60.             (* (- (cadr p2) (cadr p1)) (- (car  p3) (car  p1)))
61.         )
62.         1e-8
63.     )
64. )
65.  

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]

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. (vl-load-com)
2.  
3. (defun quickbench  (statements / maxinc _printformat _rtodec)
4.   (princ "Benchmarking ")
5.   (setq statements (mapcar '(lambda (statement / inc time start stop)
6.                               (princ ".")
7.                               (setq inc 1 time 0.)
8.                               (while (< time 1000)
9.                                 (setq inc   (* inc 2)
10.                                       start (getvar "MilliSecs"))
11.                                 (repeat (/ inc 2) (eval statement))
12.                                 (setq stop (getvar "MilliSecs"))
13.                                 (setq time (+ time (- stop start))))
14.                               (list statement (/ inc 2) time))
15.                            statements)
16.         maxinc     (cadar statements))
17.   (foreach statement  (cdr statements)
18.     (if (< maxinc (cadr statement))
19.       (setq maxinc (cadr statement))))
20.   (setq statements
21.          (vl-sort (mapcar '(lambda (statement /)
22.                              (append statement (list (* (last statement) (/ maxinc (cadr statement))))))
23.                           statements)
24.                   '(lambda (a b) (< (last a) (last b)))))
25.   (princ (strcat " done for "
26.                  (rtos (float maxinc) 2 0)
27.                  " iterations. Sorted from fastest.\n"
28.                  "Statement                                Increment  Time(ms) Normalize  Relative\n"
29.                  "--------------------------------------------------------------------------------\n"))
30.   (setq maxinc (float (last (last statements))))
31.   (defun _rtodec (val d / p)
32.     (setq val (rtos val 2 d))
33.     (cond ((> d 0)
34.            (if (not (setq p (vl-string-search "." val))) (setq p (strlen val) val (strcat val ".")))
35.            (repeat (- d (- (strlen val) p) -1) (setq val (strcat val "0")))))
36.     val)
37.   (defun _printformat (statement / a v p)
38.     (princ (if (> (strlen (setq a (vl-princ-to-string (car statement)))) 40)
39.              (setq a (strcat (substr a 1 36) "...)"))
40.              a))
41.     (repeat (- 40 (strlen a)) (princ " "))
42.     (setq a (rtos (float (cadr statement)) 2 0))
43.     (repeat (- 10 (strlen a)) (princ " "))
44.     (princ a)
45.     (setq a (rtos (float (caddr statement)) 2 0))
46.     (repeat (- 10 (strlen a)) (princ " "))
47.     (princ a)
48.     (setq a (rtos (setq v (float (last statement))) 2 0))
49.     (repeat (- 10 (strlen a)) (princ " "))
50.     (princ a)
51.     (setq a (_rtodec (/ maxinc v) 2))
52.     (repeat (- 10 (strlen a)) (princ " "))
53.     (princ a)
54.     (princ "\n"))
55.   (foreach statement statements (_printformat statement))
56.   (princ "--------------------------------------------------------------------------------")
57.   (princ))

[irneb]

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 

[irneb]

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%    40
FAST-FARTHEST-PTS    0%    12.77389330283525%    40
FURTHEST-POINTS-QUICK-2    0%    0%    38I.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
--------------------------------------------------------------------------------

[ElpanovEvgeniy]

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. )