Software that makes placemats

[jdaw1]

Software and manual updated.

Comments, complaints, praise, bug reports: all welcomed.

[jdaw1]

Googling the problem of packing circles reveals much learned comment, and lists of best-known packings at Packomania.com. But, as posted in sci.math, the placemat software knows some to be better, most obviously that for 1607 circles on a square page. If using Bunghole-standard glasses, it would have to be a large page.

[RAYC]

Very nice.

For smaller tastings, how about an A3 mat, guillotined lengthways (i.e 420 x 15mm), that can be placed near centre table (leaving uncluttered space for notes/meals etc.) and contain ports in an easy access row?

[jdaw1]

For smaller tastings, how about an A3 mat, guillotined lengthways (i.e 420 x 15mm), that can be placed near centre table (leaving uncluttered space for notes/meals etc.) and contain ports in an easy access row?

There are also three simple designs, /TopRow, /MiddleRow, /BottomRow, each having everything in one row, with obvious vertical position. There is also /Sides, with the obvious meaning.
For more than a few glasses these are too cramped.

Might /BottomRow do the job?

[PhilW]

(i.e 420 x 15mm)

That would certainly leave the table uncluttered.

[jdaw1]

Packomania.com is for geeky mathematicians, and has lots of examples of packing circles of maximal radius in various containers, including 7×10 rectangles. That is close to the proportions of A4, less a fixed margin.

Observe Packomania’s best for for 7 circles and 10 on a 7×10 rectangle:
 

I’ll implement this as two on the right (/Landscape) or top (/Portrait), reversed for /Mirror, of course, and three-row (three-column) /Diamonds for the rest. Packomania’s 10-glass solution is an epsilon better than that, but generalising the asymmetry would be too complicated. Compared to plain seven-glass /Diamonds, that adds ≈5% to the radius. PW would have wanted that for Warre versus Fonseca tasting.

What should it be called?

[djewesbury]

Are you thinking architectural, prosaic, allusive..? I can't see anything in the pattern that would provide a short metaphorical name at present. I'm guessing it'll probably end up being something like /DiamondsPlusTwo or /DiamondsAsymmetricalSeven or something like that.

[jdaw1]

/DiamondsPlusTwo

Current winner is ‟/DiamondsPlus”, which allows a little generalisation to something like Packomania’s 29-glass best:

[djewesbury]

I wouldn't like to be reaching for glass 16 on that placemat...

[jdaw1]

I wouldn't like to be reaching for glass 16 on that placemat...

It’s printed on A0. Each glass can hold most of a bottle. By the time you reach glass 16, it would indeed be difficult.

[Glenn E.]

Current winner is ‟/DiamondsPlus”

I can think of nothing better.

[PhilW]

Current winner is ‟/DiamondsPlus”

I can think of nothing better.

Ditto. Some possible insect outlines came to mind, but ‟/DiamondsPlus” is probably simpler and clearer, and therefore preferred.

[djewesbury]

Current winner is ‟/DiamondsPlus”

I can think of nothing better.

Ditto. Some possible insect outlines came to mind, but ‟/DiamondsPlus” is probably simpler and clearer, and therefore preferred.

I quickly discarded /BeetleCarapace

[jdaw1]

Step one: write code to solve a quartic equation. Worrying, I think that I have devised an algorithm as good as Brent’s Method, but simpler, and not needing a pre-chosen x-step.

Assume root bounded by LowerX and UpperX, with matching y values LowerY and UpperY. Interpolation would make the next x value be LowerX + (UpperX”“LowerX) × LowerY/(LowerY”“UpperY). This can fail for some shapes (e.g., y = x^4 ”“ c), as the interpolated value is always on the same side of the root, so only one side (say, LowerX) ever gets moved.

So instead make the next x value be LowerX + (UpperX”“LowerX) × Max[0.143, Min[0.857, LowerY/(LowerY”“UpperY) ]]

Repeat until UpperX”“LowerX ≤ Tolerance, that constant being pre-determined and small, at which time return the interpolated value (without the bounds).

When LowerX and UpperX are roughly even around the root, it interpolates. When one side is much closer, it brings in the other, moving it by a factor of 1÷0.143 ≈ 7.

FYI, the ‟0.143” constant came from a small experiment done in Excel. I do not know whether it should be precisely 1/7, or some other value. But a small non-exactitude in this would add only a tiny extra to the algorithm’s average time.

Indeed, this can be seen as a compromise between the slow robustness of interval bisection (‟! Max[0.5, Min[0.5, ! ]]”) and interpolation (‟! Max[0, Min[1, ! ]]”).

[Glenn E.]

Current winner is ‟/DiamondsPlus”

I can think of nothing better.

