math - optimal algorithm if line intersects convex polygon -

i know if there faster algorithm o(n) detecting if line intersects convex polygon. know algorithm when check every edge of polygon if intersects line , if number of intersections odd or even, looking if there exists faster example in o (log n) complexity.

thanks

lhf's answer close correct. here version should fix problem his.

let polygon have vertices v0, v1, ..., vn in counterclockwise order. let points x0 , x1 on line.

note 2 things: first, finding intersection of 2 lines (and determining existence) can done in constant time. second, determining if point left or right of line can done in constant time.

we follow same basic idea of lhf o(log n) algorithm. base cases when polygon has 2 or 3 vertices. these can both handled in constant time.

determine if line (v0,v(n/2)) intersects line (x0,x1).

case 1: not intersect.

in case line interested in either left or right of line splitting polygon, , can recurse half of polygon. specifically, if x0 left of (v0,v(n/2)) vertices in right "half", {v0, v1, ... v(n/2)} on same side of (x0,x1) , know there no intersection in "half" of polygon.

case 2: intersect.

this case little trickier, can still narrow down intersection 1 "half" of polygon in constant time. there 3 subcases:

case 2.1: intersection between points v0 , v(n/2)

we done. line intersects polygon.

case 2.2: intersection closer v0 (that is, outside polygon on v0's side)

determine if line (x0,x1) intersects line (v0,v1).

if not done, line not intersect polygon.

if does, find intersection, p. if p right of line (v0, v(n/2)) recurse right "half" of polygon, {v0, v1, ..., v(n/2)}, otherwise recurse left "half" {v0, v(n/2), ... vn}.

the basic idea in case points in polygon 1 side of line (v0, v1). if (x0, x1) diverging away (v0, v1) on 1 side of intersection (v0, v(n/2)). know on side there can no intersection polygon.

case 2.3: intersection closer v(n/2)

this case handled case 2.2 using appropriate neighbor of v(n/2).

we done. each level, requires 2 line intersections, left-right check, , determining point on line. each recursion divides number of vertices 2 (technically divides them @ least 4/3). , runtime of o(log n).