纯数学计算求多边形之间最小距离

llsheng_73

熬了一晚上，总算能计算出来了,至于算法的优化，限于水平，只能期待各位版主大人，各位兄弟姐妹们多提建议了
其实就用了个最笨的办法，分别以两个多边形的顶点P与另一个多边形的相邻两个顶点p的对边L)组成三角形，计算p到L的垂足,如果垂足在L延长线上则的返回P到L最近的端点p1的距离d及这两个点组成的表(d p p1),否则返回垂距(d p 垂足)最后对表进行排序选出最短距离，由于返回了顶点及垂足，因此可以在后边的应用中方便的利用最短距离所在的两个点的坐标。

logoin

llsheng_73 发表于 2013-11-2 23:16
我觉得只是取表中的元素出来纯计算，不需要生成图元以辅助计算然后删除，也不对表本身进行操作，就算慢也 ...

如果两根线的话可以做得很快，我有时面对的是超过一万条线，每条线节点都上百个，还有弧，要求出这一堆线中的最小间距，那速度是很难提上去的

highflybird

http://blog.csdn.net/acmaker/article/details/3178696
如果楼主的两个多边形是凸多边形，可以参考上面的算法。
但是如果两个多边形不是凸多边形，那就有些麻烦了。

llsheng_73

highflybird 发表于 2013-11-4 10:47
http://blog.csdn.net/acmaker/article/details/3178696
如果楼主的两个多边形是凸多边形，可以参考上面的 ...

谢谢高飞鸟版主，在大家的指点下已经弄出来了，好象是可以允许凹多边形的

荒野孤行

llsheng_73 发表于 2013-11-3 05:37
熬了一晚上，总算能计算出来了,至于算法的优化，限于水平，只能期待各位版主大人，各位兄弟姐妹们多提建议 ...

我倒是想要顶点连接的呢，以下是最近点连接的，供参考。

(defun c:test ()
  (setvar "osmode" 15359)
  (setvar "cmdecho" 0)
  (command "undo" "be")
  (princ "\n功能：将点选的两条曲线之间的最近端点对连。\n制作者：吴丁运\n")
  (vl-load-com)
  (while
    (progn
      (setq ent1 (entsel "\n请点选第一条曲线：\n"))
      (not
        (if (= ent1 nil)
          nil
          (wcmatch (cdr (assoc 0 (entget (car ent1))))
                   "LWPOLYLINE,POLYLINE,SPLINE"
          )                                ;限定只能选取的曲线类型
        )
      )
    )
     (princ
       "\n提示：选取的不是多段线、样条曲线或未选取任何图元,请重新选取第一条曲线：\n"
     )
  )
  (while
    (progn
      (setq ent2 (entsel "\n请点选第二条曲线：\n"))
      (not
        (if (= ent2 nil)
          nil
          (wcmatch (cdr (assoc 0 (entget (car ent2))))
                   "LWPOLYLINE,POLYLINE,SPLINE"
          )                                ;限定只能选取的曲线类型
        )
      )
    )
     (princ
       "\n提示：选取的不是多段线、样条曲线或未选取任何图元,请重新选取第一条曲线：\n"
     )
  )
  (setq        entnam1        (car ent1)
        obj1        (vlax-ename->vla-object entnam1)
        entnam2        (car ent2)
        obj2        (vlax-ename->vla-object entnam2)
        j        -1
        n        0
        ptlist        nil
  )
  (while (setq ptdd (vlax-curve-getpointatparam obj1 (setq j (1+ j))))
    (setq ptlist (cons ptdd ptlist))        ;获取端点坐标，获取顶点坐标
  )
  (command "color" "Bylayer")
  (command "layer" "M" "层-两线端点对连" "C" "1" "层-两线端点对连" "")
  (setvar "osmode" 0)
  (repeat (length ptlist)
    (setq pt1 (nth n ptlist))
    (setq pt2 (vlax-curve-getclosestpointto obj2 pt1))
    (setq pt2_near
           (vlax-curve-getPointAtParam
             obj2
             (+ (vlax-curve-getParamAtPoint obj2 pt2) 0.5)
           )
    )
    (if        (<= (distance pt1 pt2) (distance pt1 pt2_near))
      (command "Line" pt1 pt2 "")
      (command "Line" pt1 pt2_near "")
    )
    (setq n (1+ n))
  )
  (setvar "osmode" 15359)
  (command "undo" "e")
  (princ)
)