Modelado del "sofá móvil"

Question

Creo que muchos de vosotros conocéis el problema del sofá móvil; si no es así, podéis encontrar la descripción del problema aquí .

En esta pregunta voy a girar la sala en forma de L en lugar de mover un sofá en la esquina. Al girar el salón $180^{\circ}$ lo que queda entre las paredes dará la forma del sofá. Así:

Los puntos de la sala tienen las siguientes propiedades:

\begin{eqnarray} A & = & \left( r\cos { \alpha } ,t\sin { \alpha } \right) \\ { A }' & = & \left( r\cos { \alpha } +\sqrt { 2 } \cos { \left( \frac { \pi }{ 4 } +\frac { \alpha }{ 2 } \right) } ,t\sin { \alpha } +\sqrt { 2 } \sin { \left( \frac { \pi }{ 4 } +\frac { \alpha }{ 2 } \right) } \right) \\ { B } & = & \left( r\cos { \alpha } -\frac { t\sin { \alpha } }{ \tan { \left( \frac { \alpha }{ 2 } \right) } } ,0 \right) \\ { B }' & = & \left( r\cos { \alpha } -\frac { t\sin { \alpha } }{ \tan { \left( \frac { \alpha }{ 2 } \right) } } -\frac { 1 }{ \sin { \left( \frac { \alpha }{ 2 } \right) } } ,0 \right) \\ C & = & \left( r\cos { \alpha } +t\sin { \alpha } \tan { \left( \frac { \alpha }{ 2 } \right) } ,0 \right) \\ { C }' & = & \left( r\cos { \alpha } +t\sin { \alpha } \tan { \left( \frac { \alpha }{ 2 } \right) } +\frac { 1 }{ \cos { \left( \frac { \alpha }{ 2 } \right) } } ,0 \right) \end{eqnarray}

Atención: $\alpha$ no es el ángulo de $AOC$ es algún ángulo $ADC$ donde $D$ cambia de ubicación en $x$ eje para $r\neq t$ . Lo digo porque las imágenes pueden crear confusión. De todas formas las cambiaré lo antes posible.

Podría considerar $r=f(\alpha)$ y $t=g(\alpha)$ pero para esta pregunta voy a tomar $r$ y $t$ como constantes. Si fueran funciones de $\alpha$ aparecerían algunas formas interesantes. Experimenté para diferentes funciones, sin embargo las áreas son más difíciles de calcular, por eso no voy a compartir. Tal vez en el futuro.

Rotamos la sala para $r=t$ en el ejemplo anterior:
En este caso:

1. el punto A se mueve en un semicírculo
2. La envolvente de líneas entre A' y C' es un arco de círculo. Hay que demostrarlo, pero supongo que es cierto para $r=t$ .

Si mi segunda suposición es correcta, el área del sofá es $A= 2r-\frac { \pi r^{ 2 } }{ 2 } +\frac { \pi }{ 2 } $ . La superficie máxima se alcanza cuando $r = 2/\pi$ y su valor es: $$A = 2/\pi+\pi/2 = 2,207416099$$

que coincide con el sofá de Hammersley. La forma también es similar o igual:

Ahora voy a aumentar $t$ con respecto a $r$ . Para $r=2/\pi$ y $t=0.77$ :

Bueno, esto parece El sofá de Gerver .

Creo que el área se puede maximizar encontrando las ecuaciones de los sobres por encima y por debajo del sofá. Mira esta pregunta donde @Aretino ha calculado el área de abajo $ABC$ .

No sé lo suficiente como para encontrar ecuaciones para los sobres. Tengo miedo de cometer errores. He considerado calcular el área contando el número de píxeles en ella, pero no es una buena idea porque para optimizar el área tengo que crear muchas imágenes.

Daré una recompensa de 200 para quien calcule el área máxima Como dije la parte más difícil del problema es encontrar las ecuaciones de los sobres. @Aretino lo hizo.

