Calculer le plus grand rectangle dans un rectangle pivoté

Question

J'essaie de trouver la meilleure façon de calculer le plus grand (dans la région) rectangle qui peut être contenue à l'intérieur d'une rotation du rectangle.

Quelques images devraient aider (je l'espère) dans la visualisation de ce que je veux dire:

La largeur et la hauteur de l'entrée du rectangle est donné, et si est l'angle de rotation. La sortie rectangle n'est pas tourné ou incliné.

Je vais en bas de la longwinded route que je ne suis même pas sûr si elle va gérer le cas du coin (no pun intended). Je suis certain qu'il y est une solution élégante à ce. Des conseils à donner?

EDIT: La sortie rectangle points n'ont pas forcément besoin de toucher à l'entrée des rectangles à bords. (Merci à M. E)

Answer 1

Je suis juste venu ici à la recherche pour la même réponse. Après de frémir à la pensée de tant de mathématiques impliqués, j'ai pensé que je pourrais recourir à une demi-instruits deviner. Gribouille un peu je suis arrivé à l' (intuitive et peut-être pas entièrement exact) conclusion que le plus grand rectangle est proportionnelle à l'extérieur rectangle résultant, et de ses deux coins opposés se situent à l'intersection des diagonales du rectangle extérieur avec le côté le plus long de la rotation d'un rectangle. Pour les places, les diagonales et les côtés ferais... je pense que je suis assez heureux avec cela et il va maintenant commencer à brosser les toiles d'araignée de mon rusty trig compétences (pathétique, je sais).

Mise à jour mineure... Réussi à faire quelques calculs trigonométriques. C'est pour le cas lorsque la Hauteur de l'image est plus grande que la Largeur.

La mise à jour. Obtenu la chose entière de travail. Voici quelques code js. Il est connecté à un programme plus large, et la plupart des variables sont hors de la portée des fonctions et sont modifiés directement dans les fonctions. Je sais que ce n'est pas bon, mais je suis en utilisant ce dans une situation d'isolement, où il n'y aura pas de confusion avec d'autres scripts: expurgée

---

J'ai pris la liberté de nettoyage du code et en l'extrayant d'une fonction:

function getCropCoordinates(angleInRadians, imageDimensions) {
    var ang = angleInRadians;
    var img = imageDimensions;

    var quadrant = Math.floor(ang / (Math.PI / 2)) & 3;
    var sign_alpha = (quadrant & 1) === 0 ? ang : Math.PI - ang;
    var alpha = (sign_alpha % Math.PI + Math.PI) % Math.PI;

    var bb = {
        w: img.w * Math.cos(alpha) + img.h * Math.sin(alpha),
        h: img.w * Math.sin(alpha) + img.h * Math.cos(alpha)
    };

    var gamma = img.w < img.h ? Math.atan2(bb.w, bb.h) : Math.atan2(bb.h, bb.w);

    var delta = Math.PI - alpha - gamma;

    var length = img.w < img.h ? img.h : img.w;
    var d = length * Math.cos(alpha);
    var a = d * Math.sin(alpha) / Math.sin(delta);

    var y = a * Math.cos(gamma);
    var x = y * Math.tan(gamma);

    return {
        x: x,
        y: y,
        w: bb.w - 2 * x,
        h: bb.h - 2 * y
    };
}

J'ai rencontré quelques problèmes avec l' gamma-calcul, et l'a modifié pour tenir compte de la direction dans laquelle la boîte d'origine est la plus longue.

-- Magnus Hoff

Answer 2

En essayant de ne pas rompre avec la tradition en mettant la solution du problème comme une image:)

---

Edit: Troisième équations est faux. La bonne est:

3.w * cos(α) * X + w * sin(α) * Y - w * w * sin(α) * cos(α) - w * h = 0

Pour résoudre le système d'équations linéaires, vous pouvez utiliser la règle de Cramer, ou de la méthode de Gauss.

Answer 3

Tout d'abord, nous nous occupons de le cas trivial où l'angle est égal à zéro ou à un multiple de pi/2. Puis le plus grand rectangle est le même que le rectangle d'origine.

En général, le rectangle intérieur dispose de 3 points sur les limites du rectangle extérieur. Si elle ne le fait pas, alors il peut être déplacé de façon que l'un des vertex sera sur le fond, et un sommet sera sur la gauche. Vous pouvez ensuite agrandir le rectangle intérieur jusqu'à ce que l'un des deux sommets restants atteint une limite.

Nous appelons les côtés du rectangle extérieur R1 et R2. Sans perte de généralité, nous pouvons supposer que R1 <= R2. Si nous appelons les côtés du rectangle intérieur H et W, alors nous avons que

H cos a + W sin a <= R1
H sin a + W cos a <= R2

