Scale one polygon to touch another polygon

Question

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?

Answer 1

I have implemented the technique given in this answer. It more or less works, but the output is sensitive to how dense the vertices in the inputs are. I've had to densify to input vertices to =~1.0 for it to perform as expected.

Here is a Java implementation that uses JTS for geometry primitives:

package micycle.pgs.commons_experimental;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import org.locationtech.jts.algorithm.Angle;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Polygon;

public class PolyScale {

    /**
     * Calculates the minimum scaling factor required for polyA to intersect or
     * touch polyB.
     *
     * @param polyA the polygon to find the scaling factor for
     * @param polyB the static polygon that polyA should touch
     * @return the minimum scaling factor for polyA to intersect or touch polyB
     */
    public static double findMinScalingFactor(final Polygon polyA, final Polygon polyB) {
        final Coordinate centroid = polyA.getCentroid().getCoordinate();

        final List<Segment> segmentsA = createSegments(polyA, centroid);
        final List<Segment> segmentsB = createSegments(polyB, centroid);

        segmentsA.sort(Comparator.comparingDouble(s -> s.startAngle));
        segmentsB.sort(Comparator.comparingDouble(s -> s.startAngle));

        double minScalingFactor = Double.MAX_VALUE;
        PriorityQueue<Segment> activeSegmentsB = new PriorityQueue<>(Comparator.comparingDouble(s -> s.endAngle));

        int idxB = 0;
        final int nA = segmentsA.size();
        final int nB = segmentsB.size();

        for (int idxA = 0; idxA < nA; idxA++) {
            Segment segmentA = segmentsA.get(idxA);

            // Add segments from B that start before or at the same time as the current
            // segment from A
            while (idxB < nB && segmentsB.get(idxB).startAngle <= segmentA.startAngle) {
                activeSegmentsB.add(segmentsB.get(idxB));
                idxB++;
            }

            // Remove segments from B that have ended before the current segment from A
            // starts
            while (!activeSegmentsB.isEmpty() && activeSegmentsB.peek().endAngle <= segmentA.startAngle) {
                activeSegmentsB.poll();
            }

            if (!activeSegmentsB.isEmpty()) {
                Segment segmentB = activeSegmentsB.peek();
                if (segmentA.endAngle >= segmentB.startAngle) {
                    double scalingFactor = segmentB.distance / segmentA.distance;
                    minScalingFactor = Math.min(minScalingFactor, scalingFactor);
                }
            }
        }

        return minScalingFactor;
    }

    /**
     * Creates a list of segments for the given polygon with respect to the
     * centroid.
     *
     * @param polygon  the input polygon
     * @param centroid the centroid of the polygon
     * @return a list of segments representing the polygon
     */
    private static List<Segment> createSegments(Polygon polygon, Coordinate centroid) {
        List<Segment> segments = new ArrayList<>();
        Coordinate[] coordinates = polygon.getCoordinates();

        for (int i = 0; i < coordinates.length - 1; i++) {
            Coordinate start = coordinates[i];
            Coordinate end = coordinates[i + 1];

            double startAngle = Angle.angle(centroid, start);
            double endAngle = Angle.angle(centroid, end);
            double distance = start.distance(centroid);

            if (startAngle > endAngle) {
                double temp = startAngle;
                startAngle = endAngle;
                endAngle = temp;
            }

            segments.add(new Segment(startAngle, endAngle, distance));
        }

        return segments;
    }

    /**
     * Segment is a private class representing a segment of a polygon, defined by
     * its start and end angles and the distance from the centroid to the segment.
     */
    private static class Segment {

        final double startAngle;
        final double endAngle;
        final double distance;

        Segment(double startAngle, double endAngle, double distance) {
            this.startAngle = startAngle;
            this.endAngle = endAngle;
            this.distance = distance;
        }
    }

}

Answer 2

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.

Answer 3

I see it like this:

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.