[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
"FlatLand Piano Movers, as part of their Total Quality Management project, has decided to focus on the job estimation process. Part of this process involves walking the proposed paths that are to be used to move a piano to see if it will fit through corridors and around corners. "
"Now this is harder than it might seem, since FlatLand is a 2-dimensional world. FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit ``T'' intersections. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don't have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. "
"Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos). Your team's job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor. "
(..... Info on input and output formats snipped)
Background & Techniques
Here's an interesting little problem from the 1989 Southern California Regional ACM International Collegiate Programming Contest.
We had to convert it from batch to interactive and add a few graphics of course. I spent a day trying to find an analytical solution to the problem but never quite got there. Too many triangles inside of triangles. So this is an empirical solution, i.e. turn the piano around the corner in small steps, keeping 2 piano corners against the outside of the corridor, and then check to see if the other side clears the inside corner.
I really need a good tool that will let me draw an annotated diagram without spending half a day. The best I have so far is a pencil and paper, so here's a scanned diagram of the geometry. It's not very readable, I had to reduce the size considerably, but maybe you can make some sense of it.
I borrowed the Intersect function from the Tangram program to see if a line from the outside to inside corner of the corridor (Line2) intersects the lower long side of the piano (Line1). If it does, all is well. If not, then the bottom long side of the piano has tried to cut the the corner and the piano is stuck. The diagram simply shows the derivation of the coordinates for Line1, If A is the angle that the piano has been rotated from vertical (and the exterior corner of the corridors is at [0,0] then the lower corners of the piano are at [L*sin(A)+W*(cos(A), W*sin(A)] and [W*cos(A), L*cos(A)+W*sin(A)]. For corridors of width CW1 and CW2, the inside corner (the other end of line segment Line2, is at [CW1,CW2].
There is some risk that the corner is clipped between 2 successive steps as we rotate around the corner and we miss that collision entirely. I've made the number of steps a variable in order to eliminate this as a practical issue, but it is would be a concern for any theoretical solution. Drawing the piano for many steps makes the turn images display as solid black, so I limited the drawing to every 10 degrees (or a collision) regardless of the number of steps checked.
If anyone comes up with the math (and a readable diagram) for the analytical solution, I sure would like to see it.
Running/Exploring the Program
Suggestions for Further Explorations
Find the analytical solution. I'm thinking we want the equation for the perpendicular distance from the inside corner of the corridor to the nearest long side of the piano and then find the minimum value of that function. If it stays positive, the piano clears the corner, otherwise it hits.
Copyright © 2000-2018, Gary Darby All rights reserved.