圈多边形交点

甲计算几何问题：
点P0随机选择上的多边形的边（例如，EB）（例如，BCDE），以找到可能的点（即，P1,P2,P3,...）上的其他基于给定距离的边（即，r）。以下演示通过找到以点号P0为中心的圆与多边形边之间的交点来显示解决方案。所以这个问题基本上可以通过Circle--Line-Segment相交分析来解决。圈多边形交点

我想知道有没有更高效的方法这个非常简单的问题就计算成本而言？该过程将被评估几个million times，所以任何改进都是有意义的。

最终解决方案将受益于Python功耗;
核心计算将在Fortran如果需要。

enter image description here

更新：
感谢您的意见。请考虑我对评论的评论，这有助于澄清更多问题。不愿在这里重复，鼓励考虑所有评论和答案;）。

我刚刚实施了基于[here]算法的Circle--Line-Segment Intersection的方法。事实上，我调整它适用于线段。在Python实现的算法的基准如下：
enter image description here

线段的数目是：100,000和系统通常是桌面。所用时间为：15 seconds。希望这些有助于给出一些计算成本的概念。在Fortan的核心实现可以显着提高性能。
但是，翻译是最后一步。

来源

2012-01-23 Developer

所有百万个查询的距离“r”是否相同？我们可以指望多边形是凸的吗？ –

@BorisStrandjev对于我们的问题，所有的多边形都是凸的。对于每次迭代，“r”可能会有所不同，因此它可能会变化，但对于每个多边形都是不变的。 – Developer

并且是在单个多边形或不同的数百万个查询中完成的？ –

对于line（或line-segment）之间的交叉和circle（在3Dsphere）有更多的解释，实施细节和也的Python，C在[this link]等样本代码。你可以尝试解决你的问题。
这个想法基本上和你在[here]中已经找到的一样。

来源

2012-01-23 11:47:48 Developer

链接已死亡 – Alnitak

假设circle--line-intersection进行了优化，你可能能够通过不同情况区别有所收获：

为点A，B：

如果d（P0，A）< r和d（P0，B）< R：否相交
如果d（P0，A）== R：交叉口A处
如果d（P 0，B）== R：交叉口B处
如果d（P0，A）< r和d（P0，B）> R：1个相交，执行circle--line-intersection
如果d（P0，A）> r和d（P0，B）< R：1个相交，执行circle--line-intersection
如果d（P0，A）> r和d（P0，B）> R：有是0，1个或2个交点（A，B）> r：无交集 - >如果minimum distance以行（A，B）== r：1交叉 - >如果minimum distance以行（A，B）< r：2相交纳秒

来源

2012-01-23 09:12:39 Wesley

在最后一种情况下，我相信你的意思是d（P0，P2）> r。 –

请注意，以“P0”为中心的圆圈，所有交点位于圆上，因此它们的距离等于“r”。那就是'd（P0，*）= r'。我从你的回答中遗漏了什么？ – Developer

对不起，我把交点与实际点混淆了。我会修复答案，希望它更有意义，然后 – Wesley

圈多边形交点

回答

相关问题