MÁS: ¿Podría ser el siguiente el sofá más largo donde $(r,t)=((\sqrt 5+1)/2,1)$ ?

Si quieres investigar más o utilizar la animación con fines educativos, aquí tienes el archivo de Geogebra: http://ggbm.at/vemEtGyj

---

Vale, he tenido algo de tiempo libre y he contado el número de píxeles en el sofá y estoy seguro de que tengo algo más grande que la constante de Hammersley.

Primero, hice una simulación para el sofá de Hammersley donde $r=t=2/\pi$ y exporté la imagen a png en 300 dpi (6484x3342 píxeles) y usando Gimp conté el número de píxeles que tienen exactamente el mismo valor. Para Hammersley obtuve $3039086$ píxeles.

Para el segundo caso $r=0.59$ y $t=0.66$ y tengo $3052780$ píxeles. Para calcular el área en este caso:

$$\frac{3052780}{3039086}(2/\pi + \pi/2)=2.217362628$$

que es ligeramente inferior a la constante de Gerver, que es $2.2195$ . Aquí está el sofá:

Answer 1

ATENCIÓN: esta respuesta utiliza la nueva parametrización de puntos introducida por el OP: \begin{eqnarray} A & = & \left( r\cos { \alpha } ,t\sin { \alpha } \right) \\ { A }' & = & \left( r\cos { \alpha } +\sqrt { 2 } \cos { \left( \frac { \pi }{ 4 } +\frac { \alpha }{ 2 } \right) } ,t\sin { \alpha } +\sqrt { 2 } \sin { \left( \frac { \pi }{ 4 } +\frac { \alpha }{ 2 } \right) } \right) \\ C & = & \left( r\cos { \alpha } +t\sin { \alpha } \tan { \left( \frac { \alpha }{ 2 } \right) } ,0 \right) \\ { C }' & = & \left( r\cos { \alpha } +t\sin { \alpha } \tan { \left( \frac { \alpha }{ 2 } \right) } +\frac { 1 }{ \cos { \left( \frac { \alpha }{ 2 } \right) } } ,0 \right) \end{eqnarray}

Otra parametrización, que también aparecía en una primera versión de esta pregunta, se utilizó en un respuesta anterior a una pregunta relacionada.

La forma interior del sofá está formada por la elipse de semiejes $r$ , $t$ y por la envoltura de las líneas $AC$ (aquí y en lo que sigue consideraré sólo la parte del sofá en el $x\ge0$ medio plano).

Las ecuaciones de las líneas $AC$ puede expresarse en función de $\alpha$ ( $0\le\alpha\le\pi$ ) como $F(x,y,\alpha)=0$ , donde: $$ F(x,y,\alpha)= -t y \sin\alpha \tan{\alpha\over2} - t \sin\alpha \left(x - r \cos\alpha - t \sin\alpha \tan{\alpha\over2}\right). $$ La ecuación de la envolvente se puede encontrar a partir de: $$ F(x,y,\alpha)={\partial\over\partial\alpha}F(x,y,\alpha)=0, $$ dando las ecuaciones paramétricas de la envolvente: $$ \begin{align} x_{inner}=& (r-t) \cos\alpha+\frac{1}{2}(t-r) \cos2\alpha+\frac{1}{2}(r+t),\\ y_{inner}=& 4 (t-r) \sin\frac{\alpha}{2}\, \cos^3\frac{\alpha}{2}.\\ \end{align} $$

No necesitamos considerar este sobre si $t<r$ porque en ese caso $y_{inner}<0$ . Si $t>r$ la envolvente se encuentra con la elipse en un punto $P$ el valor correspondiente de $\alpha$ se puede encontrar a partir de la ecuación $(x_{env}/r)^2+(y_{env}/t)^2=1$ , cuya solución $\alpha=\bar\alpha$ está dada por: $$ \begin{cases} \displaystyle\bar\alpha= 2\arccos\sqrt{t\over{t+r}}, &\text{for $t\le3r$;}\\ \displaystyle\bar\alpha= \arccos\sqrt{t\over{2(t-r)}}, &\text{for $t\ge3r$.}\\ \end{cases} $$

