Given some line segments (a1, b1) to (c1, d1), (a2, b2) to (c2, d2) for example, I have a special line that points radially outwards from the origin, and I want to determine the maximum and minimum number of intersections I can achieve. Is there an algorithm or concept I can use?
The closest I can think of is the gift wrapping algorithm problem, where we can find the enclosing perimeter of the line segments, but I'm stuck at the concept level and so unable to devise a strategy.
Another thought: if two lines are not intersecting in either x or y dimensions, then the maximum number of intersection that can pass through them is just 1. but that applies only if my special line points in that direction, and so how do I account for other line segments?
As far as I understand, you need to create angular intervals for every segment and check for intersections of these segments with ray from coordinate origin.
Find angle for every segment end (for example, using atan2), order these angles (as start and end of angluar interval).
Make array/list containing all angles together with start/end field with values 1/-1.
Sort all items by angles.
Make ac=Active_Counter=0
Traverse list, adding start/end field to ac. Max value of ac corresponds to maximal nuimber of segments intersected by origin-based ray
Example:
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
So max value is 2
(Don't forget to overlap traversal to account for intervals over zero angle)