Splitting a polygon by another polygon

1
votes

I need an algorithm for splitting a (convex) polygon (let's call it base polygon). The polygon should be splitted into several smaller polygons by another polygon's edges (let's call this one the splitting polygon). I know there exist algorithms for clipping a polygon (f.e. the Sutherland-Hodgman algorithm), but these algorithms discard the vertices that are lying outside of the splitting polygon instead of creating new polygons with them. I don't want to clip a polygon, i want to split it into several small parts. I know the answer seems quite obvious because I would just have to extend the existing algorithms. The problem is that I can't figure out a nice and performant way of doing this. Are there existing algorithms that describe how to best split a polygon in a performant way? There has to be a simple solution for this problem that I can't figure out at the moment.

1
algorithmmathgraphics
Can we assume the clipping polygon is not complex? – Floris
Yes, the clipping polygon is always convex. – user3067395
"these algorithms discard the vertices that are lying outside of the splitting polygon instead of creating new polygons with them" Not for any good reason; you could easily modify them to save the bits on the other side of the line. – David Eisenstat
That's correct. The hard part is to determine which of the vertices outside of the splitting polygon should be connected to a new one. I'm stuck in finding a fast way to connect all the outlying vertices. – user3067395
Are both the subject and window (splitting) polygons convex ? – Yves Daoust

1 Answers

1
votes

You can see this problem as that of finding the intersection of the subject polygon and the complement of the window polygon. So you can use the standard Surtherland-Hodgman algorithm for that purpose, taking two precautions:

  1. swap the roles of the subject and the window (actually your window is not convex as you consider its complement, only the subject is convex),

  2. embed the window polygon in a large bounding box that covers both polygons, and consider the box as a polygon with a hole.

    enter image description here

Example: the subject polygon is the rectangle and the window is the pentagon. Form the green polygon (larger rectangle with a hole) and clip it inside the rectangular (convex) window. The result of the clipping is in blue.

With some extra care, it should be possible to do without the large bounding box.