[编程申请]：提一个有点难度的问题

WHGF

用LISP编程 ------ >  如何确定一个任意多边形的内接矩形或最大内接圆？
这个问题不是一般的难。
希望高手们出招！！！！！！

littlecong

加个条件---凸多边形？

snoopychen

应该是一个比较复杂的问题，假如对于凸多变形和比较简单的凹多边形（还没有仔细想通），应该还是可以解决的。
查了一下全文期刊库，相关的文章并不是很多，好像多数和在一个复杂截面中找出一个可通行的管道有关的实际问题
以下一篇文章的思想倒不是很复杂，虽然不一定完全解决楼主的问题，不过应该挺有启发的。
该文章是英文的，不过有下面的中文摘要

求解最大内切圆的一种新方法
孙玉芹 , 车仁生
(哈尔滨工业大学 自动化测试与控制系 ,黑龙江 哈尔滨 150001)
摘要:提出了一种求解最大内切圆的新方法 ,给出了最大内切圆圆心坐标值的计算公式 ,该方法的基本思路是:首先在被测轮廓上选取初始三点 ,并保证这三点构成一个锐角三角形;接下来通过给出的公式计算出这三点所在圆的圆心坐标值 ,被测轮廓各点到该圆心的距离序列;最后判断该圆半径是否等于上述距离序列中的最小值 ,如果条件不满足 ,用最短距离所对应的被测轮廓点代替上述三点之一 ,并保证新的三点仍然形成一个锐角三角形 ,然后重复上述计算和判断过程 ,直至条件满足。最后一次计算所得到的圆心恰好是被测轮廓的最大内切圆圆心 ,该方法的优点在于不存在原理误差 ,速度快 ,一般二、三次计算即可 ,给出了程序流程图。
关 　键 　词:圆度误差评定;最大内切圆;锐角三角形

WHGF

任意多边形包含凸多变形和凹多边形，在这里对问题进行补充。
三楼说的方法挺好！先谢谢。

xiao_longxin

首先暂不考虑曲线，本帖只讨论任意多边形。
多边形内最大圆，必有且仅有3点在多边形上，由此可以推出如下几点：
1：此圆为多边形3边（此3边可能不相邻）内切
2：此圆为多边形3顶点（3顶点可能不相邻）共圆
3：此圆为多边形2边（此2边可能不相邻）相切且过多边形一顶点
4：此圆为过多边形2顶点（此2顶点可能不相邻）且与多边形一边相切
按此思路做了一个程序，现打包供大家测试，命令名：getmaxcir
但此思路有一个致命弱点：效率极差，几乎不可用。
要看源码请看：http://www.mjtd.com/bbs/dispbbs. ... p;skin=0&page=1

littlecong

楼上的思路正确吗？
这个圆怎么可能过多变形的定点呢？

还有，你的压缩包里只有个.prv文件

snoopychen

凹多边形是可能经过一个顶点的
枚举法应该是可行

但“必有且仅有3点在多边形上”对于正多边形应该是有点不对

查到的一些资料

关于最大内切圆的相关定义
http://www.taylor-hobson.com/faq ... Maximum%20Inscribed

采用vroni图的一个通用代码程序，涉及最大内切圆
http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html

采用MATLAB利用VORONI算法编写的源码cvoronoi
http://www.mathworks.com/matlabc ... amp;objectType=FILE
需要http://www.qhull.org/的函数
cvoronoi computes the smallest circumscribed circle (SCC), the
% greatest inscribed circle (GIC) and the best fitted circle (BFC)
% of a given set of points in 2D. The center of SCC is located on
% one of the furthest-site Voronoi diagram vertices while the center
% of GIC is located on one of the nearest-site Voronoi diagram
% vertices [1].

也有一些java程序

具体有lisp源码的还没有怎么见

应该说这个问题具有实际意义和理论意义，是计算几何的问题，国外有不少相关文章，算法时间被推算为线性的，应该和voroni图有较大关系

xiao_longxin

不好意思，我的打包时搞错了。
楼上snoopychen 兄所说正多边形是我所没有考虑的，但不影响算法的进行。
后来发现，效率不高的主要原因是枚举的量太大，但还有一个原因是因为程序中大量使用了COMMA函数，且枚举的次数越多使用COMMAND函数的次数也越多，现把所有COMMAND函数改成ENTMAKE，效率有所提升，但总的来说还是效率极差，希望高手能给出一个更好的思路。
关注中

WHGF

大家讨论的非常好！这对我和其它网上的朋友都有帮助，其它的话我就不多说了。
我最近一直在想这个困扰我多时的问题......
能否换一种思路将凹多边形转换为凸多变形。具体做法是按一定的规则对多边形进行磨角，消除多边形上的外凸点最后形成一个凸多边形。再用楼上朋友的方法....这只是一个想法还用程序实现

雨箭风刀

关键是算法

xiao_longxin

考虑到要大量3点做圆，取得圆心与半径，用COMMAND效率又差，就用几何算法编了个函数：由三点计算圆心与半径，如果有必要绘圆，再用ENTMAKE效率要高很多
;;已知三点求圆心与半径
(defun XL:get3p->C
       (pt1 pt2 pt3 / A B C D E F X Y CPT pt R X1 Y1 X2 Y2 X3 Y3)
  (SETQ        x1  (nth 0 pt1)
        y1  (nth 1 pt1)
        x2  (nth 0 pt2)
        y2  (nth 1 pt2)
        x3  (nth 0 pt3)
        y3  (nth 1 pt3)
        A   (* 2 (- X2 X1))
        B   (* 2 (- Y2 y1))
        c   (+ (* x2 x2) (* y2 y2) (* x1 x1 -1) (* y1 y1 -1))
        d   (* 2 (- x3 x2))
        e   (* 2 (- y3 y2))
        f   (+ (* x3 x3) (* y3 y3) (* x2 x2 -1) (* y2 y2 -1))
        x   (/ (- (* b f) (* e c)) (- (* b d) (* e a)))
        y   (/ (- (* d c) (* a f)) (- (* b d) (* e a)))
        cpt (list x y 0)
        pt  (list x1 y1 0)
        r   (distance cpt pt)
  )
  (list cpt r)
)
;;测试
;;(defun c:te ()
  ;;(setq pt1 (getpoint)
        ;;pt2 (getpoint)
        ;;pt3 (getpoint)
  ;;)
  ;;(command "circle" "3p" pt1 pt2 pt3)
  ;;(xl:get3p->c pt1 pt2 pt3)
;;)

WHGF

三楼的方法的方法结果好坏主要依赖初始三角形的位置。无法看到原文，可能还有其它一些限定条件。