« previous next »
Pages: 1 [2]  All |   Go Down

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

0 Members and 1 Guest are viewing this topic.

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 »
Logged

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%    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%    81At 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
--------------------------------------------------------------------------------
Logged
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
--------------------------------------------------------------------------------
Logged
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 :-D
Logged

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.     (progn
  11.       (setq maxXpt (assoc (apply 'max (mapcar 'car ptSet)) ptSet))      ;maximum  X value of the points
  12.       (setq sortPt (sort-by-angle-distance ptSet maxXpt))               ;sort the points
  13.       (setq H (list (cadr sortPt) maxXpt))                              ;two points at the beginning
  14.       (foreach n (cddr sortPt)                                          ;start from the third point
  15.         (setq H (cons n H))                                             ;add the point from the sorted point
  16.         (setq P (cadr H))                                               ;the point - next H
  17.         (setq Q (caddr H))                                              ;the point - next H
  18.         (while (and Q (> (det n P Q) -1e-6))                            ;if turn left
  19.           (setq H (cons n (cddr H)))                                    ;delete point H,and get a new one
  20.           (setq P (cadr H))                                             ;new point P
  21.           (setq Q (caddr H))                                            ;new point Q
  22.         )
  23.       )
  24.       (reverse H)                                                       ;retuen the hull
  25.     )
  26.   )
  27. )
  28.  
  29.  
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.            (function
  5.              (lambda (e1 e2 / ang1 ang2 )
  6.                (setq ang1 (angle pt e1))
  7.                (setq ang2 (angle pt e2))
  8.                (if (= ang1 ang2)
  9.                  (< (distance pt e1) (distance pt e2))
  10.                  (< ang1 ang2)
  11.                )
  12.              )
  13.            )
  14.   )
  15. )
  16.  
  17. ;;;The midpoint of a pair of points                                    
  18. (defun mid-pt (p1 p2)
  19.   (list
  20.     (* (+ (car p1) (car p2)) 0.5)
  21.     (* (+ (cadr p1) (cadr p2)) 0.5)
  22.   )
  23. )
  24.  
  25. ;;; DOT product (according to three points)                            
  26. (defun dot (p1 p2 p3 / x1 y1)
  27.   (setq x1 (car p1)
  28.         y1 (cadr p1)
  29.   )
  30.   (+ (* (- (car p2) x1) (- (car p3) x1))
  31.      (* (- (cadr p2) y1) (- (cadr p3) y1))
  32.   )
  33. )
  34.  
  35. ;;; across product (according to three points)                          
  36. (defun det (p1 p2 p3 / x2 y2)
  37.   (setq x2 (car p2)
  38.         y2 (cadr p2)
  39.   )
  40.   (- (* (- x2 (car p3)) (- y2 (cadr p1)))
  41.      (* (- x2 (car p1)) (- y2 (cadr p3)))
  42.   )
  43. )
  44.  

The complete code is in this attachment.
« Last Edit: May 27, 2012, 05:29:54 AM by HighflyingBird »
Logged
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.
Logged
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
--------------------------------------------------------------------------------
Logged
I am a bilingualist,Chinese and Chinglish.

Lee Mac

  • Seagull
  • Posts: 12914
  • 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?
Logged

highflyingbird

  • Bull Frog
  • Posts: 415
  • Later equals never.
Re: ==={challenge}=== Find farthest points
« Reply #23 on: May 28, 2012, 06:52:37 AM »
Quote from: Lee Mac 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?
Yes,I did.
see here
Logged
I am a bilingualist,Chinese and Chinglish.
Pages: 1 [2]  All |   Go Up
« previous next »