例如，给定一些线段 (a1, b1) 到 (c1, d1)，(a2, b2) 到 (c2, d2)，我有一条从原点径向向外指向的特殊直线，我想确定我可以实现的最大和最小交叉点数。有我可以使用的算法或概念吗？
我能想到的最接近的是礼品包装算法问题，我们可以在其中找到线段的封闭周长，但我停留在概念层面，因此无法设计策略。
另一个想法:如果两条线在 x 或 y 维度上都不相交，那么可以通过它们的最大交点数仅为 1。但这仅适用于我的特殊线指向那个方向的情况，所以如何我是否考虑其他线段？
最佳答案
据我了解，您需要为每个线段创建角度间隔，并检查这些线段与来自坐标原点的射线的交点。
找到每个线段末端的角度(例如，使用 atan2)，对这些角度进行排序(作为角度间隔的开始和结束)。
创建包含所有角度的数组/列表以及值为 1/-1 的开始/结束字段。
按角度对所有项目进行排序。
使ac=Active_Counter=0
遍历链表，在ac中加入start/end字段。 ac 的最大值对应于基于原点的射线相交的最大段数
示例:
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
(不要忘记重叠遍历以考虑零角度上的间隔)
关于algorithm - 如何确定我可以从一个点相交多少条线？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49600497/