Clever Geek Handbook

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


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.



enter image description here

+4


source






More articles:


All Articles