Finding the counterclockwise nearest point in time
Given a point q, direction w and point set P with convex hull known, give an algorithm to find the point in P that (q,w) touches first when rotated counterclockwise in time.
REMARK: We can assume that is sorted counterclockwise.
My idea would be the following: Since is sorted we can modify the approach of Binary Search to get the required bound. I suppose we have to test the angles between repeatedly, but I do not see how to formulate this clearly.
Answer & Explanation
To check the orientation of vs. w, we can use the cross product (after viewing our as subspace of ). This amounts to checking the sign of the expression
where is w rotated left by 90°.
All for which F(i) is positive are on the same side ("ahead") of the line given by point q and direction w, all with negative sign are on the other side ("behind"), and all with result 0 are on the line itself.
If q is inside the convex hull of P, we are looking for a change from negative to positive (or zero) sign along the cyclically ordered vertex sequence. Binary search is fine as soon as we have obtained one i with and one j with . Picking a random index will give us one of the signs, but it is not that trivial to find an index with the other sign. To do so, we may want to look for a maximizer or minimizer of . We may use that F switches between increasing and decreasing only once. So start with , , . If differnet signs occur at these, we are already done (up to the final binary search). So assume that F(i), F(j), F(k) are all negative and we want to look for a maximizer (or similarly: all positive and minimizer). By perhaps using cyclic rearrangement of i, j, k, we may assume that , i.e., the maximum among these three values is at the middle index. To facilitate distance calculations, I shall however assume that. Now we know that the maximizer is between i and k. We can pick between i and k and thereby reduce our interval of length to an interval of length at most if or if by picking those three consecutive out of four indices that have the maximum in the middle again. The essential trick is to pick l smartly so that the interval length decreases fast enough. Picking l such that it split [i,k] roughly by the Golden Ratio ensures this.
Most Popular Questions