I need some help with a mathematical problem. A geometry problem to be specific.
Congratulations on reading this far. One of the features of Perfect Table Plan is the drawing of tables and seats on scale floor plans. The user can optionally specify how many seats and let the software calculate a sensible table size so that all the seats touch the table and their neighbouring seats. This saves the user time and produces tidy looking floor plans. Calculating the table size is trivial for square or rectangular tables. It is a bit more complicated for circular tables. But, after a bit of head scratching, I managed to work it out. Placing the seats around the circle is then trivial.
But my customers keep asking for oval (elliptical) tables, with that callous disregard customers have for how difficult a problem might be [1]. Here is the problem.
We have an ellipse E with axes A and B surrounded by N identical circles of diameter D. Each circle touches the ellipse and each of its 2 neighbours at one point, as shown above. Given N, D and the ratio A/B what is A? Given A, what is the angle THETA subtended by the centre of each circle to the centre of E?
I doubt there is an exact analytic solution to this problem. I have some vague ideas about how to tackle it. I can work out the approximate circumference C’ of an ellipse E’ that passes through the centre of all the seats (axes A+D and B+D) using the formula derived by Indian mathematical prodigy Ramunajan.
From this we should be able to work back to A. As N becomes large C’ will tend to N*D. For smaller N, C’ will diverge from N*D so we might have to use an iterative method[2] to calculate A, but we can use the approach above to get a starting value for A and then iterate numerically from there.
I am less sure about how to work out the angle THETA for each circle. But if we pre-compute the angles of, say, 100 equally spaced points around E we could use these to interpolate the position of N circles where N is <= 100. It might be OK to place the first circle at THETA=0 for all values of N>0, I’m not sure.
Several hours on Google didn’t turn up a solution. Surely I am not the only person to have tackled this problem in human history? Can anyone point me at a workable solution? Preferably with code.
Alternatively can somebody write me the code to solve the problem? Maybe there is someone out there with a mathematical background that would relish the challenge? I am prepared to pay for working code that I can use in PerfectTablePlan (a few hundred dollars, negotiable).
- To simplify things we can assume a fixed value of A/B, say 1.5 .
- It needs to work for N from 1 to 99.
- The solution doesn’t need to be exact, but it has to look OK to the human eye. No overlaps and no big gaps.
- Low values of N might need to set up as special cases. E.g. it isn’t possible to get all the circles to touch if N <=6 (and possibly higher values of N depending on A/B).
- The solution must be returned in a reasonable time, ideally under 0.001 seconds and definitely less than 0.01 seconds. It can store pre-computed values, e.g. in an array. But it mustn’t require excessive memory.
- The code needs to be in a form I can easily convert to C++. C, Java, BASIC or Python should be fine. Haskell not so much.
- Ideally it should come with a simple GUI that allows me to set the value of N and D and see the result visually.
If you want to be paid I need to be able to buy all rights to the code and it mustn’t be released into the public domain (i.e. don’t post the code on this blog). In the unlikely event I get more than one set of working code, I will pay for the best solution according to the above criteria. Contact me for more details.
[1] I love them all really.
[2] For example Newton-Rhapson.
**** UPDATE ****
See https://successfulsoftware.net/2008/08/25/a-mathematical-digression-revisited/ .
Successful Software 
Good luck with that one!
It made my head hurt to reading it….
Why not just C = N * D then solve for A?
C’=N*D only for large N. It is going to be too big for most values of N I am interested in. Also that still doesn’t address how to calculate the angle THETA of each circle – probably the more difficult part of the problem.
A few comments after playing with it quickly…
The method of assuming C’=ND is relatively simple to work through and solve for D (or A or whatever) but as mentioned it only approximates well for large N and/or non-eccentric ellipses. Unless you doing N=50 for a near circle it won’t give adequate results.
I would try an iterative approach of finding D for a given value of A, B and N. Place the first outer circle on the C’ ellipse (anywhere but might as well be on an axis). Solve the equation to find the location of the next circle so it just touches. Note that the intersection of adjacent circles is not on the outer C’ ellipse (look at eccentric ellipses and see where the circles touch). Continue adding circles until you reach the first circle (i.e., either very close or intersect it). Adjust your value of D (or whatever you are solving for) up/down and repeat until your final error is small enough.
Not a particularily fast or easy solution but it should work. As you add circles you can calculate the theta for each one (which will vary depending on where on the ellipse the circle is placed). If you are working with limited values of A, B, and N it would probably be better to precompute the values and do a lookup/interpolation when you need them.
Interesting problem…if I had more time I’d try a full solution for you. Hope this little bit helps you some.
>Solve the equation to find the location of the next circle so it just touches
Can that be done analytically? Or does it also have to be done iteratively?
I guess a honking great look-up table might be OK. But it would need to contain 5,150 values (N angles + A for each N from 1 to 100). I could make N smaller. I don’t think anyone really uses tables with 100 seats.
> Can that be done analytically? Or does it also have to be done iteratively?
I was trying Dave’s method too.
I think that “finding the exact location of the next circle so that it just touches” is equivalent to solving the following equation for x …
a(x**2) + sqrt(1 – (x/b)**2) = c
… where a, b, and c are some constants which depend on the relative sizes of the axes of the ellipse and of the circles, and on the location of the previous (or, by induction, of the first) circle on the ellipse.
I remembered enough geometry, trig, and simple algebra to derive the above equation from the problem, but not enough to solve that equation (solving that equation means finding x given values for a, b, and c).
Solving theta might be the easy part.
Given a location {x,y} on the ellipse, I think that the location of the centre of the circle which touches the ellipse at {x,y} might be …
{ x*{ra+1} , y*(r+1) }
… where ‘a’ is the ratio (B/A) and ‘r’ is the ratio (D/A).
You didn’t say what you want theta to be a function of … but it’s easy to derive theta given location of the centre of the circle (and this gives you the location of the centre of the circle expressed as a function of {x,y} where {x,y} is any point on the ellipse).
Given that a PC can do better than 10 GFLOPS, then your 0.01 seconds allows 100 MFLOP.
If you do, say, 100 of Dave’s “Adjust your value of D (or whatever you are solving for) up/down and repeat until your final error is small enough” iterations, that’s 1 MFLOP per iteration.
Assuming 50 seats, that’s 20 KFLOP per seat/iteration.
20 KFLOP seems like it ought to be enough, for calculating the constants in my primitive equation and then solving it via Newton/Ralphson.
How much for a pointer to the solution? :-)
>How much for a pointer to the solution?
A free licence of PerfectTablePlan. ;0)
I am only paying out money for a working solution in code.
I was j/k. I’m writing a app called Cartesia for teaching geometry and it occurred to me that using equations to calculation elliptical gears with the correct parameters would do the trick. I haven’t found the general solution yet (not a mechanical engineer) but if you google elliptical gears you should have all you need.
Good luck. Spent an hour enjoying this problem… thanks!
I’m inclined to take on this problem if you’re serious. I think it would be an excellent problem set for my app. If you haven’t solved it in a day or two, let me know. Two heads, etc.
This equation …
a(x**2) + sqrt(1 – (x/b)**2) = c
… resolves to a quartic of the form …
x^4 + mx^2 + n = 0
… which is solvable analytically. So I think that the answer to your question “Can that be done analytically?” is “Yes” (and that 20 KFLOP per chair per iteration is far more than necessary): i.e. given any set of dimensions (A, B, and D) it’s possible to quickly and accurately calculate exactly how many [fractional] chairs (N) will fit round the table.
As for the part that’s being done iteratively … if we’re looking for M chairs and instead find N chairs, I think that if we try again with chairs of size M/N then this iteration would converge.
Elliptical gears use the ratio between the circumference of the ellipse and the other gear (which can be round or elliptical). The problem you have is that you want to define an even number of cords in an ellipse that’s the radius of the chair bigger than the table.
This isn’t terribly hard as long as the “radius” of the ellipse is larger than the radius of the chair at the point where two chairs might touch because the cord length isn’t sufficient to keep the two chairs from overlapping inside the extended ellipse.
I’ve got a couple of ideas (primarily because a long time ago I designed a CAD system that created CNC to move a mill around different shapes … I got really good at putting circles against those shapes), but they may not fit every ellipse.
The reality is that nobody’s going to design an elliptical table that has major and minor axis’ that differ widely, because the table with not have enough surface area for the theoretical number of chairs that could be placed around it.
Do you want to limit the ratio of the axis’ at all?
I’ll be back!
Steve,
I think it is entirely reasonable to set a fixed ratio for the axes A and B. Say A/B=1.5. Also we can limit the minimum size of the table so that the smallest axis (B) is never smaller than the seat diameter (D), regardless of N (this was an unstated assumption in the original post). Obviously this means that the seats won’t touch for N <= 6 ( not sure about higher N=7 or 8 ) – but that is ok.
The bit I am still struggling with is how to calculate the positions of the circles analytically.
Given that the i’th circle is at THETAi, how do we computer the angle of the i+1’th circle THETAi+1? Is angle X a right angle? If I could crack that, I don’t think it would be too difficult to write the code.
I’m getting closer … I think the mistake you’re making is treating the position of each chair as an angle (theta) from the center of the ellipse, but what you really want to describe is the position of the next circle’s center that is both 2r from the center of the last circle and 1r from the table ellipse on the perpendicular.
Since the perpendicular is defined as the bisection of the angle from the foci to a point on the ellipse, you’ll need the x and y values of both F1 and F2 in your formulas instead of the center x and y.
Iterating through the chairs to find x+1 should be relatively simple … what I’m still trying to figure out is how to adjust the chair spacing so there’s no gap when you’re done. The term 2r above will need some constant added to it to make the spacing even. While I can iterate through and find the space left over and then iterate again dividing that space up between the chairs, it would be nicer to determine ahead of time what the excess is and only iterate when you’re placing chairs.
My son and I have to go work on restoring his car (a 1971 Saab Sonnett), but I’ll keep this in the back of my mind and get back if I come up with some brilliance.
By the way, your spell checker must be set to UK English (why wouldn’t it be, so the spelling of center is flagged as incorrect. I live in Centre county PA – USA and, of course, nobody ever spells it correctly;)
Oooops … one more note!
A circular table is just the special case ellipse where F1 = F2, so you can indeed calculate tables with any aspect ratio (As I mentioned, they’re not all practical, but …).
ciao
>what I’m still trying to figure out is how to adjust the chair spacing so there’s no gap when you’re done.
I think you would just work out the circle spacing error for 2 different values of A and use Newton-Rhapson or some other iterative method to predict the next value of A. Repeat until it converged on a value of A that gave sufficiently accurate results.
For the best visual results you might want to try to minimise the sum of the squares of the gaps. This would help to even out any gaps/overlaps.
>By the way, your spell checker must be set to UK English
I am in the UK, so I prefer the ‘one true spelling’. ;0)
Been thinking about solving the position of a circle. If circle 1 is centred on (X1,Y1) and neighbouring circle 2 at (X2,Y2) then (X2,Y2) must lie of a circle of radius D centred on (X1,Y1) and also an ellipse with the same centre as the original ellipse (XE,YE) and axes A+D and B+D. This means:
(X2-X1)^2 + (Y2-Y1)^2 = D^2
and
(X2-XE)^2/(A+D)^2 + (Y2-YE)^2/(B+D)^2 = 1
If we pick a sensible starting position (X1,Y1) we can solve for (X2,Y2) in principal. I can rearrange the above into equations for X2 and Y2. But it is pretty ugly. It looks like a quartic. I don’t know how to solve them analytically. Maybe this is the same solution you got Christopher?
Some discussion on how to solve a quartic here:
http://en.wikipedia.org/wiki/Quartic_equation
“Another frequent generator of quartics is the intersection of two ellipses.”
Looks nasty. Perhaps there is public domain source available.
http://www.flipcode.com/archives/Polynomial_Root-Finder.shtml
Hmmmm. A solution might be within reach…
Yeah … I knew you were in the UK, hence the “and why wouldn’t it be” phrase above. I was just being amused by the spelling of my county actually being recognized as the correct spelling. I’m 1/8 welsh, and seem to have picked up an extra “u” here and there (colour and behaviour are the most common).
I looked at the link you provided, but it’s after 1000 PM here and my eyes glazed over at the sight of eigenvalues and covariance matrices. I’ll look at it tomorrow!
http://mathforum.org/library/drmath/view/66877.html
Andy, I have solved your problem…a flash demo showing it is here:
http://www.puzzlepublisher.com/tabledemo/tabledemo.htm
I did not want to post a the solution in binary form -wanted to avoid the whole virus/malware worry.
The solution isnt perfect-the spacing is off sometimes and for n >= 20 it is kind of slow…but im working on this.
Also for small n the output looks bad…I will add in your suggestion to treat n <= 6 as a special case.
Let me know if you want the executable/source code.
For those not worried about virus/malware…the Windows GUI executable is here:
http://www.puzzlepublisher.com/tabledemo/Table.zip
It seems that, in my model, there is a trade off between computational time and accuracy of the placement of the seats..you can get a nicer looking table if you are willing to trade off time to compute the table.
@Will Hunting
The last and first seat sometimes overlap a bit. Looks fairly good right up to N=100 though. What approach did you use for the seat placement? Do you know how long it takes to compute a layout? Would it be much more to make the seat placement more accurate?
I use a heuristic to compute the placement of the seats…I don’t use the analytic or numeric solution to an equation that solves for the intersection of ellipses – the seat and the table (as seems to be your current strategy).
Im trying to fix the overlapping of the last seat and the first seat. The problem is my my computation of the right ellipse circumference (and hence minor axis since major axis = 1.5*minor_axis) so that all the seats fit with no excess space.
I let you know when I figure it out.
> Maybe this is the same solution you got Christopher?
Yes maybe. I had the following equations.
1) The definition of an ellipse is like:
x^2 + (y/a)^2 = 1
… for some constant ‘a’ that represents the eccentricity.
2) The centre of a circle is normal to where it touches the ellipse; so, relative to the point {x,y} where it’s touchng the ellipse, it’s somewhere along the vector:
r*{ax,y}
… where ‘r’ is a constant proportional to the radius of the circle.
The centre of the circles location relative to the origin is therefore at:
{x,y} + r{ax,y}
I.e. at:
{(ra+1)x,(r+1)y}
3) Given any known location {m,n} on the ellipse, the distance from the centre of circle which touches it to the centre of the circle which touches arbitrary {x,y} is given by:
((ra+1)m)-(ra+1)x)^2 + ((r+1)n-((r+1)y))^2
… by Pythagoras’ theorum of the hypotenuse.
We constrain this to:
((ra+1)m)-(ra+1)x)^2 + ((r+1)n-((r+1)y))^2 = 2r
… because we want the circles to be touching.
4) Equation #3 has two variables i.e. x and y. Equation #1 also has two variables, i.e. x and y. You therefore have two simultaneous equations in two variables.
I think that you can then, with a dozen++ lines of elementary algebra, combine these two to a single equation in one variable, and then simplify this equation to the quartic which I mentioned earlier, which is exactly/analytically factorizable, and which has two solutions/roots, which represent the two circles on either side of the given/known point at {m,n}.
> It looks like a quartic … Some discussion on how to solve a quartic here …
Maybe I got it wrong (I’d have to do it again carefully to be sure) but I thought that ours would reduce to a special/simple form of quartic, i.e. a quartic of the form …
x^4 – mx^2 + n = 0
Note that the x^3 and x^1 terms are zero … so this can be factored as a quadratic in x^2, i.e.
(x^2 – p)(x^2 – q) = 0
… for some p and q … so, the solutions for x instead of x^2 would be root p and root q.
Sorry, I think I did get it wrong: it’s not a “biquadratic” equation, instead there’s a term in x^3 as well.
Christopher,
You approach sounds very similar, although I don’t think it is exactly the same.
>simplify this equation to the quartic
I did make a start on this. The equations got a bit scary. But I think it is doable. Might be able to find it already done on Google.
You can solve a quartic that doesn’t factor into a quadratic using the code linked to above.
> The equations got a bit scary.
Yes the ‘constant’ terms (i.e. the coefficients of the polynomial as functions of ‘r’ and ‘a’) are complicated; need to be attempted carefully.
> You can solve a quartic that doesn’t factor into a quadratic using the code linked to above
The code seemed (I didn’t look at it carefully) to be iterative (Newton-Raphson, or something). The Wikipedia entry might have been explaining an analytic solution.
Do you have any comments on estimating the number of FLOPS available/required?
By the way, Google Images didn’t show any elliptic banquet tables … the “oval” tables seemed instead to be rectangles with a semi-circle at either end.
> The code [for solving a quartic] seemed to be iterative
I suspect that if the table and the number of chairs is large, then the ellipse is relatively flat (over the distance between two chairs), and so you can get a good initial estimate, and the estimate will converge quite quickly; however the more chairs there are the more accurately you might want to measure each one, unless you count on the Law of Large Numbers, which you probably shouldn’t because your estimation errors might all have the same sign.
Check out the Table.zip now. Ive made it so that instead of a slight overlap, you get a slight gap between the last and first seat. I figure this is more tolerable, without any loss in computation time.
Ive also added in a zoom in/zoom out buttons so you can see the performance on each draw. As you can tell, zooming gets choppy for larger ellipses (as n and d get bigger), to the point where it would bother a user of Perfect table plan.
The solution is to pre-compute the placement of the tables for all known values d can take when zooming. This will mean there is a delay when first rendering the table (and more memory – each seat placement needs a double so up to 99*(number of zoom values)*8 bytes for each table), but then zooming in and out should be smooth.
I’m having a crack at getting the analytic solution working…
looking at this I see the movement of a planet about the sun.
therefore Keplers laws. …Speed.
Kepler’s laws..this is what is saw also..too bad Kepler’s laws only describe elliptical orbits and not the center of a circle that is tangent to a given circle on the orbit path.
Hi Andy, you can try this code for the quartic solution.
Although I have not tested it extensively, the code worked for the couple of test cases I threw at it, and returns all non-complex roots.
I’m assuming you already have your quadratic solver and a cubic solver that returns at least one non-complex root.
The variable naming (H/h and G/g etc) follow those of the Neumark description in the document in the link.
// solves general quartic using Neumark’s algorithm
// contains tweaks and general method described in:
// “Solving Quartics and Cubics for Graphics”
// Don Herbison-Evans
// Technical Report TR94-487
// University of Sydney, Australia
// ( http://linus.socs.uts.edu.au/~don/pubs/solving.html )
// Added special cases for the calculation on G/g and H/h in case the tweak would result in a div/0
int solve_quartic(double a4,double a3,double a2,double a1,double a0,double results[4])
{
register double R,D,E,R2,g1,g2,h1,h2,G,H,g,h,mn,tmp;
int rescount,ownrescount;
double y[3];
if(a4==0.0)
return solve_cubic(a3,a2,a1,a0,results);
a3/=a4;
a2/=a4;
a1/=a4;
a0/=a4;
// Using Neumark’s algorithm – cubic is y3 – 2by2 + (ac + b2 – 4d)y + (a2d – abc + c2)=0
if(a0*a3*a3-a3*a2*a1+a1*a1 == 0.0) { // if this is 0, then y=0 is a solution, so don’t bother looking for the rest
y[0]=0;
}
else
if(solve_cubic(1.0,-2.0*a2,a1*a3+a2*a2-4.0*a0,a0*a3*a3-a3*a2*a1+a1*a1,y,true)==0)
return 0;
rescount=0;
// once we get this far, we know that at least y[0] contains a real root
// determine most stable derivations for g2 and h2
tmp = (a2-y[0]); // b-y in the paper
g1 = 0.5*a3;
h1 = 0.5*tmp;
if(y[0]>0.0 && a2<0.0 && a0 4.0*a0) {
mn = tmp*tmp – 4.0*a0;
g2=(a3*h1 – a1)/sqrt(mn);
h2=sqrt(mn)*0.5;
}
else {
mn = a3*a3 – 4.0*y[0];
g2=sqrt(mn)*0.5;
h2=(a3*h1 – a1)/sqrt(mn);
}
}
else {
if(a3*a3 > 4.0*y[0]) {
mn = a3*a3 – 4.0*y[0];
g2=sqrt(mn)*0.5;
h2=(a3*h1 – a1)/sqrt(mn);
}
else {
mn = tmp*tmp – 4.0*a0;
g2=(a3*h1 – a1)/sqrt(mn);
h2=sqrt(mn)*0.5;
}
}
if(g1<0.0 && g2=0.0 && g2>=0.0) {
g = g1 – g2;
if(g != 0.0)
G = y[0]/g;
else
G = g1 + g2;
}
else {
G = g1 + g2;
if(G != 0.0)
g = y[0]/G;
else
g = g1 – g2;
}
if(h1<0.0 && h2=0.0 && h2>=0.0) {
h = h1 – h2;
if(h != 0.0)
H = a0 / h;
else
H = h1 + h2;
}
else {
H = h1 + h2;
if(H != 0.0)
h = a0 / H;
else
h = h1 – h2;
}
rescount=solve_quadratic(1.0,G,H,results);
rescount+=solve_quadratic(1.0,g,h,results+rescount);
return rescount;
}
I noticed some bits of code don’t come across during the copy&paste. Send me an e-mail if you want me to send the quartic code. I’ll have to send it from home though.
I’m stuck. It is over 20 years since I did much algebra and I am struggling to rearrange the equations into a quartic.
The centre of circle 2 (x2,y2) falls on the intersection of a circle C with radius D centred at the previous circle (x1,y1) and an ellipse E’ with semi-major and semi-minor axes a+D/2 and b+D/2.
I have rearranged (2) to give an equation in y2 that I can substitute into (1). But, due to the square root, it isn’t going to give a quartic in the form ax2^4 + bx2^3 +cx2^2 + dx2 + e = 0 . Any ideas?
Ps/ E and E’ are centred on (0,0).
I think you’ll need to write out eq. 1. I think that will leave you with the square of x2 and the square of y2, and their product. The rest are constants (including x1 and y1).
Then express x2 and y2 in terms of a new variable ‘t’, which you could probably get from eq. 2.
Don’t bother with any square roots. Just take the square of the entire equation if you run into any of them.
That’s where you’ll likely get your fourth degree polynomial from, which is solvable.
Intuitively you should be getting two real roots out of that equation (one to the left and one to the right).
However your direction seems to be towards calculating the y2 and x2 coordinates based on known x1 (and known y1), in other words how to draw the individual circles around the larger ellipse.
It does not look like the path towards determining how large a (and b) should be.
You’re probably better off asking your circle and ellipse question on mathworld or some such site.
Squaring both side of (1) might work. The resulting equation will be quite nasty though.
>However your direction seems to be towards calculating the y2 and x2 coordinates based on known x1 (and known y1), in other words how to draw the individual circles around the larger ellipse.
yes.
>It does not look like the path towards determining how large a (and b) should be.
I am assuming I already know a. If not I can use the error in the circle placement to work back to it.
I was also assuming that a and b were know, since table manufacturers obviously don’t make every size elliptical table possible. And I was also assuming the chair space designated by the circle was something that Andy fixed in his diagrams.
So the problem is really calculating an even number of fixed length cords around the ellipse, whose curvature varies sinusoidally. Sounds more like a calculus problem if you state it that way
> I am struggling to rearrange the equations into a quartic.
dy/dx of the ellipse at a location {x,y} on its circumpherence:
= -a*(x/y)
Location of the centre of the circle which touches the ellipse at {x,y}:
= {x,y} + r*{ax,y}
= {x*(ra+1),y*(r+1)}
Given any two cartesian locations, at points {m,n} and {o,p}, the distance between these two points is given by Pythagoras’ hypotenuse:
=> (o-m)**2 + (p-n)**2
So given any two circles, the first of which touches the ellipse at point {c,d} and the second of which touches the ellipse at at point {x,y}, the distance between the centres of the two circles is given by:
=> ((ra+1)*(c-x))**2 + ((r+1)*(d-y))**2
Constraining these so that the circles touch each other:
=> ((ra+1)*(c-x))**2 + ((r+1)*(d-y))**2 = 2r
The equation, which constrains the two variables {c,d} to be on the ellipse, is that:
=> c**2 + (d/a)**2 = 1
=> c = +- sqrt(1 – (d/a)**2) //where d ((ra+1)**2)(c**2 + x**2 – 2cx) = 2r – ((r+1)*(d-y))**2
=> ((ra+1)**2)(x**2 – 2cx) = 2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2
Substituting into this the second equation which expresses x as a function of y:
=> ((ra+1)**2)((sqrt(1 – (y/a)**2))**2 – 2c(sqrt(1 – (y/a)**2))) = 2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2
=> ((ra+1)**2)(1 – (y/a)**2 – 2c(sqrt(1 – (y/a)**2))) = 2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2
Isolating the square root on the left hand side:
=> ((ra+1)**2)(- 2c(sqrt(1 – (y/a)**2))) = 2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2 – ((ra+1)**2)(1 – (y/a)**2)
Take the square of both sides to eliminate the square root:
=> ((ra+1)**4)(4c**2)(1 – (y/a)**2) = (2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2 – ((ra+1)**2)(1 – (y/a)**2))**2
Given that r and a are constants, the above is a quartic for y.
There’s a second quartic to be had, by substituting “x = negative sqrt(1 – (y/a)**2)” instead of “x = positive sqrt(1 – (y/a)**2)”.
I’m expecting a total of two solutions for y.
Something that’s worrying me is that we have two quartics, and that each quartic probably has an even number of solutions (e.g. 2 solutions for each quartic), totalling four solutions. I don’t know how that will work out. Maybe the pair of solutions from one quartic will match the pair from the other quartic, or maybe both quartics each have only one solution, but I’m dubious. Anyway, that’s what I would have experimented with.
The middle of the above was trashed by my having a < sign in the text. Here’s the middle bit again:
…
The equation, which constrains the two variables {c,d} to be on the ellipse, is that:
=> c**2 + (d/a)**2 = 1
=> c = +- sqrt(1 – (d/a)**2) //where d less than or equal to a by definition
Note that c is +ve or -ve, which corresponds to the two solutions (two circles on either side).
To summarize, we have two simultaneous equations:
((ra+1)*(c-x))**2 + ((r+1)*(d-y))**2 = 2r
and:
x = sqrt(1 – (y/a)**2)
Expanding the first equation in order to isolate the terms for x:
=> ((ra+1)**2)(c**2 + x**2 – 2cx) = 2r – ((r+1)*(d-y))**2
=> ((ra+1)**2)(x**2 – 2cx) = 2r – ((r+1)*(d-y))**2 – ((ra+1)c)**2
Substituting into this the second equation …
Maybe the reason why the number of solutions was doubled was because of the step which says “Take the square of both sides to eliminate the square root”.
For example, given:
a = b
Take the square:
a**2 = b**2
This has two solutions, i.e. “a = b” and “a = -b”, only one of which satisfies the original equation.
So, when you get two solutions for the quartic, maybe you need to try substituting both (each) of them into the earlier equation which involved a square root, to see which *one* of them is the solution to that equation.
You would expect a quartic to have up to 4 roots. A circle can cross an ellipse at up to 4 points (although not in this particular case).
Well, that’s true enough.
I’m hoping (grin) that *these* quartics might have only 2 real roots, only one of which solves the previous equation involving a square root.
If you double-check my algebra, and plug the quartic’s coeffients into some graphing software, you might see how the numbers and positions of the quartic’s roots might vary with a, r, and {c,d}.
It’s beyond me (I can’t visualize how the shape of the quartic relates to the geometry of the problem, so I can’t use my understanding of the geometry of the problem to predict the shape of the quartic).
Here is my approach. Unless solving the quartics/geometric equations results in an closed-form solution, a heuristic maybe better. Here is what I came up with:
Step 1. Consider an ellipse E that traces the arrangement of tables around an elliptical table. Let N be the number of seats and seat_radius be the radius of each circle seat. Assume N > 6. This ellipse will initially have minor axis of minor > seat_radius*N and major axis of major = 1.5*minor.
Set the center of circle seat 1 at coordinate (0, minor).
Step 2. Iterate Subroutine 1 for i= 2….N, where N is the number of seats.
Subroutine 1. Find the center of circle seat i.
To solve for the center of the next seat you can either use exact methods or a heuristic. The heuristic is easier to implement, but will not produce exact results (i.e. the seats will not be perfectly tangent in every case). This may also end up to be true of the exact method, depend on the nature of the resulting equations—if a closed form solution for the equations does not exist, numerical methods will need to be employed, producing solutions that will not be much better than those produced via the heuristic.
Exact Method:
(1) solve for the roots of a quartic or other higher degree polynomial that exactly (or to an adjustable degree of accuracy) finds the point of intersection of Ellipse E and circle seat i – 1. Call this point P.
(2) Use this to compute the center of circle seat i: the center is the point that is both on Ellipse E and also crosses point P. This will give rise to a system of polynomials, which can be used to solve for the center of seat circle i.
Heuristic:
Alternatively you can employ a heuristic: instead of trying to calculate center coordinates exactly from equations, you can trace Ellipse E using a parameterized representation of E, namely x = major*cos(t), y = minor*sin(t), where (x,y) are the Cartesian coordinates and t is a parameter between 0 and 2π. As t varies, test to see if a circle seat drawn at t will intersect the last drawn circle seat. If so, increment t. If not, stop, you have found a position on E that is “good enough” and draw your circle at the x, y coordinates implied by the current value of t.
Step 3. Check the amount of excess space left on the ellipse after all seats are drawn. Usually after the first iteration of steps 1 and 2, there seats will not fully make is around the ellipse, leaving a gap between circle seat 1 and circle seat N. Test this distance by measuring the distance from the center of circle seat 1 and circle seat N.
If this distance D > some critical number (usually 2*seat_radius + some error allowance), then decrement the minor axis (minor) of ellipse E by an amount (smaller amount->more accuracy but longer computation time), and set major = 1.5*minor. Then loop back to Step 1 and repeat this algorithm. If D is less than or equal the critical number, terminate this algorithm and return the values of the centers of the seats computed in Step 2, and draw the table.
@Will Hunting,
The more I look at Christopher’s equations, the more attractive your approach becomes. ;0)
I think I am going to try transplanting your code into a Qt test harness I wrote and see whether I can I get it accurate enough in a reasonable time.
I could always cache the results for the last 5 values of N if it is a bit slow.
Looks like finding an analytic solution for this class problem is really tough (not that we didnt know that already):
Click to access PRE_75_2007.pdf
> The more I look at Christopher’s equations, the more attractive your approach becomes. ;0)
They devolved to a quartic: so how bad was that?!
It’s a different quartic (i.e. different coefficients) for each seat, admittedly, because it depends on {c,d} as well as on a and r … but that’s inevitable, in order to have a different location for each seat.
Calculating the each seat’s quartic’s coefficients (the coefficients being functions of a, r, and {c,d}) looks like it would be a few dozen FLOPs.
Then the analytic solution of those (or any) quartics e.g. http://www.karlscalculus.org/quartic.html looks like it might be several dozen more (though why they don’t just write it out as an end-result like http://www.karlscalculus.org/notes.html#quadratic somewhere, I don’t know).
Using a heuristic to find the seats’ centres ought to do too … I’m guessing you have the FLOPS to spare.
I kept coming back to the fact that given the circumference of the ellipse that contains the seats centers, the circumference divided by the number of seats is the arc length that you need to determine the angular reference for the center of a seat in reference to the ellipse’s center.
It turns out, there’s a whole series of integrals specifically dedicated to this problem. See http://en.wikipedia.org/wiki/Elliptic_integral
I don’t think that the seats’ centres are on an ellipse; for example if the width of the table tends towards zero, so that the shape of the elliptic table tends towards a thin line, then the shape of the line through the centres of the chairs would tend towards a rectangle (i.e. not an ellipse).
Also the arc length between each pair of chairs isn’t constant (the length pf the straight line between the centres of each pair of chairs is constant, but the shape’s curvature isn’t constant and the arc length is greater betwen pairs where the shape’s curvature is larger).
> though why they don’t just write it out as an end-result …
Here’s why:
http://planetmath.org/encyclopedia/QuarticFormula.html
NB: at one point I implemented that in code, but I suspect it requires complex numbers to work, because the results I got were completely wrong.
“I don’t think that the seats’ centres are on an ellipse”
I’ve been placing seat centers such that for a table with major/minor axes of a/b, the seat centers fall on the ellipse a+r/b+r where r is the radius of the seat circle. The seats seem to be tangent to the table ellipse, but maybe there’s some error I’m not seeing in the resulting graphics (I’m using Genius … it’s kind of like Matlab).
> Here’s why: h**p://planetmath.org/encyclopedia/QuarticFormula.html
Thanks. I don’t remember seeing *that* in school.
> seat centers fall on the ellipse a+r/b+r where r is the radius of the seat circle
I think those seats will overlap the ellipse at all except the 4 cardinal points (and that this will be most visible when a is much smaller than b, and the seats are sized such that there are about 8 or 12 seats around the table).
yep … I stretched the elliptical table to an extreme and they do overlap.
I think a lot got real close to the solution but you are focusing on the wrong ellipse.
You first do what the original poster did and set C = N*D.
That gives you the ellipse of the chairs. They use the equation of an ellipse and the distance equation for two points.
That is two equations and two unknowns (the new X and Y position).
You will need to pick the location of the first chair (circle origin), but then after that those two equations will give you two results, one in each direction around the ellipse.
After you have used that chair ellipse, shrink both sides by D and you have the table ellipse.
For small values of N (say 6 or less), the use of C = N*D does not work too well, so I would suggest D by a factor of 2 or so in all calculations. That will allow the chairs to not have to touch.
SHOULD HAVE CHECKED MY LAST POST FOR TYPOS.
*****************************************************
I think a lot got real close to the solution but you are focusing on the wrong ellipse.
You first do what the original poster did and set C = N*D.
That gives you the ellipse of the chairs. Then use the equation of an ellipse and the distance equation for two points.
That is two equations and two unknowns (the new X and Y position).
You will need to pick the location of the first chair (circle origin), but then after that those two equations will give you two results, one in each direction around the ellipse.
After you have used that chair ellipse, shrink both sides by D and you have the table ellipse.
For small values of N (say 6 or less), the use of C = N*D does not work too well, so I would suggest scaling D by a factor of 2 or so in all calculations. That will allow the chairs to not have to touch.
An update.
I have two software solutions. One from ‘Will Hunting’ in C++/Qt and one from Bruce Pearson in Python/WxWidgets. Both use heuristic approaches.
Bruce Pearson’s code does pretty well for up to N=27. But the circles overlap beyond that.
Will Hunting’s does better with circle placement over a wider range of N. It also had the advantage of being in C++, making it easier to incorporate into PerfectTablePlan. But there is a visible gap between circle 0 and circle N-1. if this error could be spread equally between all the circles I think it might be good enough.
GJ Peltenburg has sent me some quartic solver code and Christopher Wells has filled in more details on an analytic approach. But every time I try to write out the quartic equation for x2 in terms of x1 and y1 my brain starts to bleed. ;0)
Another update. I have a working solution! More details soon.
Pingback: A mathematical digression (revisited) « Successful Software