如何确定我可以从一个点相交多少条线？

Question

给定一些线段（a1，b1）到（c1，d1），（a2，b2）到（c2，d2）例如，我有一条特殊的线从原点径向向外指向，我想确定我可以实现的最大和最小交叉点数。有我可以使用的算法或概念吗？

我能想到的最接近的是礼品包装算法问题，我们可以在其中找到线段的封闭周长，但我停留在概念层面，因此无法设计策略。

另一个想法：如果两条线在 x 或 y 维度上都不相交，那么可以通过它们的最大交点数仅为 1。但这仅适用于我的特殊线指向那个方向，并且那么如何计算其他线段？

Answer 1

据我了解，您需要为每个线段创建 angular 间隔，并检查这些线段与来自坐标原点的射线的交点。

找到每个线段末端的角度（例如，使用 atan2），对这些角度进行排序（作为角度间隔的开始和结束）。

使 array/list 包含所有角度以及 start/end 值为 1/-1 的字段。

按角度对所有项目进行排序。

制作ac=Active_Counter=0

遍历列表，将start/end字段添加到ac。 ac 的最大值对应于 origin-based 射线

相交的最大段数

示例：

 segments (1,0)-(0,1) and (-1,1)-(1,1)
 angles (0, Pi/2) and (Pi/4, 3*Pi/4) // I ordered angles for the second segment
 sorted list    (0;+1), (Pi/4;+1),(Pi/2;-1),(3*Pi/4;-1)
 ac:         0    1        2          1          0

所以最大值是 2

（不要忘记重叠遍历以考虑零角度的间隔）

如何确定我可以从一个点相交多少条线？

How do I determine how many lines I can intersect from from a point?

algorithm

data-structures

convex-hull