Determinar las dimensiones de un rectángulo girado

14

Este fragmento de pila dibuja un rectángulo blanco con alias sobre un fondo negro con parámetros dados para sus dimensiones, posición, ángulo y las dimensiones de la cuadrícula:

<style>html *{font-family:Consolas,monospace}input{width:24pt;text-align:right;padding:1px}canvas{border:1px solid gray}</style><p>grid w:<input id='gw' type='text' value='60'> grid h:<input id='gh' type='text' value='34'> w:<input id='w' type='text' value='40'> h:<input id='h' type='text' value='24'> x:<input id='x' type='text' value='0'> y:<input id='y' type='text' value='0'> &theta;:<input id='t' type='text' value='12'>&deg; <button type='button' onclick='go()'>Go</button></p>Image<br><canvas id='c'>Canvas not supported</canvas><br>Text<br><textarea id='o' rows='36' cols='128'></textarea><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function toCart(t,a,n,r){return{x:t-n/2,y:r/2-a}}function vtx(t,a,n){return{x:n.x+t*Math.cos(a),y:n.y+t*Math.sin(a)}}function sub(t,a){return{x:t.x-a.x,y:t.y-a.y}}function dot(t,a){return t.x*a.x+t.y*a.y}function inRect(t,a,n,r){var e=sub(a,t),o=sub(a,n),l=sub(a,r),i=dot(e,o),v=dot(e,l);return i>0&&i<dot(o,o)&&v>0&&v<dot(l,l)}function go(){var t=parseInt($("#gw").val()),a=parseInt($("#gh").val()),n=parseFloat($("#w").val()),r=parseFloat($("#h").val()),e={x:parseFloat($("#x").val()),y:parseFloat($("#y").val())},o=Math.PI*parseFloat($("#t").val())/180,l=Math.sqrt(n*n+r*r)/2,i=Math.atan2(r,n),v=vtx(l,o+i,e),h=vtx(l,o+Math.PI-i,e),u=vtx(l,o-i,e),x=$("#c");x.width(t).height(a).prop({width:t,height:a}),x=x[0].getContext("2d");for(var s="",c=0;a>c;c++){for(var f=0;t>f;f++)inRect(toCart(f+.5,c+.5,t,a),v,h,u)?(s+="..",x.fillStyle="white",x.fillRect(f,c,1,1)):(s+="XX",x.fillStyle="black",x.fillRect(f,c,1,1));a-1>c&&(s+="\n")}$("#o").val(s)}$(go)</script>
( Versión JSFiddle )

La representación de texto tiene XXdonde haya un píxel negro en la imagen y ..donde sea que haya un píxel blanco. (Parece aplastado si lo están Xy .).

Escriba un programa que tome la representación de texto de un rectángulo producido por el Fragmento y genere el ancho y alto aproximados del rectángulo, ambos dentro de ± 7% del ancho y alto real .

Su programa debería funcionar para todos los rectángulos posibles que pueden ser dibujados por el fragmento, con las restricciones que:

  • El ancho y la altura del rectángulo son 24 como mínimo.
  • El ancho y la altura de la cuadrícula son 26 como mínimo.
  • El rectángulo nunca toca ni sale de los límites de la cuadrícula.

Por lo tanto, el rectángulo de entrada puede tener cualquier rotación, posición y dimensiones, y la cuadrícula puede tener cualquier dimensión, siempre que se cumplan las tres restricciones anteriores. Tenga en cuenta que, a excepción de las dimensiones de la cuadrícula, los parámetros Snippet pueden ser flotantes.

Detalles

  • Tome el rectángulo de texto sin formato como entrada o tome el nombre de archivo de un archivo que contiene el rectángulo de texto sin formato (a través de stdin o línea de comando). Puede suponer que el rectángulo de texto tiene una nueva línea final.
  • Puede suponer que el rectángulo de texto está hecho de dos caracteres ASCII imprimibles distintos que no sean Xy .si lo desea. (Las nuevas líneas deben seguir siendo nuevas).
  • Envíe el ancho y la altura medidos como enteros o flotantes a stdout en cualquier orden (ya que no hay forma de determinar cuál fue realmente con qué parámetro). Cualquier formato que muestra claramente las dos dimensiones está muy bien, por ejemplo D1 D2, D1,D2, D1\nD2, (D1, D2), etc.
  • En lugar de un programa, puede escribir una función que tome el rectángulo de texto como una cadena o el nombre del archivo e imprima el resultado normalmente o lo devuelva como una cadena o lista / tupla con dos elementos.
  • Recuerde eso XXo ..es un 'píxel' del rectángulo, no dos.

