如何求解从原点出发的射线与线段的最大、最小交点数？

嘿，这个问题其实可以通过角度区间分析+扫描线算法来解决，我给你一步步拆解清楚，顺便说说为啥礼物包装算法不太适用～

核心转化：把射线问题变成角度区间问题 #

径向射线的本质就是一个角度θ（从x轴正方向逆时针转的角度），所以咱们的问题可以转化为：

对每一条线段，找出所有能让射线θ和它相交的θ的区间；然后通过这些区间的重叠情况，找出被最多区间覆盖的点（对应最大交点数），以及被最少区间覆盖的点（对应最小交点数）。

第一步：给每条线段计算对应的角度区间 #

拿一条线段P₁(x₁,y₁)到P₂(x₂,y₂)来说，要找出所有θ使得射线θ和它相交，分几种情况处理：

• 线段穿过原点：如果原点在这条线段上，那所有射线都会和它在原点相交（如果规定原点算有效交点的话），对应的θ区间就是整个[0, 2π)。
• 线段两个端点在原点同侧：先算两个端点的极角θ₁=atan2(y₁,x₁)，θ₂=atan2(y₂,x₂)。线段在原点的“视野”里会占据一个角度范围，这个范围就是θ₁和θ₂之间的较小区间——比如θ₁是350°，θ₂是10°，那区间就是350°到360°，加上0°到10°。
• 线段两个端点在原点两侧：这时候线段会把原点的视野分成两部分，只有当射线落在其中一部分时才会相交，其实对应的区间还是θ₁和θ₂围成的较小那个区间（本质是原点到线段的可见角度范围）。
• 线段和原点共线（但不穿过原点）：只有当射线和这条线完全重合时，才会和线段相交，对应的θ就是那个共线的角度（相当于一个长度为0的区间）。

第二步：用扫描线算法计算区间的最大/最小重叠数 #

现在我们有了所有线段的角度区间，接下来就是经典的区间重叠问题了：

求最大交点数

1. 把所有区间拆成事件点：每个区间[start, end]，如果start < end，就加两个事件：(start, +1)（进入区间，交点数+1）和(end, -1)（离开区间，交点数-1）；如果start > end（比如跨了0°/360°），就拆成[start, 2π)和[0, end]两个区间，分别生成对应的事件点。
2. 把所有事件点按角度从小到大排序（注意0和2π是同一个点）。
3. 遍历排序后的事件点，维护一个当前重叠数的变量，每次遇到+1就加1，遇到-1就减1，过程中记录下最大的那个数值，就是最大交点数。

求最小交点数

和上面流程一样，只是遍历的时候记录最小的重叠数。另外要注意：如果所有区间的并集没有覆盖整个[0,2π)，那肯定存在射线和任何线段都不相交，这时候最小交点数就是0。

边界情况要注意 #

• 线段端点在射线上：如果规定端点算有效交点，那处理事件点的时候要注意顺序——比如两个事件在同一个角度，先处理+1再处理-1，这样端点处的重叠数才是对的。
• 原点处的交点：如果不算原点作为交点，那穿过原点的线段要特殊处理，比如拆成从原点到P₁和原点到P₂的两条线段，这时候只有射线和它们共线时才会有交点。

为啥礼物包装算法帮不上忙？ #

礼物包装算法（Jarvis March）是用来求点集凸包的，核心是找凸边界，和射线与线段的交点数问题根本不搭边。凸包最多能帮你快速排除完全在凸包外的线段？但线段可能在凸包内部，所以这个思路对解决你的问题没什么实际作用，你之前卡在这里很正常～

补充：其他可能的思路 #

如果你之前有过类似“极坐标投影”的想法，其实和上面的角度区间分析是一回事。另外还有对偶变换的方法，把射线转成点、线段转成区域，再找区域交集数的最值，但这个方法偏理论，不如扫描线算法直接好用。

内容的提问来源于stack exchange，提问作者oldselflearner1959