求解图形移动距离的问题！
求解图形移动距离的问题：<br/>如图所示，已知封闭多边图形A和B（A和B均由若干直线段和圆弧组成）以及直线CD，求图形B沿直线CD方向移动多少距离才能和图形A相交？<br/>求教各位高手们有没有比较通用的算法求类似图形移动相交的问题，非常感谢各位高手多多帮助！ <p>这是一个很好的计算几何题目啊</p><p>可惜一时还找不到相关论文，扫描线法当然可以解决，但是对于圆和直线组成的图形，我觉得应该还是存在着几何解的。</p><p>我是这么考虑的，假如图形只是圆形和直线组成的话，我先做些初步探索吧，问题其实还需要细分很多</p><p>找出所有的角点和圆弧端点，根据平行线将图形分为多个区域</p><p>1）假如全部是直线型的，则考虑角点即可</p><p>2）假如是直线型+圆形，此时呢，一种比较常见的图形如下，就是，比如沿定向直线，直线和圆形之间的最小距离如何，圆和圆之间的最小距离如何</p><p> </p><p>3.</p><p>4.</p><p>不过对于凸凹弧，凹凹弧，弧段等等，可能都会出现各种情况，但应该可以穷举</p><p>今天晚上再思考一下</p> <p></p><p> </p>
<p>AB是方向，CD是为所求，EF为公切线.</p>
<p> </p>
<p>上面图中最主要的是要求这点。剩下算法参考：</p>
<p><font face="Verdana">http://bbs.mjtd.com/forum.php?mod=viewthread&tid=75403</font></p>
页:
[1]