Los valores correspondientes $\bar\theta$ para el parámetro de la elipse se puede calcular fácilmente a partir de: $\bar\theta=\arcsin(y_{inner}(\bar\alpha)/t)$ : $$ \begin{cases} \displaystyle\bar\theta= \arcsin\frac{4 \sqrt{rt} (t-r)}{(r+t)^2}, &\text{for $t\le3r$;}\\ \displaystyle\bar\theta= \arcsin\frac{\sqrt{t(t-2 r)}}{t-r}, &\text{for $t\ge3r$.}\\ \end{cases} $$

Para $t\ge r$ entonces podemos representar la mitad del área bajo la forma interior del sofá como una integral: $$ {1\over2}Area_{inner}=\int_0^{2t-r} y\,dx= \int_{\pi/2}^{\bar\theta}t\sin\theta{d\over d\theta}(r\cos\theta)\,d\theta+ \int_{\bar\alpha}^{\pi} y_{inner}{dx_{inner}\over d\alpha}\,d\alpha. $$

Esto puede ser calculado explícitamente, aquí está por ejemplo el resultado para $r<t<3r$ : $$ \begin{align} {1\over2}Area_{inner}= {\pi\over4}(r^2-rt+t^2) +\frac{1}{48} (t-r)^2 \left[-24 \cos ^{-1}\frac{\sqrt{t}}{\sqrt{r+t}} +12 \sin \left(2 \cos^{-1}\frac{\sqrt{t}}{\sqrt{r+t}}\right)\\ +12 \sin \left(4 \cos^{-1}\frac{\sqrt{t}}{\sqrt{r+t}}\right) -4 \sin \left(6 \cos^{-1}\frac{\sqrt{t}}{\sqrt{r+t}}\right) -3 \sin \left(8 \cos^{-1}\frac{\sqrt{t}}{\sqrt{r+t}}\right) \right]\\ -2 r t {\sqrt{rt} |r^2-6 r t+t^2|\over(r+t)^4} -{1\over4} r t \sin ^{-1}\frac{4 \sqrt{rt} (t-r)}{(r+t)^2}\\ \end{align} $$

La forma exterior del sofá está formada por la línea $y=1$ y por la envoltura de las líneas $A'C'$ . Repitiendo los mismos pasos anteriores se pueden encontrar las ecuaciones paramétricas de la envolvente exterior: $$ \begin{align} x_{outer}&= (r-t) \left(\cos\alpha-{1\over2}\cos2\alpha\right) +\cos\frac{\alpha}{2}+{1\over2}(r+t)\\ y_{outer}&= \sin\frac{\alpha}{2} \left(-3 (r-t) \cos\frac{\alpha}{2} +(t-r) \cos\frac{3 \alpha}{2}+1\right)\\ \end{align} $$ Esta curva se une a la línea $y=1$ para $\alpha=\pi$ si $t-r\le\bar x$ , donde $\bar x=\frac{1}{432} \left(17 \sqrt{26 \left(11-\sqrt{13}\right)}-29 \sqrt{2 \left(11-\sqrt{13}\right)}\right)\approx 0.287482$ . En ese caso el punto de intersección tiene coordenadas $(2t-r,1)$ y el área bajo la forma exterior del sofá se puede encontrar fácilmente: $$ {1\over2}Area_{outer}={1\over3}(r+2t)+{\pi\over4}(1-(t-r)^2) $$ Si, por el contrario, $t-r>\bar x$ entonces hay que encontrar el valor del parámetro $\alpha$ en la que la envolvente se encuentra con la línea, resolviendo la ecuación $y_{outer}=1$ y buscando la solución positiva más pequeña. Esto debe hacerse, en general, mediante algún método numérico.