Ditto. Some possible insect outlines came to mind, but ‟/DiamondsPlus” is probably simpler and clearer, and therefore preferred.

I quickly discarded /BeetleCarapace

Hmm... it does look a bit like a top down view of a Star Trek shuttlecraft... though /Galileo would probably be too esoteric of a reference.

[jdaw1]

Hmm... it does look a bit like a top down view of a Star Trek shuttlecraft... though /Galileo would probably be too esoteric of a reference.

Not sure to which of the many possible uses of /Galileo this refers, but, as you say, too esoteric.

[djewesbury]

[jdaw1]

too esoteric of a reference.

[jdaw1]

Different question. In the arrangement thread for the 1966 horizontal on 27th June, with each update of the placemats pictures have been posted in the thread.

E.g.,

Updated draft of the placemats.

• +BMHR and his Croft.

Is this worth the effort?

[djewesbury]

yes

[DRT]

with each update of the placemats pictures have been posted in the thread.
!
Is this worth the effort?

yes

Agreed.

[PhilW]

Different question. In the arrangement thread for the 1966 horizontal on 27th June, with each update of the placemats pictures have been posted in the thread.

Is this worth the effort?

In the general case I'd say no; It's useful in the case you refer to because the first post is not currently being regularly updated, so the image posts are providing a useful update of current attendees and ports; if the first post were being regularly updated, I think the additional effort of pdf -> jpg -> image hosting -> post for each placemat iteration would be excessive.

[PhilW]

Step one: write code to solve a quartic equation. Worrying, I think that I have devised an algorithm as good as Brent’s Method, but simpler, and not needing a pre-chosen x-step.

Assume root bounded by LowerX and UpperX, with matching y values LowerY and UpperY. Interpolation would make the next x value be LowerX + (UpperX”“LowerX) × LowerY/(LowerY”“UpperY). This can fail for some shapes (e.g., y = x^4 ”“ c), as the interpolated value is always on the same side of the root, so only one side (say, LowerX) ever gets moved.

So instead make the next x value be LowerX + (UpperX”“LowerX) × Max[0.143, Min[0.857, LowerY/(LowerY”“UpperY) ]]

Repeat until UpperX”“LowerX ≤ Tolerance, that constant being pre-determined and small, at which time return the interpolated value (without the bounds).

When LowerX and UpperX are roughly even around the root, it interpolates. When one side is much closer, it brings in the other, moving it by a factor of 1÷0.143 ≈ 7.

FYI, the ‟0.143” constant came from a small experiment done in Excel. I do not know whether it should be precisely 1/7, or some other value. But a small non-exactitude in this would add only a tiny extra to the algorithm’s average time.

Indeed, this can be seen as a compromise between the slow robustness of interval bisection (‟! Max[0.5, Min[0.5, ! ]]”) and interpolation (‟! Max[0, Min[1, ! ]]”).

Presumably this also depends on any assumptions regarding the nature of the quartic to be solved, i.e. all-real roots (or at least a real root between the specified starting points), no discontinuities (no matching pole-zero root pairs) etc. In which case whether bisection, interpolation or your alternate specified scheme would be quicker in the general case would presumably depend on the nature of the group of potential curves across which the technique would be used? An alternative to the factor changed used to avoid never reaching the root could be to add a small proportion of the step delta determined from interpolation (deliberate over-adjust), though potentially decreasing the over-step with time to avoid oscillation; similar to techniques used to avoid getting stuck in local minima.

[jdaw1]

Presumably this also depends on any assumptions regarding the nature of the quartic to be solved, i.e. all-real roots (or at least a real root between the specified starting points), no discontinuities (no matching pole-zero root pairs) etc. In which case whether bisection, interpolation or your alternate specified scheme would be quicker in the general case would presumably depend on the nature of the group of potential curves across which the technique would be used? An alternative to the factor changed used to avoid never reaching the root could be to add a small proportion of the step delta determined from interpolation (deliberate over-adjust), though potentially decreasing the over-step with time to avoid oscillation; similar to techniques used to avoid getting stuck in local minima.

Assumptions: ∈ ℝ; continuous; starting points either side. No more. Desiderata include robustness, speed, and simplicity of code.

Don’t need to reach the root, only for the bounds either side to be closer than xTolerance, when do a final unconstrained linear interpolation.

[PhilW]

Assumptions: ∈ ℝ; continuous; starting points either side. No more. Desiderata include robustness, speed, and simplicity of code.

Don’t need to reach the root, only for the bounds either side to be closer than xTolerance, when do a final unconstrained linear interpolation.

Any possibility of multiple roots between initial bounds (excluding duplicate root)? (I.e. can we either exclude the possibility of multiple roots being present, and If not then do we care? i.e. are all roots required, or any root). Could there be any bounding of the relative ratio of xTolerance to initial delta between upper and lower bounds?