Puisque nous avons au moins 3 points sur les frontières, au moins l'un de ces inégalités doivent être en fait une égalité. Nous allons utiliser la première. Il est facile de voir que:

W = (R1 - H cos a) / sin a

et si la région est

A = H W = H (R1 - H cos a) / sin a

Nous pouvons prendre les dérivés wrt. H et de demander à être égale à 0:

dA/dH = ((R1 - H cos a) - H cos a) / sin a

La résolution pour la H et en utilisant l'expression de W, ci-dessus, nous constatons que:

H = R1 / (2 cos a)
W = R1 / (2 sin a)

En substituant ceci dans la deuxième inégalité devient, après quelques manipulations,

R1 (tan a + 1/tan a) / 2 <= R2

Le facteur sur le côté gauche est toujours au moins 1. Si l'inégalité est satisfaite, alors nous avons la solution. Si elle n'est pas satisfaite, alors la solution est la seule qui satisfasse à la fois les inégalités que les égalités. En d'autres termes: c'est le rectangle qui touche tous les quatre côtés du rectangle extérieur. C'est un système linéaire avec 2 inconnues, qui est facilement résolu:

H = (R2 cos a - R1 sin a) / cos 2a
W = (R1 cos a - R2 sin a) / cos 2a

En termes de coordonnées d'origine, on obtient:

x1 = x4 = W sin a cos a
y1 = y2 = R2 sin a - W sin^2 a 
x2 = x3 = x1 + H
y3 = y4 = y2 + W

Answer 4

Edit: Mon Mathematica réponse ci-dessous est faux - j'étais à la résolution d'un problème légèrement différent de ce que je pense que vous êtes vraiment se poser.

Pour résoudre le problème, vous êtes vraiment se poser, je voudrais utiliser l'algorithme suivant(s):

Sur le Maximum de Vide Rectangle Problème

En utilisant cet algorithme, désigner un nombre fini de points qui forment la frontière de la rotation de rectangle (peut-être 100 ou alors, et assurez-vous d'inclure les coins) - ce serait l'ensemble S il est décrit dans le papier.

.

.

.

.

.

Dans un souci de postérité, j'ai quitté mon premier post ci-dessous:

L'intérieur du rectangle avec la plus grande zone sera toujours le rectangle où le moyen inférieur coin du rectangle (le coin près de l'alpha sur votre schéma) est égale à la moitié de la largeur du rectangle extérieur.

J'ai un peu triché et utilisé Mathematica pour résoudre l'algèbre pour moi:

À partir de ce que vous pouvez voir que la superficie maximale de l'intérieur du rectangle est égale à 1/4 de la largeur^2 * cosécante de l'angle de fois la sécante de l'angle.

Maintenant j'ai besoin de comprendre quelle est la valeur x du coin en bas pour cette condition optimale. À l'aide de la Résoudre fonction dans mathematica sur ma zone de formule, je reçois le texte suivant:

Ce qui montre que la coordonnée x du coin en bas est égal à la moitié de la largeur.

Maintenant, juste pour m'en assurer, je vais allez tester notre réponse empirique. Avec les résultats ci-dessous vous pouvez voir qu'en effet, le quartier le plus haut de tous mes tests (certainement pas exhaustive, mais vous obtenez le point), c'est quand le coin en bas de la valeur de x = la moitié de l'extérieur du rectangle de largeur.

Answer 5

@Andri ne fonctionne pas correctement pour l'image où width > height été testé. J'ai donc corrigé et optimisé son code de cette manière (avec seulement deux fonctions trigonométriques):

 calculateLargestRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var sina = Math.sin(ang);
    var cosa = Math.cos(ang);
    var sinAcosA = sina * cosa;
    var w1 = w0 * cosa + h0 * sina;
    var h1 = w0 * sina + h0 * cosa;
    var c = h0 * sinAcosA / (2 * h0 * sinAcosA + w0);
    var x = w1 * c;
    var y = h1 * c;
    var w, h;
    if (origWidth <= origHeight) {
        w = w1 - 2 * x;
        h = h1 - 2 * y;
    }
    else {
        w = h1 - 2 * y;
        h = w1 - 2 * x;
    }
    return {
        w: w,
        h: h
    }
}
 

METTRE À JOUR

J'ai aussi décidé d'afficher la fonction suivante pour le calcul proportionnel du rectangle:

 calculateLargestProportionalRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var c = w0 / (h0 * Math.sin(ang) + w0 * Math.cos(ang));
    var w, h;
    if (origWidth <= origHeight) {
        w = w0 * c;
        h = h0 * c;
    }
    else {
        w = h0 * c;
        h = w0 * c;
    }
    return {
        w: w,
        h: h
    }
}