El área del sofá se puede encontrar entonces como $Area_{tot}=Area_{outer}-Area_{inner}$ . Utilicé Mathematica para dibujar un gráfico de contorno de esta área, en función de $r$ (eje horizontal) y $t$ (eje vertical):

Hay un claro máximo en la región alrededor de $r = 0.6$ y $t = 0.7$ . En esta región se pueden utilizar las expresiones simples para $Area_{inner}$ y $Area_{outer}$ dado anteriormente, para encontrar el valor exacto del máximo. Una búsqueda numérica da $2.217856997942074266$ para el área máxima, alcanzada para $r=0.605513519698965$ y $t=0.6678342468712839$ .

Answer 2

Esto no es una respuesta a la pregunta planteada, sólo un esquema y un ejemplo de cómo calcular la envolvente (y por tanto el área) numéricamente, de forma bastante eficiente.

El código parece funcionar, pero no está probado, ni se acerca a lo óptimo en el plano algorítmico; es sólo un esbozo inicial para explorar el problema en cuestión.

El sofá es simétrico con respecto al $x$ por lo que sólo tenemos que considerar el eje (positivo $x$ ) medio plano. Si utilizamos $\alpha$ para la rotación, $\alpha \in [0, \pi]$ Los muros inicialmente verticales (en el lado derecho) son los únicos que debemos considerar. Para simplificar, utilizaré $r_x$ y $r_y$ para los radios (OP utilizó $r$ y $t$ respectivamente).

La ecuación para los puntos que forman la pared lateral cercana ( $t \ge 0$ ) es $$\vec{p}_{nw}(t, \alpha) = \begin{cases} x_{nw}(t, \alpha) = r_x \cos(\alpha) + t \sin(\alpha/2)\\ y_{nw}(t, \alpha) = r_y \sin(\alpha) - t \cos(\alpha/2)\end{cases}$$

Configuración $x_{nw}(t, \alpha) = x$ , resolviendo para $t$ y sustituyendo en $y_{nw}(t, \alpha)$ produce $$y_n(x, \alpha) = r_y \sin(\alpha) + \frac{r_x \cos(\alpha) - x}{\tan(\alpha/2)}$$ Debido a que la pared cercana comienza con un ángulo $\alpha$ Sólo hay que tener en cuenta $x \ge x_n(0,\alpha)$ . Podemos hacerlo en la práctica definiendo $$\alpha_0(x) = \left\lbrace\begin{matrix} r_y\sqrt{1 - \left(\frac{x}{r_x}\right)^2},&x \lt r_x\\ 0,&x \ge r_x\end{matrix}\right.$$ y sólo considerando $\alpha_0 \le \alpha \le \pi$ al evaluar $y_n(x,\alpha)$ . Alcanza su máximo cuando su derivada, $$\frac{d y_n(x,\alpha)}{d \alpha} = \frac{x - r_x}{1 - \cos(\alpha)} - (r_x - r_y)\cos(\alpha)$$ es cero. Puede haber dos raíces reales, $$\begin{align}\alpha_1(x) &= \arccos\left(\frac{\sqrt{ (r_x - r_y)(5 r_x - r_y - 4 x)} + (r_x - r_y)}{2 ( r_x - r_y )}\right)\\ \alpha_2(x) &= \pi - \arccos\left(\frac{\sqrt{ (r_x - r_y)(5 r_x - r_y - 4 x)} - (r_x - r_y)}{2 ( r_x - r_y )}\right)\end{align}$$ En resumen, la pared cercana es el máximo de uno, dos o tres valores: $y_n(x,\alpha_0)$ ; $y_n(x,\alpha_1)$ si $\alpha_0 \lt \alpha_1 \lt \pi$ y $y_n(x,\alpha_2$ ) si $\alpha_0 \lt \alpha_2 \lt \pi$ .

