Optimal algorithm if line intersects convex polygon?

Lhf's answer is close to correct. Here is a version that should fix the problem with his.

Up vote 7 down vote favorite 3 share g+ share fb share tw.

I would like to know if there is faster algorithm then O(n) for detecting if line intersects a convex polygon. I know the algorithm when you check every edge of the polygon if it intersects with the line and look if the number of intersections is odd or even, I am just looking if there exists some faster for example in O (log n) complexity. Thanks algorithm math graphics computational-geometry link|improve this question edited Dec 21 '10 at 9:47Draco Ater2,5651516 asked Dec 21 '10 at 9:34infinity_x382.

– Tim Barrass Dec 21 '10 at 9:36 And I always thought that O(log n) was slower than O(n)... – GolezTrol Dec 21 '10 at 9:37 @GolezTrol I think you're thinking of O(n log n) – daveb Dec 21 '10 at 9:40 1 I can't see how there can be a faster one. How can you detect an intersection without looking at every line, and so O(N)? – Paul Dec 21 '10 at 9:47 There is some problem that I am trying to solve and this is the last part of it.

So, actually the polygon is Voronoi cell. – infinity_x Dec 21 '10 at 9:54.

Lhf's answer is close to correct. Here is a version that should fix the problem with his. Let the polygon have vertices v0, v1, ..., vn in counterclockwise order.

Let the points x0 and x1 be on the line. Note two things: First, finding the intersection of two lines (and determining its existence) can be done in constant time. Second, determining if a point is to the left or the right of a line can be done in constant time.

We will follow the same basic idea of lhf to get an O(log n) algorithm. The base cases are when the polygon has 2 or 3 vertices. These can both be handled in constant time.

Determine if the line (v0,v(n/2)) intersects the line (x0,x1). Case 1: They do not intersect. In this case the line we are interested in is either to the left or the right of the line splitting the polygon, and so we can recurse into that half of the polygon.

Specifically, if x0 is to the left of (v0,v(n/2)) then all the vertices in the right "half", {v0, v1, ... v(n/2)} are on the same side of (x0,x1) and so we know that there is no intersection in that "half" of the polygon. Case 2: They do intersect. This case is a little trickier, but we can still narrow down the intersection to one "half" of the polygon in constant time.

