Determine the Dimensions of a Rotated Rectangle

Question

This Stack Snippet draws an aliased white rectangle on a black background given parameters for its dimensions, position, angle, and the grid dimensions:

<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>

^{(JSFiddle Version)}

The text representation has XX wherever there is a black pixel in the image and .. wherever there is a white pixel. (It looks squished if they are X and ..)

Write a program that takes the text representation of a rectangle produced by the Snippet and outputs the approximate width and height of the rectangle, both to within ± 7% of the actual width and height.

Your program should work for effectively all possible rectangles that can be drawn by the snippet, with the constraints that:

• The rectangle width and height are 24 at minimum.
• The grid width and height are 26 at minimum.
• The rectangle never touches nor goes out of the grid bounds.

So the input rectangle may have any rotation, position, and dimensions, and the grid may have any dimensions, as long as the three constraints above are met. Note that except for the grid dimensions, the Snippet parameters can be floats.

Details

• Take the raw text rectangle as input or take the filename of a file that contains the raw text rectangle (via stdin or command line). You may assume the text rectangle has a trailing newline.
• You may assume the text rectangle is made from any two distinct printable ASCII characters other than X and . if desired. (Newlines must stay newlines.)
• Output the measured width and height as integers or floats to stdout in any order (since there's no way to determine which one actually went with which parameter). Any format that clearly shows the two dimensions is fine, e.g. D1 D2, D1,D2, D1\nD2, (D1, D2), etc.
• Instead of a program, you may write a function that takes the text rectangle as a string or the filename to it and prints the result normally or returns it as a string or list/tuple with two elements.
• Remember that XX or .. is one 'pixel' of the rectangle, not two.

Examples

Ex. 1

Parameters: grid w:60 grid h:34 w:40 h:24 x:0 y:0 θ:12 (Snippet defaults)

Input

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

Example Outputs

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

Ex. 2

Parameters: grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 θ:38.5

Input

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

Example Outputs

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

Scoring

The shortest code in bytes wins. Tiebreaker is highest voted post.

Answer 1

Matlab, 226 bytes

The idea is simple: First I try to find out how much the rectangle was turned, then turn the image accordingly such that the rectangle is upright. Then I just 'sum' up all the pixels in the row columns sperately and try count how many of the sums are above than average (simple thresholding) for determining the width and height. This simple method works surprisingly reliably.

How can I detect the angle?

I just try each step (one degree each) and sum along the columns and get a vector of sums. When the rectangle is upright, I should ideally get only two sudden changes in this vector of sums. If the square is on the tip, the changes are very gradual. So I just use the first derivative, and try to minimize the number of 'jumps'. Here you can see a plot of the criterion we are trying to minimize. Notice that you can see the four minima which corresponds to the fours possible upright orientations.

Further thoughts: I am not sure how much it could be golfed as the exhausive angle search takes a lot of characters and I doubt you could achieve that so well with built in optimization methods, because as you can see there are a lot of local minima that we are not looking for. You can easily improve the accuracy (for big pictures) by choosing a smaller step size for the angle and only search 90° instead of 360° so you could replace 0:360 with 0:.1:90 or somehting like that. But anyways, for me the challenge was more finding a robust algorithm rather than golfing and I am sure the entries of the golfing languages will leave my submission far behind=)

PS: Someone should really derive a golfing language from Matlab/Octave.

Outputs

Example 1:

 25    39

Example 2:

 25    24

Code

Golfed:

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))])

Ungolfed:

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))])

Answer 2

CJam, 68 65 64 bytes

This can be golfed a little more..

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

How it works

The logic is pretty simple, if you think about it.

All we need from the input X. combinations is 3 coordinates of two adjacent sides. Here is how we get them:

First

In any orientation of the rectangle, the first . in the whole of the input is going to be one of the corners. For example..

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

Here, the first . is in the 2^nd line, 8^th column.

But that's not it, we have to do some adjustment and add the width of the . run on that line to the coordinates to get the coordinate of the right end.

Second

If we transpose the above rectangle (pivoted on newlines), then the bottom left corner takes the above step's place. But here, we do not compensate for the . run length as we would have wished to get the bottom left coordinate of the edge anyways (which in transposed form will still be the first encountered .)

Rest two

For rest two coordinates, we simply flip horizontally, the rectangle and perform the above two steps. One of the corners here will be common from the first two.

After getting all 4, we simply do some simple math to get the distances.

