Asymptotically optimal algorithm to compute if a line intersects a convex polygon

An O(n) algorithm to detect if a line intersects a convex polygon consists in checking if any edge of the polygon开发者_运维问答 intersects the line, and look if the number of intersections is odd or even.

Is there an asymptotically faster algorithm, e.g. an O(log n) one?

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

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.

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.

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.