Suppose I have overlapping polygons. Neither is necessarily convex. What's an efficient algorithm to find a point interior to both of them and not on either's boundary?
Assuming that they overlap, and our polygons are defined by their sets of vertices in 3D.
A variant of the Vatti polygon clipping algorithm can be used. Vatti's algorithm is a scanline algorithm, which basically means scan over the vertices of both polygons, from (say) left to right, as well as over any intersections between their boundaries. Between the vertical lines passing through any consecutive two of these "events", you then examine the trapezoids/triangles created by the polygons. Once you find a trapezoid which is part of both, you can just output its centroid.