圆形 - 多边形交叉点

Question

计算几何问题:
在多边形(例如)P0的边缘(例如EB)上随机选择该点BCDE,以P1,P2,P3,...基于给定距离(即,r)在其他边缘上找到可能的点(即).以下演示通过查找以点为中心的圆P0与多边形边之间的交点来显示解决方案.因此问题基本上可以通过Circle--Line-Segment交叉点分析来解决.

我想知道在计算成本方面有没有更有效的方法解决这个非常简单的问题？该过程将进行几次评估,million times因此任何改进都是有意义的.

• 最终的解决方案将受益于Python的强大功能;
• 如果需要,核心计算将在Fortran中.

更新:
感谢您的评论.请考虑我对评论的评论,这有助于更多地澄清问题.不愿意在这里重复,鼓励考虑所有的评论和答案;).

我刚刚实现了Circle--Line-Segment Intersection基于[here]找到的算法的方法.实际上我改编它用于线段.Python中实现的算法基准如下:


线段的数量是:100,000并且系统通常是桌面.经过的时间是:15 seconds.希望这些有助于对计算成本有所了解.在Fortan中实施核心可以显着提高性能.
然而,翻译是最后一步.

Answer 1

line对于(or line-segment) 和circle( spherein )之间的交集，[此链接]3D中有更多解释、实现细节以及Python、C等示例代码。您可以尝试一下它们来解决您的问题。这个想法与您在[此处] 中已经找到的基本相同。