Finding a common interior point for two polygons
Suppose I have overlapping polygons. None of them are convex. What is an efficient algorithm for finding a point within each of them and not on any of these boundaries?
Assuming they overlap and our polygons are defined by their sets of vertices in 3D.
+3
Charles taylor
source
to share
1 answer
You can use a variant of the Vatti polygon trimming algorithm . Watti's algorithm is a sweep algorithm that basically means scanning over the vertices of both polygons, from (say) left to right, as well as any intersections between their boundaries. Between the vertical lines through any of the next two of these "events", you then examine the trapezoids / triangles created by the polygons. Once you find a trapezoid that is part of both, you can simply pull out your centroid.
+4
Sneftel
source
to share