Now this is not the most accurate method, but it works well within the error margin and well for all possible orientations of the rectangle.

Code expansion (bit outdated)

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

Try it online here

Answer 3

Python 3, 347 337 bytes

This turned out harder than I expected. Work in progress...

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])

Try it online! Comes with a test harness that tries 100 random valid rectangles. Note: The test harness seems to produce some errors and prints the corresponding grids. It seems like these cases all have rather round corners - an issue which seems to be caused by the grid generation code, which I translated from the original snippet.

Defines a function f taking the string as an argument and printing the result to STDOUT.

Pyth, 87 84 82 81 75 72 71 bytes (broken)

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

This seems to have been broken in 2015. Since then, something in Pyth has changed so that the old versions now crash and the new ones return [0, 0]. Right now I have neither the slightest idea what this monstrosity does nor the time to figure it out. I'm leaving it here as crossed-out for historical reasons.

Way Still too long. Basically a port of the previous. Loving Pyth's .a Euclidean distance. Takes input via STDIN and gives output via STDOUT. Expects the non-rectangle character to be lower-case x (well, anything with ASCII value 98 or more).

Algorithm

Both of these use the same algorithm. I basically start with an array containing the center of mass of the rectangle area. I then add three points to the array of all points in the rectangle, always choosing the one with maximum sum of distances to the points already in the array. The result is always three points in different corners of the rectangle. I then just calculate all the three distances between those three points and take the two shortest ones.

Answer 4

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

This took inspiration from @Pietu1998's algorithm. It takes the idea of determining one corner as the point farthest from the center, but differs from there:

• I determine the second corner as the point with the largest cross product with the vector from center to first corner. This gives the point with the largest distance from the line from center to first corner.
• There's no need to search for a third corner, since it's just the mirror image of the second corner relative to the center.

So the code follows this sequence:

• First loop is over the lines in the input, and builds a list r of rectangle points.
• Second loop calculates the average of all rectangle points, giving the center of the rectangle.
• Third loop finds the point farthest from the center. This is the first corner. At the same time, it subtracts the center from the points in the list, so that the point coordinates are relative to the center for the remaining calculation.
• Fourth loop finds the point with the largest cross product with the vector to the first corner. This is the second corner.
• Prints out the distance between first corner and second corner, and distance between first corner and mirror image of second corner.
• 1.0 is added to the distances because the original distance calculations use pixel indices. For example, if you have 5 pixels, the difference between the index of the last and first pixel was only 4, which needs compensation in the final result.

Precision is quite good. For the two examples:

$ cat rect1.txt | python Golf.py 
24.5372045919 39.8329756779
$ cat rect2.txt | python Golf.py 
23.803508502 24.5095563412

Answer 5

Python 2, 272 bytes

Posting this as a separate answer since it's an entirely different algorithm than my previous one:

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

This approach does not identify corners at all. It is based on the observation that the size (width and height) of the bounding box and the area of the rotated rectangle are sufficient to determine the width and height of the rectangle.

If you look at a sketch, it is fairly easy to calculate the width (wb) and height (hb) of the bounding box with w/h the size of the rectangle, and p the rotation angle:

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

wb and hb can be extracted directly from the image. We can also quickly extract the total area a of the rectangle by counting the number of .. pixels. Since we're dealing with a rectangle, this gives us the additional equation:

a = w * h

So we have 3 equations with 3 unknowns (w, h and p), which is enough to determine the unknowns. The only bummer is that the equations contain trigonometric functions, and at least with my patience and math skills the system cannot easily be solved analytically.

What I implemented is a brute force search for the angle p. Once p is given, the first two equations above become a system of two linear equations, which can be resolved for w and 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))

With these values, we can then compare w * h with the measured area of the rectangle. The two values would ideally be equal at some point. This is of course not going to happen in floating point math.

The value of w * h decreases as the angle increases. So we start at angle 0.0, and then increment the angle by small steps until the first time w * h is less than the measured area.

The code only has two main steps:

1. Extract size of bounding box and rectangle area from input.
2. Loop over candidate angles until termination criterion is reached.

The precision of the output is good for rectangles where the width and height are significantly different. It gets somewhat iffy with rectangles that are almost square and rotated close to 45 degrees, just barely clearing the 7% error hurdle for test example 2.

The bitmap for example 2 actually looks slightly odd. The left corner looks suspiciously dull. If I add one more pixel at the left corner, it both looks better (to me), and gives a lot better precision for this algorithm.