Polygon clipping: How to clip both polygons down middle?

Question

I've seen several implementations of "polygon clipping" that allow you to 'subtract' one polygon from another, but I'm looking for something a little different.

How can I clip both polygons by subtracting an even amount from each, such that they no longer overlap?

e.g. in the picture below, the pink and red polygons are overlapping. I want to slice them both along the red line so that they're no longer overlapping.

I drew the red line by hand down the center of the intersection. It should be equidistant to the edges of the [intersection] polygon on either side. I believe this also means the left and right halves have equal area.

The polygons are not necessarily convex. They're user drawn, so they can be concave, but there won't be holes. Technically they can self-intersecting, but I should probably find another algorithm to clean or discard those ones.

I hope that's clear enough. Does this algorithm have a name? Better yet if it has an implementation in JS.

---

Best idea I have so far is:

1. Compute the intersection of the two polygons, using one of
   1. Martinez-Rueda-Feito
   2. Sutherland–Hodgman
   3. Weiler–Atherton clipping algorithm
   4. Vatti clipping algorithm
2. Compute the "center line" (haven't figured this out yet)
3. Use polygon clipping again to clip off the halves from each poly

Answer 1

You could just sort of do a sweep line to find the center. Each time you hit a point, you'll have two active edges (you could have more but always even. Then you merely travel in the direction of the crossproduct of the active edges. You can use a scanline to see if you're inside the polygon. Then if you hit a merge or split node you'll need to recalculate but basically the scanline will hit some even number of segments. And your segments between them are just the cross product of the two.

Note, this algorithm gets a bit weird when you consider complex polygons. Weird, but not inexplicable.

Answer 2

Completely different direction from my previous answer (I missed the It should be equidistant to the edges of the [intersection] polygon on either side part - sorry).

Let's look at the case that the right part of the intersection polygon has the same number of vertices as the left part of the intersection polygon (And assuming convex - if not convex solve for each convex polygon). In this case draw a line between each two corresponding vertices, i.e. the two top ones and the two bottom ones in your example, and draw a line from the top intersection point to the middle of the lines you drew. It can be shown that it solves the problem.

Now for the trick to generalize the solution - Simply add dummy vertices wherever you want to make the number of vertices equal in each side.

I used a lot of "top" and "bottom" here but actually you just need the lines to never intersect, choose whatever method you want to pick from where you start.

Once again,
Good luck

Answer 3

Let's build on the Best idea you presented, I am assuming you found all the vertices of the polygon.

First calculate the surface area of the polygon using a formula to calculate this using only the vertices. Now we assume the separating lines can be generated using only two lines, I believe this is a reasonable assumption if both of you polygons are convex (Need a proof, probably with Intermediate value theorem).

So we call the point in the middle (that creates the two lines) a := (x_a, x_b), now Creating two polygons - one with only half of the points (in your case all the points to the right of the red line and a), and the second with the rest of the points where a and the intersection points are in both polygons.

We know that the sum area of these polygons is equal to the precalculated sum, so we have 1 equation with 2 parameters (x_a, x_b), solving this will create a line on which the middle point can exist.

Now choose a random point on this line (inside on the intersection polygon :) ) and you are done.

Edit:
If the polygon is not convex you can cat it to parts so it will be and apply the algorithm of each part.
Also this algorithm has no name or implementation that I am aware of.

Good luck