3

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.

Charles Taylor
  • 686
  • 6
  • 23
  • 2D, 3D, nD? Is it predefined that the polygons actually overlap? – Amit May 28 '15 at 18:48
  • Yes, we're assuming they overlap. – Charles Taylor May 28 '15 at 19:05
  • @Amit if they're >2D, then either they're coplanar and the problem can be reduced to 2D, nonintersecting which is trivial, or intersect along a line which reduces the problem to 1D. – Sneftel May 28 '15 at 19:07
  • @Sneftel - you're right of course, but that doesn't change the importance of the question if you want to provide a complete answer. (Unfortunately, Mr. Taylor decided not to answer that part) – Amit May 28 '15 at 19:12
  • "Overlapping" is meaningless for 3D polygons. –  May 29 '15 at 07:36
  • I'm assuming they're coplanar and that their borders intersect. I think that's a pretty meaningful notion of "Overlapping". – Charles Taylor May 29 '15 at 15:56

1 Answers1

4

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.

enter image description here

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • Can these easily extended to being an algorithm that finds the overlapping polygon? – Charles Taylor May 28 '15 at 19:14
  • Sure! I mean, that's what Vatti's algorithm does -- the "just find a centroid" thing is my simplification for the "I just want one point" use-case. Note, however, that the intersection region may consist of *multiple* non-connected polygons. – Sneftel May 28 '15 at 19:21
  • Oh, and if you don't want to do the work yourself (and scanline algorithms are notoriously fiddly to implement properly), check out [Clipper](http://www.angusj.com/delphi/clipper.php). – Sneftel May 28 '15 at 19:23