求解图形移动距离的问题！

zzs

求解图形移动距离的问题：
如图所示，已知封闭多边图形A和B（A和B均由若干直线段和圆弧组成）以及直线CD，求图形B沿直线CD方向移动多少距离才能和图形A相交？
求教各位高手们有没有比较通用的算法求类似图形移动相交的问题，非常感谢各位高手多多帮助！

qjchen

这是一个很好的计算几何题目啊

可惜一时还找不到相关论文，扫描线法当然可以解决，但是对于圆和直线组成的图形，我觉得应该还是存在着几何解的。

我是这么考虑的，假如图形只是圆形和直线组成的话，我先做些初步探索吧，问题其实还需要细分很多

找出所有的角点和圆弧端点，根据平行线将图形分为多个区域

1）假如全部是直线型的，则考虑角点即可

2）假如是直线型+圆形，此时呢，一种比较常见的图形如下，就是，比如沿定向直线，直线和圆形之间的最小距离如何，圆和圆之间的最小距离如何

 

3.

4.

不过对于凸凹弧，凹凹弧，弧段等等，可能都会出现各种情况，但应该可以穷举

今天晚上再思考一下

highflybird

 

AB是方向，CD是为所求，EF为公切线.

 

上面图中最主要的是要求这点。剩下算法参考：

http://bbs.mjtd.com/forum.php?mod=viewthread&tid=75403