0

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.

enter image description here

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
mpen
  • 272,448
  • 266
  • 850
  • 1,236
  • @mrmcgreg Not sure I can apply voronoi here. – mpen Dec 06 '20 at 00:16
  • Your question seems related to the medial axis transform, though the latter is not necessarily made of line segments. –  Dec 07 '20 at 12:44
  • @YvesDaoust Ahah! Thank you for giving me a search term. This looks relevant: https://stackoverflow.com/a/52796778/65387 I think it's even more complicated than that though, because the medial axis needs to connect to the points where the two polygons intersect. – mpen Dec 08 '20 at 04:02
  • Yes, your problem IS difficult. (Standard polygon clipping is already pretty uneasy.) –  Dec 08 '20 at 07:24

3 Answers3

1

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

Yonlif
  • 1,770
  • 1
  • 13
  • 31
  • I don't think two line segments will suffice, even for convex polygons (my input isn't limited to convex polys tho). Don't think two line segments is even correct for my drawn example; I think it's roughly equivalent to the number of points around the perimeter of the intersection poly. There should be a tiny bend near the top of my red line. – mpen Dec 06 '20 at 00:49
  • I think it is easy to proof that in your case two line segments is enough and that there is a solution, simply by saying that if the middle point is very close to the left then the area is not balanced in favor of left and if you move the middle point right so again - not balanced but this time to the right. so somewhere along the line between these two middle point we know that a balanced middle point exists. Also about non-convex polygon I did an edit, I might add a picture if it is unclear. Unless of course I miss understood your question. – Yonlif Dec 06 '20 at 00:52
0

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

Yonlif
  • 1,770
  • 1
  • 13
  • 31
  • I am not deleting the previous answer yet since you might still use it of a variant of it, if this solution fails as well. – Yonlif Dec 06 '20 at 01:04
  • Even if you can pair the vertices like that, I don't think you can just draw a straight line between them. I think you have to look at the two neighbouring edges and extend a straight line out down the middle. Then maybe you can down the same one the other side, and those two lines will intersect unless the lines happen to be parallel... [like this](https://stackoverflow.com/a/40464906/65387) but you have to move that circle from one of the poly to the other, which will draw a line down the middle. There's a name for this algo but I can't remember the name – mpen Dec 06 '20 at 02:05
0

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.

comply polygon bification

Tatarize
  • 10,238
  • 4
  • 58
  • 64