There are 3 subcases: Case 2.1: The intersection is between the points v0 and v(n/2) We are done. The line intersects the polygon. Case 2.2: The intersection is closer to v0 (that is, outside the polygon on v0's side) Determine if the line (x0,x1) intersects with the line (v0,v1).

If it does not then we are done, the line does not intersect the polygon. If it does, find the intersection, p. If p is to the right of the line (v0, v(n/2)) then recurse into the right "half" of the polygon, {v0, v1, ..., v(n/2)}, otherwise recurse to the left "half" {v0, v(n/2), ... vn}.

The basic idea in this case is that all points in the polygon are to one side of the line (v0, v1). If (x0, x1) is diverging away from (v0, v1) on one side of its intersection with (v0, v(n/2)). We know that on that side there can be no intersection with the polygon.

Case 2.3: The intersection is closer to v(n/2) This case is handled similarly to Case 2.2 but using the appropriate neighbor of v(n/2). We are done. For each level, this requires two line intersections, a left-right check, and determining where a point is on a line.

Each recursion divides the number of vertices by 2 (technically divides them by at least 4/3). And so we get a runtime of O(log n).

Please, clarify what is left/right half of the polygon. Maybe it would be better to use terms v0->vk or vk->v0 assuming the order is CCW. – Juraj Blaho Dec 22 '10 at 9:46 Everytime I said left/right half I did clarify, I listed the vertices in that half.

Specifically, the left half is the vertices that are not to the right of the line (v0,v(n/2)), {v0, v1, ..., v(n/2)}. I use the term not to the right because it is the set of vertices to the left of the line plus those on the line. – Chris Hopman Dec 22 '10 at 9:53 +1 Until I find a contra-example.

Note: I think the clarification is wrong. In CCW order the right half is v0->v(n/2). – Juraj Blaho Dec 22 '10 at 10:23 1 thanks for fleshing out my short description.

– lhf Dec 22 '10 at 10:52 @juraj - Yes, you are correct. Fixed. – Chris Hopman Dec 22 '10 at 16:54.

Bounding boxes may prove useful. Recall that a convex part of an affine space is the intersection of all its envelope hyperplanes: you could get an approximation of your polygon (read a "bounding convex polygon") by considering only the intersection of a subset of the envelope hyperplanes, test for intersection of your line with this approximation, and refine if necessary. All this works better if you expect a low number of intersections.

1: interesting idea! – EOL Dec 22 '10 at 8:46 +1: Very practical approach. – Juraj Blaho Dec 23 '10 at 8:24.

Here is a O(log n) algorithm. Let L be the line. Assume that the polygon is oriented counterclockwise.

If vertices 1 and n/2 are on the left side of L, then consider the polygon 1,...,n/2, else consider the polygon n/2,...n,1. The base case is a single edge.

That is not correct. If the vertices are all on the left side, they will NOT interfere with the line (but you consider only them). Also if that two points are on the left, it does not mean all points between them are on the left.

– Juraj Blaho Dec 21 '10 at 13:51 1 This algorithm is mostly correct, but you should clarify it a bit. Specifically, left-side of a line is somewhat ill-defined. I find positive and negative half-space more fitting.

Also, the case where the line halving the polygon intersects the line of course terminates the algorithm. BTW, this is just a simple modification of standard binary search. – ltjax Dec 21 '10 at 14:06 Having two points on one side of a line does not say anything about the points in between (even in the case of convex polygon).

It is not binary search because you do not begin with full range. You just begin with random range and split it. This means you may miss the intersection.

– Juraj Blaho Dec 21 '10 at 14:22 Ok, you are correct, I missed that case. – ltjax Dec 21 '10 at 14:43 This algorithm is mostly incorrect. Checking whether points are to the left/or right is O(n) already.

– pouncep Dec 21 '10 at 14:43.

You just need to find a point A that is on the left side of the line and another point that is on the right side. The remaining question is how to find that points quickly.

I think softsurfer.com/Archive/algorithm_0112/al... gives a clear O(log n) solution. Find the extremes in the direction perpendicular to the given line.

Take a random two points A and B from convex poligon. If they are on different side of the line, they intersect if they are on the same side, on both poligon parts (lets say clockwise AB and BA) do: create a line parallel to your line l that goes through A find point at maximal distance from l on the poligon, which is same as finding maximum in function that is first monotonically nondecreasing, and then monotonically nonincreasing. This can be done in O(log n) by ternary search if those two furthest points are on different side of your line, line intersects poligon, otherwise it doesn't By the way you can also find actual intersection points in O(log n) too.

Clever algorithm, +1. – Alexandre C. Dec 21 '10 at 20:06 The algorithm is invalid.

1) sequences of vertices AB and BA may not be valid for ternary search. 2) Having points with maximal distance from l on these polylines does not guarantee that the points are on opposite sides of the investigated line. Even when the line crosses the polygon.

– Juraj Blaho Dec 21 '10 at 20:20 Either distance should not be absolute (so that on one side is negative, on other positive), or for one side l goes through A and through B on another. – Sarmun Dec 21 '10 at 20:33 Non-absolute distance would help, but not in all cases. See jurajblaho.wz.cz/path2816.png .

The A->B in CW order is not valid for ternary search as it is increasing, decreasing and finally increasing. – Juraj Blaho Dec 21 '10 at 20:48 @create a line parallel to your line l that goes through A: If B is on this line then this algorithm fails... – pouncep Dec 21 '10 at 22:54.

Here's how I think about it: 1. Sorting is O(nlog(n)). 2.

After traversing half (or any fraction) of the vertices on the polygon, can you tell, in general, whether the line intersects the polygon? Not necessarily. I believe you need at least O(n) to do this.

– pouncep Dec 21 '10 at 22:45 No where do we know the polygon was given as a list of vertices that are adjacent. – pouncep Dec 21 '10 at 22:51.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.