Ray Shooting Amidst Convex Polygons in 2D
Pankaj K. Agarwal, Micha Sharir · Journal of Algorithms · 1996
We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log2 m log2 n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m2+n)log m) andO((m2+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(⌈m/[formula]⌉1+ε log2 n) time, for any ε>0.