n.b. I assume direct calculation would not be appropriate?

[jdaw1]

Any possibility of multiple roots between initial bounds (excluding duplicate root)? (I.e. can we either exclude the possibility of multiple roots being present, and If not then do we care? i.e. are all roots required, or any root). Could there be any bounding of the relative ratio of xTolerance to initial delta between upper and lower bounds?

n.b. I assume direct calculation would not be appropriate?

LowerX < UpperX; f(LowerX) × f(UpperX) ≤ 0. Any root that is between LowerX and UpperX, please.

n.b. I assume direct calculation would not be appropriate?

I thought about that, and decided that it would be too much grief.

[PhilW]

Could there be any bounding of the relative ratio of xTolerance to initial delta between upper and lower bounds?

(and if the implicit answer from your previous post is "no", then how is xTolerance defined/determined?)

[jdaw1]

how is xTolerance defined/determined?)

I know that x is in points, so xTolerance is defined to be 0.01. An answer that accurate is good enough for me.

[PhilW]

how is xTolerance defined/determined?)

I know that x is in points, so xTolerance is defined to be 0.01. An answer that accurate is good enough for me.

If a maximum paper size can also be assumed, perhaps no greater than 3.5m in one dimension should be more than sufficient, then this would presumably bound the upper limit to 10000 points, which with a tolerance of 0.01 gives a worst case ratio of tolerance to initial upper-lower of 1/1000000 or approx. 1/(2^20). To identify a 1 in 2^20 region, would then require 20 calculations of y using bisection, which then gives us an upper bound for the required computation.

Desiderata include robustness, speed, and simplicity of code

Interpolation is only worthwhile compared with bisection if division is sufficiently computationally efficient compared with the saving in additional multiplication/addition operations to calculate the additional bisection steps. At some point this trade-off may change. On a system where division is not fully accelerated in hardware, a division could be as computationally intense as say five bisections, in which case only one or two interpolations may be worthwhile before switching to subsequent bisections, for example.

Going back to your original formula; it is not in the form I would have intuitively expected, but is equivalent, and your arrangement maps well to define the restriction of movement of the estimation region boundaries. The computation is essentially equivalent to standard interpolation; Notably the division could also be avoided for the case where the interpolation is limited, since the tests:
-LowerY<=0.14*(UpperY-LowerY) OR -LowerY>=0.86*(UpperY-LowerY)
could be performed and the division only calculated if they were true.

The generalised formula as:
next x = LowerX + (UpperX”“LowerX) × Max[alpha, Min[(1-alpha), LowerY/(LowerY”“UpperY) ]]
does seem useful, where determination of suitable alpha for different applications is possible.

Seems like a good approach for this application provided division isn't too costly (in which case bisection wins). I would guess you could usefully select a slightly higher value than 1/7 (anything up to 1/4 potentially) which would speed some cases up and others down. Not sure where the optimum value would be, likely data dependent.

[jdaw1]

1/1000000 or approx. 1/(2^20).

PostScript uses single precision, with a 23-bit mantissa.

Seems like a good approach for this application provided division isn't too costly

(LowerX + UpperX) ÷ 2 still has s division. Maybe the hardware tests for and accelerates by-two division. Probably not.

Not sure where the optimum value would be, likely data dependent.

Constant, 1/7, determined by crude experiment in Excel.

[PhilW]

Seems like a good approach for this application provided division isn't too costly

(LowerX + UpperX) ÷ 2 still has s division.

(LowerX + UpperX) * 0.5 does not have a division in floating point calculation and would be the expected implementation to reduce computation for that case;
(LowerX + UpperX) >> 1 would be similarly used for the integer case (though an integer /2 might well be compiler optimised to that shift).

[jdaw1]

n.b. I assume direct calculation would not be appropriate?

I thought about that, and decided that it would be too much grief.

Alas, it is required. Damn.

Have you recommended (pseudo)code that will convert c0!c4 to four roots?

[PhilW]

Have you recommended (pseudo)code that will convert c0!c4 to four roots?

No, sorry; I would use the formulae from there, and implement calculation of discriminant,p,q,S,Q,x (where c4..c0 are a..e and is only valid for non-zero a).

The only optimisations I can see would be potential detection of non-real solutions to allow you to ignore part of the calculation, but not much in the general case.

The fortran implementation here might help?

[jdaw1]

PostScript lacks complex types, and lacks derived types. Ick. I’ll try harder to avoid this.

[jdaw1]

/DiamondsPlus: done.


Best fitting of seven glasses on A4.

[djewesbury]

/DiamondsPlus: done.


Best fittin of seven glasses on A4.

Is the mathematician's solution always the drinker's?

[jdaw1]

