CODEWITHSUNDEEP
algorithmgeometrycomputational-geometryconvex-optimization
grom
grom

Reputation: 63

The largest aligned rectangular with fixed aspect ratio in an arbitrary convex polygon?

How to calculate the width / height of the largest aligned rectangular with fixed aspect ratio in an arbitrary convex polygon?

The examples of such rectangles (red) in the different convex polygons (black) are presented on this image:

are presented on this image.

I found different papers on subject, but they are not fit to set of my limitations. That's weird, because they should significally simplify the algorithm, but unfortunately I didn't found any clue of it.

Upvotes: 4

Views: 1153

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65447

Fixed ratio does simplify the problem since now there's a linear program.

You want to find x1, y1, x2, y2 to maximize x2 − x1 subject to the constraints that (x2 − x1) h = w (y2 − y1) where the aspect ratio is w:h, and for each linear inequality defining the convex polygon, each of the points (x1, y1), (x1, y2), (x2, y1), (x2, y2) satisfy it.

For example, consider this convex polygon: Polygon

The linear program for the rectangle with four points (x_1, y_1), (x_1, y_2), (x_2, y_2), (x_2, y_1), aspect ratio r = w / h and inscribed to the polygon above will be following:

Linear program

In theory, there are specialized algorithms for low-dimensional linear programming that run in linear time. In practice, you can throw a solver at it. If you want to code your own, then you could do the simplex method, but gradient descent is even simpler.

First let's get rid of the equality constraint and a variable by maximizing z over variables x, y, z subject to the point-in-polygon constraints for x1 = (x − w z), y1 = (y − h z), x2 = (x + w z), y2 = (y + h z). Second let's trade in those constraints for an objective term. Normally a point-in-polygon constraint will look like (signed distance to half-plane) ≤ 0. Instead we're going to apply a penalty term to the objective. Let α > 0 be a parameter. The new term is −exp(α (signed distance to half plane)). If the signed distance is negative (the point is inside half-plane), then the penalty will go to zero as α goes to infinity. If the signed distance is positive, then the penalty goes to minus infinity. If we make α large enough, then the optimal solution of the transformed problem will be approximately feasible.

This is what it looks like in Python. I'm not a continuous optimization expert, so caveat emptor.

# Aspect ratio.
w = 3
h = 2

# Represented as intersection of half-spaces a*x + b*y - c <= 0 given below as
# (a, b, c). For robustness, these should be scaled so that a**2 + b**2 == 1,
# but it's not strictly necessary.
polygon = [(1, 1, 20), (1, -2, 30), (-2, 1, 40)]

# Initial solution -- take the centroid of three hull points. Cheat by just
# using (0, 0) here.
x, y, z = (0, 0, 0)

from math import exp

# Play with these.
alpha = 10
rate = 0.02

for epoch in range(5):
    for iteration in range(10 ** epoch, 10 ** (epoch + 1)):
        # Compute the gradient of the objective function. Absent penalties, we
        # only care about how big the rectangle is, not where.
        dx, dy, dz = (0, 0, 1)
        # Loop through the polygon boundaries, applying penalties.
        for a, b, c in polygon:
            for u in [-w, w]:
                for v in [-h, h]:
                    term = -exp(alpha * (a * (x + u * z) + b * (y + v * z) - c))
                    dx += alpha * a * term
                    dy += alpha * b * term
                    dz += alpha * (a * u + b * v) * term
        x += rate * dx
        y += rate * dy
        z += rate * dz
    print(x, y, z)

Upvotes: 4

user1196549
user1196549

Reputation:

Hint:

WLOG the rectangle can be a square (stretch space if necessary).

Then the solution is given by the highest point of the distance map to the polygon, in the Chebyshev metric (L∞). It can be determined from the medial axis transform, itself obtained from the Voronoi diagram.

Upvotes: 2

Related Questions