Para la pared lateral, los puntos son $$\vec{p}_f(t, \alpha) = \begin{cases} x_f(t) = r_x \cos(\alpha) + \cos(\alpha/2) + \sin(\alpha/2) + t \sin(\alpha/2)\\ y_f(t) = r_y \sin(\alpha) + \sin(\alpha/2) - \cos(\alpha/2) - t \cos(\alpha/2)\end{cases}$$ El primer término añadido representa la anchura del pasillo y el segundo la altura del mismo, ambos $1$ . Configuración $x_f(t, \alpha) = x$ , resolviendo para $t$ y sustituyendo en $y_f(t, \alpha)$ produce $$y_f(x, \alpha) = \frac{(r_x + r_y - 2x)\cos(\alpha/2) + (r_x - r_y)\cos(3\alpha/2) + 2 }{2 \sin(\alpha/2)}$$ Su derivado es $$\frac{d y_f(x, \alpha)}{d \alpha} = \frac{rx - x + \cos(\alpha/2)}{\cos(\alpha) - 1} - \cos(\alpha)(r_x - r_y)$$ Puede tener hasta cuatro raíces reales (las raíces de $4(r_x-r_y)\chi^4 - 6(r_x-r_y)\chi^2 - \chi + (r_x - r_y) + (x - r_y) = 0$ ). Aunque tiene soluciones analíticas, son desagradables, así que prefiero utilizar una búsqueda binaria en su lugar. Utilizo el hecho de que el signo (y los ceros) de la derivada son los mismos que los de la función más simple $$d_f(x, \alpha) = \cos(\alpha)\left(\cos(\alpha)-1\right)(r_x - r_y) - \cos(\alpha/2) - r_x + x$$ que no tiene polos en $\alpha=0$ o $\alpha=\pi$ .

Aquí hay un ejemplo de implementación en C:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>

#define PI 3.14159265358979323846

static double near_y(const double x,
                     const double xradius,
                     const double yradius)
{
    double y = (x < xradius) ? yradius * sqrt(1.0 - (x/xradius)*(x/xradius)) : 0.0;
    if (xradius != yradius) {
        const double a0 = (x < xradius) ? acos(x/xradius) : 0.0;
        const double s  = (xradius - yradius)*(5*xradius - yradius - 4*x);
        if (s >= 0.0) {
            const double r = 0.5 * sqrt(s) / (xradius - yradius);
            if (r > -1.5 && r < 0.5) {
                const double a1 = acos(r + 0.5);
                if (a1 > a0 && a1 < PI) {
                    const double y1 = yradius * sin(a1) + (xradius * cos(a1) - x) / tan(0.5 * a1);
                    if (y < y1)
                        y = y1;
                } 
            }
            if (r > -0.5 && r < 1.5) {
                const double a2 = PI - acos(r - 0.5);
                if (a2 > a0 && a2 < PI) {
                    const double y2 = yradius * sin(a2) + (xradius * cos(a2) - x) / tan(0.5 * a2);
                    if (y < y2)
                        y = y2;
                }
            }
        }
    }
    return y;
}

Arriba, near_y() encuentra el máximo $y$ coordina el alcance de la pared cercana en el punto $x$ .

