python - 圆-多边形交点

Question

计算几何问题:
在多边形(例如BCDE)的边(例如EB)上随机选择点P0，以找到可能的点(即, P1,P2,P3,...) 基于给定距离(即 r)在其他边上。下面的演示展示了一个解决方案，它通过找到以点 P0 为中心的圆与多边形的边之间的交点。所以这个问题基本上可以通过Circle--Line-Segment求交分析来解决。

我想知道在计算成本方面对于这个非常简单的问题是否有更有效的方法？该过程将被评估数次百万次，因此任何改进都是有意义的。

• 最终的解决方案将受益于 Python 的力量；
• 如果需要，核心计算将使用 Fortran。

更新:
感谢您的意见。请考虑我对评论的评论，这有助于进一步澄清问题。不愿意在这里重复它们，鼓励考虑所有评论和答案；)。

我刚刚根据找到的算法实现了Circle--Line-Segment Intersection的方法[here] .实际上，我将其改编为使用线段。 Python实现的算法基准如下:


线段数为:100,000 系统为普通桌面。耗时是:15 秒。希望这些有助于了解计算成本。在 Fortan 中实现核心可以显着提高性能。
然而，翻译是最后一步。

Answer 1

line(或line-segment)和circle(sphere in 3D) 在 [this link] 中有更多解释、实现细节以及 Python、C 等示例代码.您可以尝试使用它们来解决您的问题。
这个想法与您在 [here] 中找到的基本相同。 .