Ejemplos

Ex. 1

Parámetros: grid w:60 grid h:34 w:40 h:24 x:0 y:0 θ:12(Fragmentos predeterminados)

Entrada

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Salidas de ejemplo

  • 40 24
  • 24 40
  • [40.0, 24.0]
  • 42.8, 25.68 (+ 7%)
  • 37.2, 22.32 (-7%)

Ex. 2

Parámetros: grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 θ:38.5

Entrada

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX..................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX................................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Salidas de ejemplo

  • 24.0 24.5
  • 25.68 26.215 (+ 7%)
  • 22.32 22.785 (-7%)

Puntuación

El código más corto en bytes gana. Tiebreaker es la publicación más votada.

Pasatiempos de Calvin
fuente
¿No debería una solución cumplir con los requisitos de precisión para ser aceptada? El que aceptó está lejos para ciertos valores de entrada.
Reto Koradi

Respuestas:

6

Matlab, 226 bytes

La idea es simple: primero trato de averiguar cuánto se giró el rectángulo, luego gire la imagen en consecuencia para que el rectángulo esté en posición vertical. Luego, simplemente 'sumo' todos los píxeles en las columnas de la fila de manera específica e intento contar cuántas de las sumas están por encima del promedio (umbral simple) para determinar el ancho y la altura. Este método simple funciona sorprendentemente confiable.

¿Cómo puedo detectar el ángulo?

Solo intento cada paso (un grado cada uno) y sumo a lo largo de las columnas y obtengo un vector de sumas. Cuando el rectángulo está en posición vertical, idealmente debería obtener solo dos cambios repentinos en este vector de sumas. Si el cuadrado está en la punta, los cambios son muy graduales. Así que solo uso la primera derivada e intento minimizar el número de 'saltos'. Aquí puede ver una gráfica del criterio que estamos tratando de minimizar. Tenga en cuenta que puede ver los cuatro mínimos que corresponden a las cuatro orientaciones verticales posibles.

criterio de minimización

Reflexiones adicionales: no estoy seguro de cuánto se podría jugar al golf, ya que la búsqueda exhaustiva de ángulos requiere muchos caracteres y dudo que pueda lograrlo tan bien con métodos de optimización integrados, porque como puede ver, hay muchos mínimos locales que no estamos buscando Fácilmente puede mejorar la precisión (para imágenes grandes) por la elección de un tamaño más pequeño paso para el ángulo y la búsqueda sólo 90 ° en lugar de 360 ° por lo que podría reemplazar 0:360con 0:.1:90o somehting así. Pero de todos modos, para mí el desafío fue encontrar un algoritmo robusto en lugar de jugar al golf y estoy seguro de que las entradas de los idiomas de golf dejarán mi presentación muy atrás =)

PD: Alguien realmente debería derivar un lenguaje de golf de Matlab / Octave.

Salidas

Ejemplo 1:

 25    39

Ejemplo 2

 25    24

Código

Golfizado:

