### Author Topic: General Hill Climbing Wrapper Function  (Read 275 times)

0 Members and 1 Guest are viewing this topic.

#### Rod

• Newt
• Posts: 180 ##### General Hill Climbing Wrapper Function
« on: March 17, 2022, 09:07:10 PM »
I have seen the hill-climbing approach used in this forum and I think its a good approach for a lot of code I write.
I thought it would be good to write wrapper recursive functions for linear, 2d and 3d hill climbing that look for the best approximate result.

Example linear wrapper function that would would find the approximate nearest point on a pollyine would take these arguments,

a function that results in a number value eg. '(lambda (dist) (distance pt (vlax-curve-getPointAtDist en dist)))
a sorting function '< (looking for the lowest value or shortest distance)
a maximum number of repetitions 50
and a minimum tolerance/ error value 0.01
min search value 0
max search value (vlax-curve-getdistatparam en (vlax-curve-getendparam en))

The wrapper would then try different distances along the polyline looking for the one with the lowest value (closest point) and then recursively try new points close to the nearest point found until the maximum number of repetitions have been reach, or our search distance is less than the minimum tolerance/ error value.
The result would be the distance along the polyine to the closest point.

I hope my idea is clear.

Cheers, Rod.

« Last Edit: March 17, 2022, 10:30:03 PM by Rod »
"All models are wrong, some models are useful" - George Box

#### BIGAL

• Swamp Rat
• Posts: 951
• 40 + years of using Autocad ##### Re: General Hill Climbing Algorithim
« Reply #1 on: March 17, 2022, 09:20:11 PM »
As clear as the mud from the floods here.

Post an image or dwg explaining your sort of contradicting yourself in what you ask for, just find closest pt from a selected group of points to a pline ?

#### Rod

• Newt
• Posts: 180 ##### Re: General Hill Climbing Algorithim
« Reply #2 on: March 17, 2022, 10:27:16 PM »
*EDIT - BIGAL hope you are alright, some people have really copped a tough time with the floods

I'm not looking for an individual task more how would you write the wrapper function.

The wrapper function searches for the value that gives the best (lowest or highest or whatever) then recursively improves on the best found answer until a suitable answer is found.
https://en.wikipedia.org/wiki/Hill_climbing

This technique is used on many approximation tasks eg.
Linear search
min dist
closest point to
min bounding box

2d search
largest inscribed circle
minimum circumscribed circle

Here is my quick and dirty version and an example of a minDist command that uses the wrapper function.

Code - Auto/Visual Lisp: [Select]
1. (defun evenlyDivide (minNo maxNo div / spacing lst item)
2.   ;;div cannot be less than or equal to 1
3.   (setq spacing (/ (- maxNo minNo) (float (- div 1))))
4.   (setq lst (list (float minNo)))
5.   (setq item minNo)
6.   (repeat (- div 1)
7.     (setq item (+ item spacing))
8.     (setq lst (cons item lst))
9.   ) ;_ end of repeat
10.   (reverse lst)
11. ) ;_ end of defun
12.
13. (defun getBestResult (func lst comp / results bestResult)
14.   (setq results (mapcar func lst))
15.   (setq bestResult (car results))
16.   (foreach result (cdr results)
17.     (if (apply comp (list result bestResult))
18.       (setq bestResult result)
19.     ) ;_ end of if
20.   ) ;_ end of foreach
21.   (nth (vl-position bestResult results) lst)
22. ) ;_ end of defun
23.
24. (defun linearSearch (func comp maxRep minS maxS error curRep div / spacing lst bestResult)
25.   (setq spacing (/ (- maxS minS) div))
26.   (setq lst (evenlyDivide minS maxS div))
27.   (setq bestResult (getBestResult func lst comp))
28.   (setq curRep (1+ curRep))
29.   (if (or (>= curRep maxRep) (< (abs (- bestResult minS)) error) (< (abs (- bestResult maxS)) error))
30.     bestResult
31.     (linearSearch func
32.                   comp
33.                   maxRep
34.                   (max (- bestResult spacing) minS)
35.                   (min (+ bestResult spacing) maxS)
36.                   error
37.                   curRep
38.                   div
39.     ) ;_ end of linearSearch
40.   ) ;_ end of if
41. ) ;_ end of defun
42.
43. (defun c:minDist (/ en1 en2 dist pt1)
44.   (setq en1 (car (entsel)))
45.   (setq en2 (car (entsel)))
46.   (setq dist (linearSearch '(lambda (dist)
47.                               (distance (setq pt (vlax-curve-getPointAtDist en1 dist)) (vlax-curve-getclosestpointto en2 pt))
48.                             ) ;_ end of lambda
49.                            '<
50.                            10
51.                            0
52.                            0.001
53.                            1
54.                            50
55.              ) ;_ end of linearSearch
56.   ) ;_ end of setq
57.   (setq pt1 (vlax-curve-getpointatdist en1 dist))
58.   (command "line" pt1 (vlax-curve-getclosestpointto en2 pt1) "")
59.   (princ)
60. ) ;_ end of defun
61.
62.
« Last Edit: March 17, 2022, 10:47:55 PM by Rod »
"All models are wrong, some models are useful" - George Box

#### Rod

• Newt
• Posts: 180 ##### Re: General Hill Climbing Wrapper Function
« Reply #3 on: March 17, 2022, 10:31:48 PM »
Here is a roll-my-own version of vlax-curve-getClosestPointTo to that uses the wrapper function

Code - Auto/Visual Lisp: [Select]
1. (defun c:test ()
2.   (setq en (car (entsel)))
3.   (setq pt (getpoint))
4.   (setq dist (linearSearch '(lambda (dist) (distance pt (vlax-curve-getPointAtDist en dist)))
5.                            '<
6.                            10
7.                            0
8.                            0.001
9.                            1
10.                            50
11.              ) ;_ end of linearSearch
12.   ) ;_ end of setq
13.   (command "line" pt (vlax-curve-getpointatdist en dist) "")
14. ) ;_ end of defun
"All models are wrong, some models are useful" - George Box