Is the mathematician's solution always the drinker's?

We once had two sets of seven, Warre and Fonseca, and a room with space constraints. /DiamondsPlus would have helped.

However, it is less elegant than some other arrangements. So should be used only when needed only when packing seven onto A4 or US Letter = 8½″×11″, or ten onto US Legal 8½″×14″.

I thought it a mite harsh of you to add a spelling error to the quote of my correctly spelt words.

[djewesbury]

I thought it a mite harsh of you to add a spelling error to the quote of my correctly spelt words.

Oops! How did I manage that I wonder..
Your Warre/Fonseca placemats are things of beauty. How did the traced line connecting the glasses appear? And what is the correct way of including an external graphic (the makers' brands)?

[jdaw1]

Made by PhilW, not by me.

[djewesbury]

There appears to be a problem with /Array .
The example code in the manual:
[ /Array /Positions [0 2] [2 2 3 2] [4 2 3 2] [6 2] [0 1] [3 1] [6 1] [0 0] [3 0] [6 0] ] ,
when used in a test script, results in an automatic substitution of /TopRow for the intended pattern.
The same thing happens with other examples: /TopRow subsitution every time.
There appears to a be a syntactical error.
The code appears to use /PositionsStart, the manual /Positions .

[PhilW]

How did the traced line connecting the glasses appear?

These were my custom use of the feature "MakePathConnectingGlasses" within Julian's postscript.

And what is the correct way of including an external graphic (the makers' brands)?

This is not a standard feature. I took a couple of photographs, converted them to postscript format using an imaging program, and then cut/pasted their use with function prototypes into Julian's program, using an online postscript manual as a reference.

[djewesbury]

This is not a standard feature. I took a couple of photographs, converted them to postscript format using an imaging program, and then cut/pasted their use with function prototypes into Julian's program, using an online postscript manual as a reference.

Right... I can live without that for now then, given that I got a migraine trying to get the /Array packing style to work...

[jdaw1]

DJ: did the emails help? Please suggest words for the manual.

[jdaw1]

Desiderata include robustness, speed, and simplicity of code

Interpolation is only worthwhile compared with bisection if division is sufficiently computationally efficient compared with the saving in additional multiplication/addition operations to calculate the additional bisection steps. At some point this trade-off may change. On a system where division is not fully accelerated in hardware, a division could be as computationally intense as say five bisections, in which case only one or two interpolations may be worthwhile before switching to subsequent bisections, for example.

It has taken me a while to realise what this misses. The assumption is that computation of f[] is slow compared to the modest computation done by the calling routine. Calling f[] half as many times is assumed to be much much more important. So the extra division of interpolation is de minimus.

[jdaw1]

The code appears to use /PositionsStart, the manual /Positions .

Very sorry. Damn. Will be fixed today.

[djewesbury]

DJ: did the emails help? Please suggest words for the manual.

The code appears to use /PositionsStart, the manual /Positions .

Very sorry. Damn. Will be fixed today.

It's all working fantastically now. The manual only needs a clearer eg for the /Array syntax, perhaps a block of code with all parameters correctly expressed for the basic (x,y) function.

Emails were v helpful. Thanks!

[jdaw1]

The placemats, which only required 14 major drafts and several ".1.1.1" updates... I'm learning...

And one bug fix in the code , and one new feature. No trouble at all.

[jdaw1]

A note to self, following the 1966 Horizontal on Thu 27 June 2013: if RAYC is printing, he prints glasses sheets to card, and TN sheets to paper. So they should be separated, perhaps by

• /PageOrderingNonDecanterLabelGlasses {[ GlassesOnSheets length {-1} repeat ]} def

[RAYC]

Alternatively they can simply be printed to paper, if preferred. I marginally favour card, but the difference is very slight.

[jdaw1]

Broader question: what should be the default? That leads to a question about our behaviour.

What do we do when setting up a tasting?
1. Arrange glasses sheets on table, simultaneously putting TN sheets with the glasses sheets.
2. Arrange glasses sheets, and when that is all done, then put the TN sheets with the glasses sheets.
Yesterday we did the second.

If we do #1, the the ideal ordering is the current one:

• Person 1
  • Glasses
  • TNs
• Person 2
  • Glasses
  • TNs
• Person 3
  • Glasses
  • TNs
• Person 4
  • Glasses
  • TNs
• !

If we do #2, the ideal ordering is

• Glasses
  • Person 1
  • Person 2
  • Person 3
  • Person 4
  • !
• TNs
  • Person 1
  • Person 2
  • Person 3
  • Person 4
  • !

I’m half-preferring acknowledging that we tend to do the second behaviour, so should have the second arrangement. Thoughts?

(FYI, the programming effort is about zero the switch would be very easy to implement.)