s=input('');r=sum(s=='n');S=reshape(s',nnz(s)/r,r)';S=S(:,1:2:end-2)=='.';m=Inf;a=0;for d=0:360;v=sum(1-~diff(sum(imrotate(S,d))));if v<m;m=v;a=d;end;end;S=imrotate(S,a);x=sum(S);y=sum(S');disp([sum(x>mean(x)),sum(y>mean(y))])

Sin golf:

s=input('');
r=sum(s=='n');              
S=reshape(s',nnz(s)/r,r)'; 
S=S(:,1:2:end-2)=='.';    
m=Inf;a=0;
for d=0:360;                 
    v=sum(1-~diff(sum(imrotate(S,d))));
    if v<m;
        m=v;a=d;
    end;
end;
S=imrotate(S,a);
x=sum(S);y=sum(S');
disp([sum(x>mean(x)),sum(y>mean(y))])
falla
fuente
7

CJam, 68 65 64 bytes

Esto se puede jugar un poco más de golf.

qN/2f%{{:QN*'.#Qz,)mdQ2$>2<".X"f#_~>@@0=?Qz}2*;@@-@@-mhSQWf%}2*;

Cómo funciona

La lógica es bastante simple, si lo piensas.

Todo lo que necesitamos de las X.combinaciones de entrada son 3 coordenadas de dos lados adyacentes. Así es como los obtenemos:

First

En cualquier orientación del rectángulo, el primero .en toda la entrada será una de las esquinas. Por ejemplo..

XXXXXXXXXXXXXX
XXXXXXX...XXXX
XXXX.......XXX
X............X
XX.........XXX
XXXX...XXXXXXX
XXXXXXXXXXXXXX

Aquí, la primera .está en la 2 nd línea, 8 º columna.

Pero eso no es todo, tenemos que hacer algunos ajustes y agregar el ancho de la .carrera en esa línea a las coordenadas para obtener la coordenada del extremo derecho.

Second

Si transponemos el rectángulo anterior (pivotado en nuevas líneas), entonces la esquina inferior izquierda toma el lugar del paso anterior. Pero aquí, no compensamos la .longitud del recorrido, ya que hubiéramos deseado obtener la coordenada inferior izquierda del borde de todos modos (que en forma transpuesta seguirá siendo la primera vez que se encuentre .)

Rest two

Para descansar dos coordenadas, simplemente volteamos horizontalmente, el rectángulo y realizamos los dos pasos anteriores. Una de las esquinas aquí será común de las dos primeras.

Después de obtener los 4, simplemente hacemos algunos cálculos matemáticos simples para obtener las distancias.

Ahora, este no es el método más preciso, pero funciona bien dentro del margen de error y para todas las orientaciones posibles del rectángulo.

Expansión de código (poco desactualizado)

qN/2f%{{:QN*'.#Q0=,)md}:A~1$Q='.e=+QzA@@-@@-mhSQWf%}2*;
qN/2f%                               e# Read the input, split on newlines and squish it
      {   ...   }2*                  e# Run the code block two times, one for each side  
{:QN*'.#Q0=,)md}:A~                  e# Store the code block in variable A and execute it
 :QN*                                e# Store the rows in Q variable and join by newlines
     '.#                             e# Get the location of the first '.'
        Q0=,)                        e# Get length + 1 of the first row
             md                      e# Take in X and Y and leave out X/Y and X%Y on stack
1$Q=                                 e# Get the row in which the first '.' appeared
    '.e=+                            e# Get number of '.' in that row and add it to X%Y
         QzA                         e# Transpose the rows and apply function A to get
                                     e# the second coordinate
            @@-@@-                   e# Subtract resp. x and y coordinates of the two corners
                  mh                 e# Calculate (diff_x**2 + diff_y**2)**0.5 to get 1 side
                    SQWF%            e# Put a space on stack and put the horizontally flipped
                                     e# version of the rows/rectangle all ready for next two
                                     e# coordinates and thus, the second side

Pruébalo en línea aquí

Optimizador
fuente
Pruebe con un tamaño de cuadrícula de 50x50, un tamaño de rectángulo de 45x45 y un ángulo -2. El error es de aproximadamente el 28%. Intenté un enfoque similar (fue mi idea inicial, antes de ver la suya), y conseguir que sea lo suficientemente preciso resulta ser más complicado de lo esperado, especialmente si los lados están cerca de horizontal / vertical. Funciona muy bien si están más cerca de la diagonal. Creo que esto requiere más lógica (por ejemplo, también la búsqueda de extremos en la dirección diagonal) o un enfoque completamente diferente.
Reto Koradi
@RetoKoradi Oh. Eso es solo porque todos los ángulos negativos necesitan el .ajuste de ancho en la segunda coordenada, en lugar de la primera. Arreglará. Debería ser una solución breve.
Optimizador
1
@RetoKoradi debería arreglarse ahora.
Optimizador
Pruebe el rectángulo de 40x24 con ángulo 0.
Reto Koradi
@RetoKoradi Buenos puntos. No aceptado por ahora.
Aficiones de Calvin
5

Python 3, 347337 bytes

Esto resultó más difícil de lo que esperaba. Trabajo en progreso...

def f(s):
 l=s.split('\n');r=range;v=sorted;w=len(l[0]);h=len(l);p=[[x,y]for x in r(w)for y in r(h)if'X'>l[y][x]];x,y=[sum(k)/w/h for k in zip(*p)];g=[[x/2,y]];d=lambda a:((a[0]/2-a[2]/2)**2+(a[1]-a[3])**2)**.5
 for i in r(3):g+=v(p,key=lambda c:~-(c in g)*sum(d(j+c)for j in g))[:1]
 print(v(map(d,[g[1]+g[2],g[2]+g[3],g[1]+g[3]]))[:2])

Define una función que ftoma la cadena como argumento e imprime el resultado en STDOUT.

Pyth, 87 84 82 81 75 72 71 bytes

(POSIBLEMENTE NO VÁLIDO, INVESTIGANDO CUANDO LLEGO A CASA)

Km%2d.zJf<@@KeThTG*UhKUKPSm.adfqlT2ytu+G]ho*t}NGsm.a,kNGJ3]mccsklhKlKCJ

Camino Sigue siendo demasiado larga. Básicamente un puerto del anterior. Amar la .adistancia euclidiana de Pyth . Toma entrada a través de STDIN y da salida a través de STDOUT. Espera que el carácter no rectangular sea en minúsculas x(bueno, cualquier cosa con valor ASCII 98 o más).

Algoritmo

Ambos usan el mismo algoritmo. Básicamente empiezo con una matriz que contiene el centro de masa del área del rectángulo. Luego agrego tres puntos a la matriz de todos los puntos en el rectángulo, eligiendo siempre el que tenga el máximo suma de distancias a los puntos que ya están en la matriz. El resultado es siempre tres puntos en diferentes esquinas del rectángulo. Luego calculo las tres distancias entre esos tres puntos y tomo las dos más cortas.

PurkkaKoodari
fuente
La solución Pyth no funciona en absoluto. Los dos ejemplos del OP dan los resultados en [33.0, 59.0]lugar de [40, 24]y en [39.0, 54.0]lugar de [24.0, 24.5].
Jakube
@Jakube Weird. Investigaré una vez que llegue a casa. Lamentablemente, estoy en un viaje de clase a Laponia hasta el 9 de junio.
PurkkaKoodari
Desafortunadamente, no llamaría a un viaje a Laponia ;-)
Jakube
0

Python 2, 342 bytes

import sys
r=[]
h=.0
for l in sys.stdin:w=len(l);r+=[[x*.5,h]for x in range(0,w,2)if l[x:x+2]=='..'];h+=1
x,y=.0,.0
for p in r:x+=p[0];y+=p[1]
n=len(r)
x/=n
y/=n
m=.0
for p in r:
 p[0]-=x;p[1]-=y;d=p[0]**2+p[1]**2
 if d>m:m=d;u,v=p
m=.0
for p in r:
 d=p[0]*v-p[1]*u
 if d>m:m=d;s,t=p
print ((u-s)**2+(v-t)**2)**.5+1,((u+s)**2+(v+t)**2)**.5+1

Esto se inspiró en el algoritmo de @ Pietu1998. Toma la idea de determinar una esquina como el punto más alejado del centro, pero difiere de allí:

  • Determino la segunda esquina como el punto con el producto cruzado más grande con el vector desde el centro hasta la primera esquina. Esto proporciona el punto con la mayor distancia desde la línea desde el centro hasta la primera esquina.
  • No es necesario buscar una tercera esquina, ya que es solo la imagen especular de la segunda esquina en relación con el centro.

Entonces el código sigue esta secuencia:

  • El primer bucle está sobre las líneas en la entrada y crea una lista rde puntos rectangulares.
  • El segundo bucle calcula el promedio de todos los puntos del rectángulo, dando el centro del rectángulo.
  • El tercer bucle encuentra el punto más alejado del centro. Esta es la primera esquina. Al mismo tiempo, resta el centro de los puntos en la lista, de modo que las coordenadas de los puntos son relativas al centro para el cálculo restante.
  • El cuarto bucle encuentra el punto con el producto cruzado más grande con el vector en la primera esquina. Esta es la segunda esquina.
  • Imprime la distancia entre la primera esquina y la segunda esquina, y la distancia entre la primera esquina y la imagen especular de la segunda esquina.
  • 1.0se agrega a las distancias porque los cálculos de distancia originales usan índices de píxeles. Por ejemplo, si tiene 5 píxeles, la diferencia entre el índice del último y el primer píxel fue de solo 4, lo que necesita una compensación en el resultado final.

La precisión es bastante buena. Para los dos ejemplos:

$ cat rect1.txt | python Golf.py 
24.5372045919 39.8329756779
$ cat rect2.txt | python Golf.py 
23.803508502 24.5095563412
Reto Koradi
fuente
0

Python 2, 272 bytes

Publicar esto como una respuesta separada ya que es un algoritmo completamente diferente al anterior:

import sys,math
y,a,r=0,0,0
l,t=[1<<99]*2
for s in sys.stdin:
 c=s.count('..')
 if c:a+=c;x=s.find('.')/2;l=min(l,x);r=max(r,x+c);t=min(t,y);b=y+1
 y+=1
r-=l
b-=t
p=.0
w,h=r,b
while w*h>a:c=math.cos(p);s=math.sin(p);d=c*c-s*s;w=(r*c-b*s)/d;h=(b*c-r*s)/d;p+=.001
print w,h

Este enfoque no identifica esquinas en absoluto. Se basa en la observación de que el tamaño (ancho y alto) del cuadro delimitador y el área del rectángulo girado son suficientes para determinar el ancho y el alto del rectángulo.

Si observa un boceto, es bastante fácil calcular el ancho ( wb) y el alto ( hb) del cuadro delimitador con w/ hel tamaño del rectángulo y pel ángulo de rotación:

wb = w * cos(p) + h * sin(p)
hb = w * sin(p) + h * cos(p)

wby hbse puede extraer directamente de la imagen. También podemos extraer rápidamente el área total adel rectángulo contando el número de ..píxeles. Como estamos tratando con un rectángulo, esto nos da la ecuación adicional:

a = w * h

Entonces tenemos 3 ecuaciones con 3 incógnitas ( w, hyp ), que es suficiente para determinar las incógnitas. Lo único malo es que las ecuaciones contienen funciones trigonométricas, y al menos con mi paciencia y mis habilidades matemáticas, el sistema no puede resolverse fácilmente analíticamente.

Lo que implementé es una búsqueda de fuerza bruta para el ángulo p. Una vez que pse da, las dos primeras ecuaciones anteriores se convierten en un sistema de dos ecuaciones lineales, que se pueden resolver wy h:

w = (wb * cos(p) - hb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))
h = (hb * cos(p) - wb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))

Con estos valores, podemos comparar w * hcon el área medida del rectángulo. Los dos valores serían idealmente iguales en algún momento. Por supuesto, esto no va a suceder en las matemáticas de coma flotante.

El valor de w * hdisminuye a medida que aumenta el ángulo. Entonces comenzamos en el ángulo 0.0, y luego incrementamos el ángulo en pequeños pasos hasta que la primera vez w * hsea ​​menor que el área medida.

El código solo tiene dos pasos principales:

  1. Extraiga el tamaño del cuadro delimitador y el área del rectángulo de la entrada.
  2. Recorra los ángulos candidatos hasta que se alcance el criterio de terminación.

La precisión de la salida es buena para rectángulos donde el ancho y la altura son significativamente diferentes. Se vuelve algo dudoso con rectángulos que son casi cuadrados y rotados cerca de 45 grados, apenas superando el obstáculo del error del 7% para el ejemplo de prueba 2.

El mapa de bits para el ejemplo 2 en realidad parece un poco extraño. La esquina izquierda se ve sospechosamente aburrida. Si agrego un píxel más en la esquina izquierda, ambos se ven mejor (para mí) y ofrecen una precisión mucho mejor para este algoritmo.

Reto Koradi
fuente