Detecting the intersection of convex objects in the plane (Q1183506): Difference between revisions

An algorithm is developed (fragments are listed) to detect intersections of two convex regions of the plane whose boundaries may be piecewise curved. The algorithm requires \(C\log n\) operations, \(n\) is the number of curved segments, \(C\) is a constant depending on the complexity of the \(n\) curved segments. The algorithm is a completed version of that by the first author and \textit{D. G. Kirkpatrick} [Theor. Comput. Sci. 27, 241-253 (1983; Zbl 0553.68033)]. First, the detection of the intersection to two complex polygons is discussed, then the polygon is replaced by a splinegon (edges are replaced by spline curves). In the case of intersection a witness point is found. Otherwise a pair of parallel supporting lines delimiting horizontal separation may be determined.