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.

Hiroko

Yes, binary search would do the trick here. And another hint - you can use that the cross (vector) product of the points of a polygon side, which is bellow the line are both negative(positive) and the points of a side which is above the line are both positive(negative). Hope that helps, and does not spoil it too bad. – Shoulders

On what do I apply Binary Search? – Hiroko

I have an idea, but there are some corner cases for it. I will try to define this idea completely and when I'm done I'll get back to you. (in short, you can use ternary search over the distance from the line, but in some cases you can lose solutions in that way) – Shoulders

An important question - how do you store the data about the polygon? – Paine

Any DS can be used.. The DS can be constructed from the input directly the input is in form of points (x,y). – Hiroko

is the polygon different per input case? You can preprocess the polygon in O(N) and then process each segment-query in O(logN). – Roxy

cs.princeton.edu/~chazelle/pubs/… Theorem 3 seems to solve the problem for dynamic polygons as well. – Roxy

@Roxy The link you shared seems to have an answer but I can't understand it at all.. Can u please explain what it is doing? – Hiroko

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).

Damnable

Answer 2

This answer was confusing so I wanted to provide some more detail in a different way.

Lets assume you have your data in array P and you are checking against Line U. p_0 is the most left lowest point. I.e p_0.x < p_i.x and in ties ensure p_0.y < p_i.y. P is sorted in ccw like most ConvexHulls are. You also have p_m where m is the half way point i.e n/2 at first. We define L,M,H as our binary search indices with L = 0, M = n/2, H = n-1. I'm going to write recursion but you could unroll this.

Base case:

Is the "polygon" array has n<= 3 points. In this case just check every line in the triangle or line for intersection with U O(1).

Recursive Step:

Do L_m = Line(p_0, p_m) intersect with U to find p_I, O(1). If p_I is NULL we know that U is ccw or cw from L_m you can use a directed Orientation Test to find which in O(1). If its ccw, recurse with ConvexLineInt({p_0,p_m,...,p_h},U) else ConvexLineInt({p_0,p_l,...,p_m},U).

If p_I exists it must occur among the line L_m i.e it is in a fully ordered set and we check these cases:

L_m.0 <= p_I <= L_m.1 (in between) => return Line intersects

p_I < L_m.0 i.e is to the left of the polygon. We calculate p_U which is U intersects with L_0= Line(p_0, p_l), O(1). If p_U is NULL that means the Line U is outside the polygon. This means U is ccw to L_0. Since p_U exists we can check Orient(L_m, p_U)=w this cannot be 0 since there is an intersection. If w > 0 the intersection is ccw i.e U can only be ccw to L_m and we can recurse as we did above on the "right" set. otherwise the point is below and U can only be cw to L_m recurse on the "left" set Notice we always keep p_0 its a pivot point for us.

p_I > L_m.1 should be symmetric and I'll leave as an exercise

Since every check is O(1) and we are dividing the set into two or so the run time is that of binary search i.e O(log n). Use Master's Theorem if you want to be formal.

Hopefully this is helpful! Orient test: How to tell whether a point is to the right or left side of a line
Finding an intersection of 2 lines: https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

Clastic