凸多边形上找点

aimisiyou · 发表于 2020-1-28 10:16:01

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

在凸多边形上找一点，使得凸多边形上的点到该点距离最远的长度达到最小值？

tzfcn · 发表于 2020-1-29 10:16:25

这是一个有意义的课题，看看哪个高手的代码好

aimisiyou · 发表于 2020-1-29 12:07:15

如果是钝角三角形或直角三角形，该点是最长边的中点；如果是锐角三角形，过每边中点做中垂线交于三角形于另一点，到该点最远的距离为li,取li（三个）的最小值；
如果是矩形，该点是长边的中点。

aimisiyou · 发表于 2020-1-29 12:09:36

如果是钝角三角形或直角三角形，该点是最长边的中点；如果是锐角三角形，过每边中点做中垂线交于三角形于另一点，到该点最远的距离为li,取li（三个）的最小值；
如果是矩形，该点是长边的中点。

qqqincccken · 发表于 2020-1-29 12:15:36

期待有心的高手出手写一下代码好

aimisiyou · 发表于 2020-1-29 18:05:19

采用暴力解法，选取任意两顶点，做中垂线交于多边形于另一点P，到P最远的距离为LP，选取LP的最小值。
算法复杂度为O(n^3）.

aimisiyou · 发表于 2020-1-30 02:05:13

本帖最后由 aimisiyou 于 2020-1-30 02:06 编辑

_$ (defun fm (pa pb)
      (list (- (* (car pa) (car pb)) (* (cadr pa) (cadr pb)))
            (+ (* (car pa) (cadr pb)) (* (cadr pa) (car pb)))
         )
)
(defun fd (pa pb)
   (mapcar  '(lambda (x) (/ x 1.0 (+ (* (car pb) (car pb)) (* (cadr pb) (cadr pb)))))
            (fm pa (list (car pb) (* -1 (cadr pb))))
         )
)
FM
FD_$ (fm '(3 4) '(5 6))
(-9 38)
_$
_$ (fd '(3 4) '(5 6))
(0.639344 0.0327869)
_$

kmliro_2017 · 发表于 2020-2-2 11:39:22

谢谢分享！！！！！

账号		自动登录	找回密码
密码			立即注册

[研讨] 凸多边形上找点

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。