首先，不得不说函数的极值问题是一个比较难的问题，特别是全局的极值问题。
一种启发式方法为：从独立自变量的各种不同初值开始，求出所有的局部极值，然后从中选出最大的或者最小的。二是对局部极值以一有限步长的扰动，然后分析由此计算出来的就结果，是稍有改进还是一直保持不变。关于模拟退火法，呵呵，太高级了，在lisp中很难实现。
我在这个程序中，首先参考了《数值算法》的C程序部分，编写了LISP。
在这本书中讲到了几个方法：
1、 一维黄金分割搜索。经过研究，极值的折半搜索并不是有效的，最佳划界区间a<b<c应满足内点b与其中一个外点(如a)的距离比例为0.38197，而与另一外点的距离比例为0.6180399。这个思想就是在每一步划界中给定一个三点组，下一试探点取在较长区间段的0.38197的分割点，如果开始划界的三点组的各段没有按照黄金比率分割，那么逐次选择黄金分割点的进程很快收敛到合适的、自行重复的比率。这个搜索方法是线性的，即随着附加函数的计算，有效数字逐步线性增长。
2、 关于Brent方法，是超线性的，在技术上被称之为逆抛物线内插。其原理是通过拟抛物线内插法，逐步接近目标函数的最小值。
3、 一阶导数的一维搜索法，那就是采用一阶导数，沿着函数的递减方向前进，并综合了Brent方法，黄金分割搜索法。
4、 其他的还有几个方法，谈到了多维函数的极值问题。我留待以后讲解。
5、 其中还讲到了如何划界的方法，以及一个实现划界的函数mnbrak（即在一个区间内找到区间中间的点，并且这个点的函数值在这三点中最小）
另外我自己也根据思路编写了一个折半的搜索方法，这个对上面的几种求解无效的情况下，显得很有效果。
可能你有点不耐烦，因为你最关心的是如何跟CAD的结合问题。
CAD的图元之间的函数关系，常常不是规则的，那么显而易见的。因而对它们的求极值，求导，是一件很困难，甚至不可能的事情，因此，我们要综合运用多种方法。
下面我分例子讲解我的思路。
1、 两条曲线之间的最小距离.
这个问题如果是用其他方法，完全是有函数的，譬如arx的getclosestpointto函数，就是用来求解两个曲线之间的最小距离的。但LISP中vlax-curve 函数中没有提供，只是提供了vlax-curve-getclosestpointto ，但这个函数仅仅是某点到曲线的最小距离，而不是两条曲线之间的最小距离。但是，我们可以利用这个函数来计算两条曲线之间的最小距离。因此程序的流程如下：
A 目标函数的设计：
参数 x ---第一条曲线的曲线参数x
返回值：参数x对应的点 pt 到第二条曲线的最小距离。(为了使得程序有通用性，采用了列表的函数返回值，第一个数值是这点对应的最小距离，第二和第三个分别是这两点)
B .对第一条曲线分成几个区间，每个区间采用mnbrak函数去试探点。
然后采用Brent方法去求得目标函数的最小值。
C 上步中求的的最小值是局部解，所以我们必须要每个局部比较一下，这样才能选取全局部的最小。
D 得到解之后，画出来。
2 画出曲线的包围盒
说实在话，我并不想用求极值的方法来求解这个问题。因为，vla-getboundingbox已经可以做到，但是Autodesk公司却表现的不够完美， boundingBox，对于spline来说根本就不准确，还有一点的就是，boundingBox得到的总是WCS 下的,所以，如果追求完美的人或者有这方面的需要的，就不够了。
因此建议vla-getboundingbox如果能满足你的需要，就不要采用这个程序了，毕竟用了迭代，速度上会有所下降。但完全可以满足一般要求。
那么程序是怎样设计的呢？
A 目标函数的设计
参数 x ---曲线的参数x
返回值 参数x对应的点的坐标的分量(我在这里只是设计了x、y分量，如果你需要的话，可以把z分量也加上)的最大最小数值，（最大数值可以加一个符号就能求最小了）
B .对曲线分成几个区间，每个区间采用mnbrak函数去试探点。
然后采用Brent方法去求得目标函数的最小值。
C 同例子1.
D 解出来后，依据x y分量的极值，画出boundingbox。
3 画出两条曲线的公切线。
这个功能是在你不想用command中xline来求解时候，或者无需人工干预的情况下用到。
关于椭圆，圆的公切线，参见我下面的帖子，这里采用的技术更快，更准确：
http://bbs.mjtd.com/forum.php?mod=viewthread&tid=82900&star=2
为了求出spline 或者复杂点的曲线的公切线，有必要采用另外的一种方式：
A 目标函数的设计
参数: x --第一条曲线的曲线参数x
返回值： 说实在话，这个地方我为难了很久，一直没找到一个完美的返回值。不过我这里是这么设置的，第一条曲线参数x对应的点P1的切线与第二条曲线相交，如果没有交点则设置为返回值为1e308---无穷大，如果相交或者相切，就为第二条曲线上的交点P，交点处的切线矢量Q和P1之间的det数值除以P1 到P的距离。
B、基本同例1.但是因为函数是不连续的，所以Brent方法我不肯定是否都有效，故采用了我自己设计的搜索法
C、实际上只有满足特定解的才能算是公切线，故需要判断。
D、画出公切线。
细节问题：譬如参数越界问题，坐标旋转问题，怎样取点和划分区间等等各位可以参考我的程序。
另外，由于是匆匆写来，我没进行错误检查和bug测试。希望你能提出好的建议。谢谢。
函数进行了更新，请重新下载附件。Vlx是编译的文件，运行速度更快。
在以后的跟帖中，我会继续谈谈我的体会和一些应用。
譬如特别是在排料中的一些应用，这些已经进入到二维或者更高维。那时候这些一维的方法有些就不能用了，
源码已经附上。各位如需要转载请说明来源。谢谢。
放在一楼。
[复制链接]
发表于 2010-9-6 21:23:00
置顶卡
变色卡
显身卡
楼主
发表于 2021-12-29 20:02:53
发表于 2010-9-7 00:24:00
