Scaling DrawingVisuals algorithm

Question

I'm trying to implement an algorithm which would find the best possible scale coefficient and the best possible angle to position the figure in such a way that it does not overlap with the edges of the container and it takes the best angle(defined by the angle in which the figure is as wide as possible).I'm using a DrawingVisual to represent the figure.

What I have in mind right now was a brute force check which looks something like this :

set scale to 1;
while (overlaps with end points(in set (verticies) { !exists vertex which position.x > window.width && position.y > window.height && position.X < 0 && position.Y < 0)){
for 0 : 360 {
   check whether at this angle all the points are aligned correctly,if yes
   save the result as the last valid tuple(angle and scale) and continue
   }
   increase scale by a constant 
}

If anyone is aware of such an implementation already available online please do share, otherwise give me a word about what you think of that what I'm currently thinking on.

Edit : You can always consider that the center point of the figure is located on the center of the screen.

M Oehm · Accepted Answer

Edit I've edited the post and propose another solution.

It is not quite clear what the "figure" and the edges of the "container" are. I assume that the container is a kind of canvas with an axis-aligned rectangle as surface.

Then you can fit the figure in three steps:

Determine the convex hull of your figure. This depends on the nature of your figure, of course, but if your figure is already a polygon, this is as simple as throwing out all concave points.
Find the optimum rotation angle, see below. (I had previously suggested to find the enclosing rectangle with the minimum-area with the rotating calipers algorithm, but this doesn't give an optimum solution here.)
Fit the rotated figure to your container by scaling and translating it.

The optimum rotation angle is the angle at which the rotated figure's axis-aligned bounding box has an aspect ratio that is closest to the aspect ratio of the container. Your idea of a brute-force solution is a good start, but it can be refined:

You don't have to increase the scale succesively; once you have found an optimum angle, you can easily calculate the scale from the dimensions of the rotated figure's bounding box and the container.
You don't need to test all angles up to 360°. It is enough to check a quarter-circle: If ϑ is a solution, then ϑ + 180° is the same solution, only rotated. You can check for solutions in the range of 90° to 180° by checking the bounding box of ϑ - 90° with height and width exchanged.
By probing the range of solutions in one-degree steps, you will get only a rough solution. A better approach might be to probe ever smaller ranges of angles with decreasing angle steps. (You can fit the exact values of the search intervals according to your required accuracy and performance. Performace should be okay, because the convex hull usually has only a few points.)
There is no need to rotate about the center of the screen. Just rotate about the origin and make the polygon fit in the container in the last step.

Here's an implementation in Javascript. (You asked for C#, but I'm not familiar with that. You should have no trouble to adopt this code to other languages, though)

/*
 *      Return left, right, top and bottom points of a polygon
 */
function bounds(poly) {
    bx = { 
        left: poly[0],
        right: poly[0],
        top: poly[0],
        bottom: poly[0]
    };

    for (var i = 1; i < poly.length; i++) {
        var p = poly[i];

        if (p.x < bx.left.x) bx.left = p;
        if (p.x > bx.right.x) bx.right = p;
        if (p.y < bx.top.y) bx.top = p;
        if (p.y > bx.bottom.y) bx.bottom = p;
    }

    return bx;
}    

/*
 *      Return a transformed (rotated, scaled, offset) polygon 
 */
function transform(poly, deg, scale, dx, dy) {
    var phi = Math.PI * deg / 180;
    var c = Math.cos(phi);
    var s = Math.sin(phi);

    var rot = [];

    for (var i = 0; i < poly.length; i++) {
        var p = poly[i];
        var x = scale * (c * p.x - s * p.y + dx);
        var y = scale * (s * p.x + c * p.y + dy);
        rot.push(new Pt(x, y));
    }

    return rot;
}

/*
 *      Return a polygon rotated by deg degrees.
 */
function rotate(poly, deg) {
    return transform(poly, deg, 1, 0, 0);
}

/*
 *      Assess a rotation of the polygon and update the optimum
 *      solution so far if necessary.
 */
function assess(opt, poly, angle, ratio) {
    var rot = rotate(poly, angle);
    var box = bounds(rot);
    var w = box.right.x - box.left.x;
    var h = box.bottom.y - box.top.y;
    var r = w / h;

    if (Math.abs(r - ratio) < opt.delta) {
        opt.delta = Math.abs(r - ratio);
        opt.angle = angle;
        opt.width = w;
        opt.height = h;
        opt.left = box.left.x;
        opt.top = box.top.y;
    }

    if (Math.abs(1/r - ratio) < opt.delta) {
        opt.delta = Math.abs(1/r - ratio);
        opt.angle = angle + 90;
        opt.width = h;
        opt.height = w;
        opt.left = -box.bottom.y;
        opt.top = box.left.x;
    }
}

/*
 *      Fit polygon inside a rectangle of width x height
 */
function fit(poly, width, height) {
    var ratio = width / height;
    var opt = { delta: 1.0e+30 };

    for (var i = 0; i < 90; i += 10) assess(opt, poly, i, ratio);

    for (d = 1; d > 0.002; d *= 0.1) {
        var a = opt.angle;

        for (var i = a - 9*d; i < a + 9.5*d; i += d) {
            assess(opt, poly, i, ratio);
        }
    }

    var sx = width / opt.width;
    var sy = height / opt.height;

    return transform(poly, 
        opt.angle, Math.min(sx, sy),
        -opt.left, -opt.top);
}

This iterative approach may not always find the optimum solution, but it will find one that is good enough.

Scaling DrawingVisuals algorithm

Answers (2)

Related Questions