如何找到与线段相交的部分圆周围的点

Question

我正在为我的方形网格寻路项目研究避障解决方案。我首先执行 A* 搜索以查找 "long" 路径。接下来，我获取我的单位的当前位置并迭代 "long" 路径，直到我不再有视线，这会产生 "short" 路径（单位的位置 -> 最远位置 w/LoS）。当我到达 "short" 路径的尽头时，我重复寻找另一条 "short" 路径，直到到达目标。

如果路上有障碍物，我想修改我的短路径以添加未对齐到网格的额外点。我发现障碍物通过它们的中心位置和半径与短路径相交，我的计划是添加围绕这些障碍物圆周的额外点。这些点必须添加到直线相交的圆的一侧，这样路径就不会一直绕到另一侧。

这里有一些截图可以更好地解释：

http://puu.sh/xFHw5/0e8f32da7a.png

http://puu.sh/xFHwU/04a4b1fe27.png

http://puu.sh/xFHxk/56f3051cc5.png

http://puu.sh/xFHxO/fcc6151a02.png

Answer 1

你可以从两边找到由tangents to circle组成的路径和切线与圆相切的圆弧连接点。作为变体 - 使用切线的交点，在这种情况下路径将仅包含两个直线段。