圆与多边形相交
计算几何问题：
在多边形（例如BCDE）的边（例如EB）上随机选择点P0，以找到可能的点（即，P1,P2,P3,...）基于给定距离（即r）的其他边缘。以下演示通过查找以点 P0 为中心的圆与多边形边缘之间的交点来展示解决方案。所以这个问题基本上可以通过Circle--Line-Segment交集分析来解决。
我想知道在计算成本方面对于这个非常简单的问题有没有更有效的方法？该过程将被评估数百万次，因此任何改进都是有意义的。
- 最终的解决方案将受益于Python的力量；
- 如果需要，核心计算将采用 Fortran 语言。
更新：
感谢您的评论。请考虑我对评论的评论，这有助于进一步澄清问题。不愿意在这里重复它们，鼓励考虑所有评论和答案；）。
我刚刚根据找到的算法实现了Circle--Line-Segment Intersection的方法[此处]。实际上，我对其进行了调整，使其能够与线段一起使用。 Python实现的算法的基准如下：
线段数为：100,000，系统为普通桌面。经过的时间是：15 秒。希望这些有助于提供一些计算成本的想法。在Fortan中实现核心可以显着提高性能。
然而，翻译是最后一步。
A Computational Geometry problem:
The point P0 is chosen randomly on an edge (e.g.,EB) of a polygon (e.g.,BCDE), to find possible points (i.e., P1,P2,P3,...) on other edges based on the given distance (i.e., r). The following demonstration shows a solution by finding intersections between the circle centered on the point P0 and the edges of polygon. So the problem basically could be solved by Circle--Line-Segment intersection analysis.
I wonder is there any more efficient method for this very simple problem in terms of computation cost? The process will be evaluated several million times so any improvemnt is of interest.
- the final solution will benefit from Python power;
- the core computation will be in Fortran if required.
Updates:
Thanks for your comments. Please consider my comments on comments which helps to clarify the question more. Not willing to repeat them here, encouraging to consider all comments and answers ;).
I just implemented the method of Circle--Line-Segment Intersection based on the algorithm found [here]. Actually I adapted it to work with line-segments. The benchmark of the algorithm implemented in Python is as follows:
The number of line segments is: 100,000 and the system is usual desktop. The elapsed time is: 15 seconds. Hope these are helpful to give some idea of computation cost. Implementation of core in Fortan could improve the performance significantly.
However the translation is the last step.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
用于
线（或线段）和圆（3D球体）之间的交集code>）[这个链接]。您可以尝试一下它们来解决您的问题。这个想法与您在[此处]中找到的基本相同。
For intersection between
line(orline-segment) and acircle(spherein3D) there is a bit more explanation, implementation details and also Python, C etc sample codes in [this link]. You may try them for your problem.The idea is basically the same as you have already found in [here].
假设圆--线交点经过优化，您可能能够通过区分不同的情况来获得一些东西：
对于点 A，B：
如果 d(P0, A)
If d(P0, A)
r和d(P0，B)＜ r：无交集
if d(P0, A) == r：在 A 处交集
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：无交叉点
->如果 到线 (A, B) 的最小距离 == r: 1 个交点
->如果 到线 (A, B) 的最小距离 < r: 2 个交点
Assuming the
circle--line-intersectionis optimized, you might be able to gain something by distinguishing between different cases:for point A, B:
If d(P0, A) < r and d(P0, B) < r: No intersection
if d(P0, A) == r: Intersection at A
circle--line-intersectionIf d(P0, A) > r and d(P0, B) < r: 1 intersection, execute
circle--line-intersectionIf d(P0, A) > r and d(P0, B) > r: There is either 0, 1 or 2 intersections
-> If the minimum distance to line (A, B) > r: No intersections
-> If the minimum distance to line (A, B) == r: 1 intersection
-> If the minimum distance to line (A, B) < r: 2 intersections