Intersection of line segment and convex polygon

Question

Looking for a O(logn) algorithm to identify the line segments of the convex polygon which intersect with an extended line segment. It is known for sure that the line segment lies inside the convex polygon completely.
Example: Input: ab /Line segment/ , {1,2,3,4,5,6} /Convex polygon vertices in CCW order alongwith their coordinates/
Output: 3-4,5-6

This can be done by getting the equation of all the lines and checking if they intersect but that would be O(n) as n lines need to be checked for intersection. I think it should be possible to use Binary search(because of the logn bound) to reduce the complexity but I can't understand on what to apply it.

Answer 1

At first, you need to work with oriented polygon edges and store them in an array (or may be in another data structure, which allows direct access with time complexity not more than O(logN)). The linked list isn't good for this problem.

Also you need to assign orientation to your extended segment - let's say it's oriented from A to B. Then it partitions the plane into two halfplanes - left and right. You choose your initial edge (with vertices 0 and 1) and then the middle edge (with vertices [n/2]-1 and [n/2]). There are two cases - the initial edge intersects the extended segment or it doesn't. I'll consider the first case here, leaving the second one to you. Also I'll assume the initial edge lies entirely in the right halfplane (the left plane case is symmetric). The middle edge partitions the polygon into two edge paths - I'll call them the first one (vertices from 0 to [n/2]) and second one (vertices from [n/2] to 0).

Five cases are possible - the middle edge can:

1. Lie entirely in the right halplane (the same as the initial edge) and follow the initial edge - then you recursively analyze the second path.
2. Lie entirely in the right halplane (the same as the initial edge) and precede the initial edge - then you recursively analyze the first path.
3. Lie entirely in the left halfplane (not the one where the initial edge is) - then you have to recursively analyze both paths.
4. Intersect the extended segment going from right halfplane to the left halfplane - one intersection is found, and then you recursively analyze the second path.
5. Intersect the extended segment going from left halfplane to the right halfplane - one intersection is found, then you recursively analyze the first path.

So - the most "inconvenient" case is the (2) - you can't drop any paths in this case, but it looks like it can't be repeated for the whole polygon.

Also you'll have to calculate relationship between oriented polygon edges - "follows/precedes". It can be done using the relative edge angle - the "following" edge must turn to the left relative to the "preceding" edge (because of convexity).