Intersection of a line and a convex hull of points cloud

Abstract

An algorithm for intersection a line and a convex hull of points cloud is presented. The algorithm doesn't require the convex hull construction. The points cloud can be arbitrary and not sorted, no topology, face list or edge list is known. The algorithm uses only vertices coordinates. Standard transformation of coordinates is performed and the points cloud is bisected by two perpendicular planes. Yielded 1D points set lies at the line. Bounds of the set are intersection points of the points cloud and the line. The algorithm was compared against the obvious algorithm which uses intersection of the line and all possible faces (sets of three points). Presented algorithm is much faster than the obvious one. © 2013 R. P. Koptelov and A. M. Konashkova.