static double far_y(const double x,
                    const double xradius,
                    const double yradius)
{
    const double rxy = xradius - yradius;
    const double rx = xradius - x;
    double       retval = 1.0;
    double       anext = 0.0;
    double       dnext = x - 1.0 - xradius;
    double       acurr, dcurr, y;

    /* Outer curve starts at min(1+xradius, 2*yradius-xradius). */
    if (x < 1.0 + xradius && x < yradius + yradius - xradius)
        return 1.0;

    while (1) {
        acurr = anext;
        dcurr = dnext;
        anext += PI/1024.0;
        if (anext >= PI)
            break;
        dnext = cos(anext)*(cos(anext) - 1.0)*rxy - cos(anext*0.5) - rx;

        if ((dcurr < 0.0 && dnext > 0.0) ||
            (dcurr > 0.0 && dnext < 0.0)) {
            double amin = (dcurr < 0.0) ? acurr : anext;
            double amax = (dcurr < 0.0) ? anext : acurr;
            double a, d;
            do {
                a = 0.5 * (amin + amax);
                d = cos(a)*(cos(a)-1.0)*rxy - cos(a*0.5) - rx;
                if (d < 0.0)
                    amin = a;
                else
                if (d > 0.0)
                    amax = a;
                else
                    break;
            } while (amax > amin && a != amin && a != amax);
            y = (cos(0.5*a)*(0.5*(xradius+yradius)-x) + cos(1.5*a)*rxy*0.5 + 1.0) / sin(0.5*a);
            if (retval > y) {
                retval = y;
                if (y <= 0.0)
                    return 0.0;
            }
        } else
        if (dcurr == 0.0) {
            y = (cos(0.5*acurr)*(0.5*(xradius+yradius)-x) + cos(1.5*acurr)*rxy*0.5 + 1.0) / sin(0.5*acurr);
            if (retval > y) {
                y = retval;
                if (y <= 0.0)
                    return 0.0;
            }
        }
    }
    return retval;
}

Arriba, far_y() encuentra el mínimo $y$ coordenada para la pared más lejana en $x$ . la pared lejana llega al mismo punto. Calcula el signo de la derivada para 1024 valores de $\alpha$ y utiliza una búsqueda binaria para encontrar la raíz (y el extremo $y$ ) siempre que la derivada sea cero.

Con las dos funciones anteriores, sólo tenemos que dividir la anchura total del sofá ( $1 + r_x$ ) a rodajas, evalúe el $y$ coordenadas para cada corte, multiplicar el $y$ diferencia de coordenadas por la anchura del doble de la rebanada (ya que sólo calculamos una mitad del sofá), para obtener una estimación del área del sofá (utilizando la regla del punto medio para la integral):

double sofa_area(const unsigned int xsamples,
                 const double       xradius,
                 const double       yradius)
{
    if (xradius > 0.0 && yradius > 0.0) {
        const double dx = (1.0 + xradius) / xsamples;
        double       area = 0.0;
        unsigned int i;
        for (i = 0; i < xsamples; i++) {
            const double x = dx * (0.5 + i);
            const double ymin = near_y(x, xradius, yradius);
            const double ymax = far_y(x, xradius, yradius);
            if (ymin < ymax)
                area += ymax - ymin;
        }        
        return 2*dx*area;
    } else
        return 0.0;
}

Por lo que he encontrado, el mejor es sofa_area(N, 0.6055, 0.6678) = 2.21785 (con N 5000 , más grande N produce estimaciones más precisas; he comprobado hasta N = 1,000,000 ).

La curva que hace la esquina interior ( $(x_{wn}(0,\alpha), y_{wn}(0,\alpha))$ , $0 \le \alpha \le \pi$ ) se cuece en el interior near_y() y far_y() funciones. Sin embargo, sería posible sustituir $y_{wn}(0,\alpha)$ con una función más complicada (quizás una escala polinómica $r_y$ para que sea $1$ en $\alpha = 0, \pi$ ?), si se revalorizan las funciones anteriores. Personalmente uso Maple o Mathematica para las matemáticas, así que lo difícil, en realidad, es pensar en una función adecuada que permita "deformar" la trayectoria elíptica de formas interesantes, sin que las ecuaciones anteriores sean demasiado difíciles o lentas de implementar.

También se podría optimizar el propio código C. (No me refiero a micro-optimizaciones; me refiero a cosas como el uso de la regla del trapecio para la integral, un mejor enfoque de búsqueda de raíces para far_y() etc.)