Scale one polygon to touch another polygon

4
votes

I'm looking to scale one concave polygon (specifically, applying a scaling affine transformation relative to the shape's centroid position to both axes) such that it intersects/touches another concave polygon. The polygons are each defined by a set of coordinates.

The illustration below shows an iterative approach: gradually scaling the polygon until the distance between the nearest points of the two polygons equals zero (I'm using the JTS library's DistanceOp.nearestPoints() for this).

Is there an non-iterative way to do this? A way to produce the required scaling factor immediately, without iteratively scaling and checking?

enter image description here

2
algorithmgeometrypolygoncomputational-geometryjts
I moved my comment into answer ... I got also idea on how to do the other case too so now it should work for any case. - Spektre
The nearest Euclidean distance is not appropriate to solve this problem. Because it is found in the direction that makes it shortest, while the scaling transform imposes the direction. - Yves Daoust

2 Answers

1
votes

I see it like this:

overview

The top triangle is the one to be scaled and the bottom is the one to touch. Let define some therms first. Let the scaled polygon (top) be A and the bottom be B Let the center of scaling be P0 (red point inside A) There are 2 cases (left and right). For both obtaining the touch point/edge (blue stuff in both A,B) position in both A and B is enough to compute the scale.

  1. edge of A touch vertex of B (left)

    simply cast ray from P0 through each vertex of A and then for each edge of A compute the perpendicular distance between selected edge of A and vertex of B that is inside the pie slice (two ray cast through the selected edge of A endpoints. Remember the closest one.

  2. Vertex of A touch edge or vertex of B (right)

    simply cast ray from P0 through each vertex of A and find closest intersection point with B (distance to P0).

So now we have a list of possible touch and we need to select the one that touches with smallest scale. So we need for each such touch know distance between P0 and selected vertex or edge (call it da) and distance between P0 and touch point in B (let call it db). From there applying scale changed da and we want da = db so:

da' = da*scale = db
scale = db/da

In some cases edge of A can touch edge of B however this case is handled by both #1,#2 because either edge of B is completely inside edge of A so the vertexes of B hit there too or the edge of B intersects ray and again the intersection is the same.

1
votes

You can "unroll" both shapes around the scaling center, i.e. convert to (distance, azimuth) coordinates. Both shapes can be decomposed in (possibly overlapping) sectors, and by a sorting/merging process, you can find the portions of sectors where a single edge of both polygons face each other. The smallest of all ratios of the distances to the endpoints will give you the solution. After the vertices are sorted, the merging process is linear in the total number of vertices.

enter image description here